[Data Structure] 데이터 구조, 자료 구조 총정리

데이터 구조란?

• 데이터를 메모리에 저장할 때, 데이터의 순서나 위치 관계를 규정한 것 (자료구조, Data structure)
• 즉, 데이터를 효율적으로 사용할 수 있도록 정리하는 방법이다. → 결국 효율적인 데이터 구조로 메모리 사용 효율을 높인다.
• 종류
  • 선형 구조 (Array, Dynamic Array, Linked List, Oueue, Stack, Hash Table)
  • 비선형 구조 (Tree, Graph)

선형 구조

비선형 구조

배열(Array)

• 배열은 데이터를 한 열로 연속해서 정렬하는 데이터 구조이다.
  • 장점 : 원하는 데이터에 접근할 때 편리하다. → 인덱스가 존재하기 때문
  • 단점 : 데이터를 추가하거나 삭제하려면 시간이 오래 걸린다.

배열 관련 코드 설명

const a = [Blue, Yellow, Red];

// 데이터 접근 방법 → 인덱스 활용
console.log(a[0]); // Blue
console.log(a[1]); // Yellow
console.log(a[2]); // Red

// 데이터 추가 및 삭제
// 추가
a.push('Green'); // [Blue, Yellow, Red, Green]
a.unshift('White'); // [White, Blue, Yellow, Red, Green]

// 삭제
a.pop(); // [White, Blue, Yellow, Red]
a.shift(); // [Blue, Yellow, Red]

• 메모리상 위치는 인덱스를 바탕으로 계산할 수 있고, 각 데이터에 직접 접근할 수 있다. (= 랜덤 접근)
• 위에서 예시로 보여줬던 추가, 삭제는 배열의 앞과 뒤에서 데이터를 다루는 것이고 중간 부분에 있는 데이터를 다루고 싶을 땐 slice() 메서드를 이용한다.
• 배열 메서드는 따로 다뤄보자.

계산 시간 : 배열 (O(1) or O(n))

• 배열에 저장되어 있는 데이터의 개수가 n이라면, 랜덤 접근이 가능하기 때문에 상수 시간 O(1)에 데이터에 접근할 수 있다.
• 반면, 데이터를 앞이나 중간에서 추가하거나 삭제할 때는 그 뒤에 있는 모든 데이터를 하나씩 뒤로 옮기거나 앞으로 옮기는 연산이 발생한다. 이렇게 배열의 앞이나 중간에서 추가, 삭제한다면 O(n)의 시간이 소요된다. 

링크드 리스트(Linked List)

• 리스트는 데이터를 일직선으로 줄줄이 정렬한 데이터 구조이다.
  • 장점 : 데이터의 추가, 삭제 쉬움
  • 단점 : 원하는 데이터에 접근하는 시간이 오래걸림
• 각 데이터는 포인터를 가지고 잇어 다음 데이터의 메모리 주소를 가리킨다.
  • 따라서, 리스트의 각 데이터는 메모리상에서 연속된 영역에 배치되어 있을 필요가 없다. 분산 배치 되어있다.
• 연속적으로 배치되어 있지 않고 개별적으로 저장되어 있기 때문에 특정 데이터에 접근하려면 데이터의 포인터를 따라가야 한다. 
  • 이를 순차 접근 혹은 시퀀스 액세스(suquential access)라고 한다. 
• 데이터를 쉽게 추가, 삭제할 수 있는 이유는 추가하거나, 삭제할 위치의 앞에 있는 데이터의 포인터를 바꾸면 되기 때문이다.

링크드 리스트 관련 코드 설명

• 코드로 살펴보자.
  1. append : 리스트 가장 뒤에 값 추가
  2. prepend : 리스트 가장 앞에 값 추가
  3. delete : 원하는 값 삭제
  4. deleteFirst : 리스트 가장 앞에 있는 값 삭제
  5. deleteLast : 리스트 가장 뒤에 있는 값 삭제
  6. display : 리스트 출력

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
        // 초기 값을 null로 해준 이유는 꼬리 tail부분에 있는 자료는 가르킴을 받는 자료가 뒤에 없기 때문
    }// constructor
}// Node

class LinkedList {
    constructor() {
        this.head = null; // 처음에 데이터가 없다면 head는 null이다.
        this.size = 0;
    }// constructor

    //append
    insertBack(data) {
        let newNode = new Node(data);
        let current;

        if (!this.head) {
            this.head = newNode;
            return
        }

        current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
        this.size++;
    }//insertBack

    //prepend
    insertFirst(data) {
        this.head = new Node(data, this.head);
        this.size++;
    }//insertFirst

    //delete
    deleteData(data) {
        let currentNode = this.head;
        if (currentNode && currentNode.data == data) {
            this.head = currentNode.next;
            currentNode = null;
            return
        }
        let prevNode = null;
        while (currentNode && currentNode.data != data ) {
            prevNode = currentNode;
            currentNode = currentNode.next;

        }
        if (!currentNode) { return }
        prevNode.next = currentNode.next;
        currentNode = null;
        this.size--;
    }// deleteData

    deleteFirst() {
        if (this.head) {
            this.head = this.head.next;
        }
        this.size--;
    }//deleteFirst

    deleteLast() {
        if (!this.head) { return }
        if (!this.head.next) { this.head = null; return }
        let seconedLast = this.head;
        while (seconedLast.next.next) {
            seconedLast = seconedLast.next;
        }
        seconedLast.next = null;
        this.size--;
    }//deleteLast

    display() {
        let currentNode = this.head;
        let viewDataStructure = '';
        while (currentNode) {
            viewDataStructure += `${currentNode.data}->`;
            currentNode = currentNode.next;
        }
        console.log(viewDataStructure + "end");
    }//display
}// LinkedList

const linkedSample = new LinkedList();

linkedSample.insertFirst(1);
linkedSample.insertFirst(2);
linkedSample.insertFirst(3);
linkedSample.insertBack(9);
linkedSample.display(); // 출력 : 3->2->1->9->end
linkedSample.deleteData(2);
linkedSample.display(); // 출력 : 3->1->9->end 
linkedSample.deleteFirst();
linkedSample.display(); // 출력 : 1->9->end
linkedSample.deleteLast();
linkedSample.display(); // 출력 : 1->end

• 기본적인 리스트의 경우 마지막 데이터는 포인터가 없다. 하지만 마지막 데이터의 포인터가 맨 앞의 데이터를 가리키게 하면 원형 리스트 혹은 순환 리스트의 형태가 된다.
  • 데이터의 맨 앞이나 맨 뒤라는 개념은 사라진다.
  • 항상 일정한 개수의 최신 데이터를 보관해야 하는 상황에서 사용되곤 한다.
• 기본 리스트의 경우 각 데이터의 포인터가 하나인데, 각 데이터가 포인터 두 개로 앞뒤 데이터를 가리키게 만든 양방향 리스트도 있다.
  • 리스트를 앞에서 뒤로, 뒤에서 앞으로도 검색할 수 있어 편리하다.
  • 다만, 양방향 리스트는 포인터 수가 늘어난 만큼 데이터양이 증가하고, 데이터를 저장하기 위한 공간도 늘어난다는 단점이 있다.

계산 시간 : 링크드 리스트 (O(1) or O(n))

• 특정 원소를 조회할 때, 해당 노드까지 탐색해야하기 때문에  O(n)의 시간이 소요된다.
• 데이터를 앞이나 중간에서 추가하거나 삭제할 때는 포인터를 바꿔주면 되기에 O(1)의 시간이 소요된다.

배열(Array)과 링크드 리스트(Linked List)

	접근	추가	삭제
리스트	느림	빠름	빠름
배열	빠름	느림	느림

 

스택(Stack)

• 스택은 데이터를 한 열로 저장하지만, 서류를 쌓아 올릴 때처럼 마지막에 추가한 데이터에만 접근할 수 있다.
• 새로운 서류가 오면 가장 위에 놓고, 꺼낼 때도 맨 위에 있는 서류를 꺼내는 것이다.
• 따라서, 스택처럼 나중에 넣은 것부터 꺼내는 후입선출 구조를 Last In First Out, 줄여서 LIFO라고 한다.

Stack - 과정 설명

1. (1) 현재 A라는 데이터만 저장되어 있다.
2. (2) B 데이터를 푸쉬(추가)한다. 스택에 데이터를 추가하면 맨 위에 추가된다. (스택에 데이터를 넣는 작업을 푸시(Push)라고 한다.)
3. (3) B 데이터를 팝(꺼냄)한다. 스택에서 데이터를 꺼낼 때는 가장 위에서 올린 즉, 가장 직전에 추가된 데이터부터 꺼낸다. (스택에서는 데이터를 꺼내는 작업을 팝(Pop)이라 한다. )

Stack 관련 코드 설명

// Stack
const stack = [];

stack.push("Apple"); // Enqueue [ Apple ]
stack.push("Banana"); // Enqueue [ Apple, Banana ]
stack.push("Orange"); // Enqueue [ Apple, Banana, Orange ]

stack.pop(); // Dequeue -> Orange 제거
// [ Apple, Banana ]

stack[stack.length-1]; // Peek -> Banana

const isEmpty = () => {
    return stack.length == 0; // false
}

• 스택도 리스트나 배열처럼 데이터를 일렬로 저장하지만, 데이터의 추가와 삭제가 한쪽 끝에서만 이뤄진다.
• 또한, 맨 위에 놓인 데이터에만 접근할 수 있기 떄문에 중간에 있는 데이터를 접근하려면 해당 데이터가 스택의 맨 위에 놓을 떄까지 데이터를 팝해야한다. 
• 그래서 스택이 가장 유용하게 쓰이는 상황은 항상 최신 데이터에 접근해야 할 때는 유용하게 사용된다.
  • 우리가 다룰 알고리즘인 깊이 우선 탐색에서는 탐색 후보 중에서 항상 최신의 것을 선택해야 하기에 Stack을 사용한다. 

Stack - 시간 복잡도

• 스택의 삽입과 삭제 연산은 항상 top에서만 일어나므로 삽입과 삭제에 소요되는 시간 복잡도는 O(1)로 고정된다.
  • 삽입  - O(1)
  • 삭제 - O(1)(pop)
  • 검색 - O(n)

큐(Queue)

• 큐도 지금까지 알아본 데이터 구조처럼 데이터를 한 열로 저장한다. 그렇다면 차이점이 뭘까?
• 큐는 추가하는 쪽과 삭제하는 쪽이 반대이다. 즉 큐를 대기 행렬이라고도 하는데, 이름이 의미하듯 줄을 서 있는 행렬과 비슷하다.
• 새로 온 사람은 제일 뒤에 줄을 서고, 제일 앞에 선 사람부터 순서대로 처리된다.
• 큐처럼 먼저 넣은 것을 먼저 꺼내는 선입선출 구조를 First In First Out, FIFO라고 부른다.

Queue - 과정 설명

1. (1) Stack과 동일하게 A라는 데이터만 큐에 저장되어 있다.
2. (2) B 데이터를 인큐(큐에 데이터를 추가하는 작업, enqueue)한다. 그럼 맨 뒤에 저장된다.
3. (3) 큐에서 데이터를 꺼낼 때 가장 오래된 즉, 가장 아래에 있는 데이터부터 꺼낸다. 따라서 A 데이터를 꺼낸다. 이 과정을 디큐(dequeue)라고 한다. 

Queue 관련 코드 설명

// Queue
const queue = [];

queue.push("Apple"); // Enqueue [ Apple ]
queue.push("Banana"); // Enqueue [ Apple, Banana ]
queue.push("Orange"); // Enqueue [ Apple, Banana, Orange ]

queue.shift(); // Dequeue -> Apple
// [ Banana, Oragne ]

queue[0]; // Peek -> Banana

const isEmpty = () => { 
    return queue.length == 0; // false
}

• 큐도 스택과 마찬가지로 데이터를 조작할 수 있는 위치가 제한적이다.
• 스택은 같은 쪽에서 데이터를 제어하는 반면, 큐는 추가하는 쪽과 삭제하는 쪽이 반대이다. 따라서 스택과 마찬가지로 중간에 있는 데이터에 접근할 수 없고, 필요한 데이터가 나올 때까지 Dequeue해야한다.
  • Queue는 오래된 데이터부터 차례로 처리하는 것은 지극히 자연스러운 방식이기에 폭넓게 사용되고 있다.
  • 예를 들어, 너비 우선 탐색에서는 탐색 후보 중 항상 가장 오래된 것을 선택해야 하기 때문에 큐를 사용한다.

Queue - 시간 복잡도

• 큐의 삽입은 스택의 삽입과 같아 O(1)으로 고정되며, 삭제는 배열로 데이터 구조가 만들어져 있으면 맨 앞에 원소를 삭제시 뒤에 있는 원소들의 인덱스 위치값이 다 바뀌므로 O(n)의 시간복잡도를 가진다. → 이를 주의하여 문제를 풀어야한다.
  • 삽입  - O(1)
  • 삭제 - O(n)(shift) : 1,000초과 되는 경우에는 클래스를 활용하여 Queue 알고리즘을 구현하여 사용하는 것이 좋다.
  • 검색 - O(n)

 

해시 테이블(Hash Table)

• 해시 테이블은 해시 함수를 활용해 만든 데이터 구조이다. 그리고 키(Key)와 값(Value)을 하나의 짝으로 저장하는 데이터 구조이다. 
• 해쉬 테이블의 장점과 단점
  • 장점 : 빠른 검색 및 삽입, 유연한 크기 조정 → 메모리 효율 좋음
  • 단점 : 무작위성 (순서가 없다.)
• 일반적으로 키는 데이터의 식별자이며, 값은 데이터의 내용을 나타낸다. 자바스크립트에서는 해시 테이블과 같은 자료구조를 가진 객체가 있다.
  • 객체는 Array, Map, Object 등을 포함한다. Array를 활용하여 해시 함수와 충돌 메커니즘을 직접 구현할 수 있는데 다음 글에서 직접 구현하며 돌아보려 한다. 이를 통해 작동 방식을 이해하는데 도움을 얻을 수 있다. 실무에서는 최적화된 Object나 Map 사용이 일반적이기 때문에 지금은 이 두개를 살펴보려 한다.
• 객체는 프로퍼티의 집합이며, 프로퍼티는 키와 값으로 구성된다. 
  • 프로퍼티 키 : 빈 문자열을 포함하는 모든 문자열 또는 심벌 값
  • 프로퍼티 값 : 자바스크립트에서 사용할 수 있는 모든 값

해시 테이블 코드 관련 설명

// Object 객체 예시
const person = new Object;

person['name'] = 'Kim';
person.age = 25;

console.log(person);
// { name: 'Kim', age: 25 }

// Map 객체 예시
const map = new Map;

// 데이터 추가 set()
map.set('name', 'Kim');
map.set('age', '20');
console.log(map);
//Map(2) { 'name' => 'Kim', 'age' => '20' }

// 키 순회 for...of
for (let key of map.keys()) { 
    console.log(key);
}

// 값 순회 for...of
for (let value of map.values()) { 
    console.log(value);
}

// 키-값 쌍 순회 for...of
for (let [key, value] of map.entries()) { 
    console.log(key, value);
}

// forEach 사용
map.forEach((value, key) => {
    console.log(key, value);
});

// 값 가져오기 get()
console.log(map.get('name')); // Kim
console.log(map.get('age')); // 20

// 키 존재 여부 확인 has()
console.log(map.has('name')); // true
console.log(map.has('addresss')); // false

// 키-값 쌍 삭제 delete()
map.delete('age');

// 맵 크기 확인 size
console.log(map.size); // 1

// 모든 요소 제거 clear()
map.clear();

• Map 객체는 고유의 용도와 특징을 가지고 있으며, 효율적이고 유연한 해시 테이블로서의 역할을 잘 수행한다. 

그럼 Map 객체와 Object 객체의 차이는 무엇일까? Map과 Object의 차이점에 대해 알아보자.

new Map vs new Object

1. Key 타입

• Object : 반드시 문자열(String)이나 심볼(Symbol)
• Map : 문자열, 객체, 함수 등 모든 값 사용 가능

2. Key 순서

	new Object	new Map
Key 타입	반드시 문자열(String)이나 심볼(Symbol)	문자열, 객체, 함수 등 모든 값 사용 가능
Key 순서	키는 삽입 순서를 보장하지 않음 문자열 키는 순서 없이 저장, 숫자 키는 자동 정렬	키는 삽입된 순서대로 저장됨
크기	수동으로 키의 개수를 세어야 함 ex. Object.keys(object).length	'size'라는 속성을 사용하여 쉽게 크기를 확인할 수 있다. ex. map.size
성능	객체는 단순한 키-값 저장 및 조회에 최적화되어 있지만, 고성능 해시 테이블로 설계된 것이 아님	맵은 해시 테이블로 설계되어 빠른 조회, 삽입, 삭제 성능을 제공한다.
반복	'for...in'루프 또는 Object.keys(), Object.values(), Object.entries()와 같은 메서드 사용	'for...of'루프와 keys(), values(), entries() 등의 메서드를 사용하여 간단히 반복할 수 있음
메서드	객체에는 Object.prototype의 메서드들이 있다. 이러한 메서드들이 키로 사용될 수 있는 위험이 있음	맵은 자체 메서드를 가지며, Map.prototype의 메서드들이 충돌할 위험이 없음
사용 사례	일반적으로 구조화된 데이터 저장 및 속성 접근에 적합	다양한 유형의 키를 사용해야 하거나, 삽입 순서를 유지해야 하는 경우 적합

• 메서드 예시 코드

let obj = {};
obj['toString'] = 'some value';
console.log(obj['toString']); // 'some value' (Object의 기본 메서드와 충돌 가능)

let map = new Map();
map.set('toString', 'some value');
console.log(map.get('toString')); // 'some value' (충돌 없음)

• 결론
  • Object 객체는 기본적으로 해시 테이블 역할을 하지만, 특정 상황에서는 Map이 더 적합할 수 있다.
  • 따라서 Object와 Map은 용도와 특성이 다르기 때문에, 필요에 따라 적절한 자료구조를 선택해야 한다.

Hash Table - 시간복잡도

• 평균 시간복잡도
  • 삽입 : O(1)
  • 삭제 : O(1)
  • 탐색 : O(1)
• 최악의 시간복잡도
  • 모든 키가 동일한 해시 값을 가질 때 해시 테이블은 연결리스트 처럼 동작하게 되어 O(n)의 시간 복잡도를 갖는다.  
• Map은 다양한 타입의 키를 허용하고 성능이 최적화되어 있어, 일반적으로 해시 테이블의 용도로 더 많이 사용되고 있다.

힙(Heap)

• 힙은 그래프의 트리 구조 중 하나로 우선 순위 큐를 구현할 때 사용된다.
• 우선순위 큐는 데이터를 자유롭게 추가할 수 있지만, 꺼낼 때 항상 작은 데이터를 꺼낸다. 따라서 우선순위 큐(Priority Queue)를 구현할 때 주로 사용되는 자료구조이다.
  • 노드 : 힙을 비롯한 트리 구조에서 각 정점
  • 힙 : 이 노드에 데이터를 저장

힙의 기본 개념

• 최대 힙(Max Heap)
  • 부모 노드의 값이 자식 노드의 값보다 크거나 값은 완전 이진 트리
• 최소 힙(Min Heap)
  • 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리

힙 관련 코드 설명

class MinHeap { 
    constructor() { 
        this.heap = [];
    }

    getParentIndex(index) { 
        return Math.floor((index - 1) / 2);
    }

    getLeftChildIndex(index) { 
        return 2 * index + 1;
    }

    getRightChildIndex(index) {
        return 2 * index + 2;
    }

    swap(index1, index2) { 
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

    insert(value) { 
        this.heap.push(value);
        this.heapifyUp();
    }

    heapifyUp() {
        let index = this.heap.length - 1;
        while (this.getParentIndex(index) >= 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) { 
            this.swap(index, this.getParentIndex(index));
            index = this.getParentIndex(index);
        }
    }

    remove() {
        if (this.heap.length === 0) {
            return null;
        }

        if (this.heap.length === 1) {
            return this.heap.pop();
        }

        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return root;
    }

    heapifyDown() {
        let index = 0;
        while (this.getLeftChildIndex(index) < this.heap.length) {
            let smallerChildIndex = this.getLeftChildIndex(index);
            if (this.getRightChildIndex(index) < this.heap.length && this.heap[this.getRightChildIndex(index)] < this.heap[smallerChildIndex]) { 
                smallerChildIndex = this.getRightChildIndex(index);
            }
            if (this.heap[index] <= this.heap[smallerChildIndex]) {
                break;
            }
            this.swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }

    peek() {
        if (this.heap.length === 0) { 
            return null;
        }
        return this.heap[0];
    }
}

const minHeap = new MinHeap();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(2);
minHeap.insert(7);

console.log(minHeap)
console.log(minHeap.peek()); // 2
console.log(minHeap.remove()); // 2
console.log(minHeap.peek()); // 3

메서드 설명

• insert()
  • 새로운 요소를 힙의 마지막에 추가하며 heapiftUp()를 사용하여 힙의 특성을 유지함
• remove()
  
  • 힙 루트 요소(최소 힙의 경우 최솟값) 제거, 힙의 마지막 요소를 루트로 이동시킨 후 heapityDown()를 사용하여 힙의 특성을 유지
• Heapify
  • heapfiyUp : 삽입 후, 요소를 올려가며 부모와 비교하여 교환
  • heapfitDwon : 삭제 후, 요소를 내려가며 자식들과 비교하여 교환

힙 - 시간복잡도

• 힙은 항상 가장 작은, 가장 큰 데이터가 맨위에 있기 때문에 최소/최대 값에 접근할 때는 데이터 개수와 상관없이 O(1)시간으로 최소값을 꺼낼 수 있다.
• 하지만 데이터를 꺼낸뒤 힙을 재구성할 때는 맨 끝에 있는 데이터를 맨 위로 옮긴 뒤 자식 노드와 비교하면서 밑으로 이동한다. 따라서 이 작업의 시간은 트리의 높이에 비례하다. 데이터의 수가 n이라면 계산 시간은 O(log n)이 된다. 데이터를 추가할 때도 마찬가지다.
  • 삽입 : O(log n)
  • 삭제 : O(log n)
  • 최소/최대 값 접근 : O(1)

힙 활용

• 보관 중인 데이터의 최솟값, 최대값을 빈번하게 찾아야 하는 경우에 힙이 유용하다.
• 다익스트라 알고리즘은 매번 후보 정점들 중에서 최솟값을 선택하는데 이때 힙을 사용하기도 한다.

이진 탐색 트리 (BST, Binary Search Tree)

• 이진 탐색 트리는 그래프의 트리 구조로 각 노드에 데이터가 저장된다. 
• 정렬된 데이터를 효율적으로 탐색, 삽입, 삭제할 수 있는 자료 구조이다.

특징

• 각 노드는 최대 두 개의 자식 노드를 가진다. 
• 각 노드의 값은 왼쪽 가지에 있는 노드들의 값보다 크다.
• 각 노드의 값은 오른쪽 가지에 있는 노드들의 값보다 작다.
• 따라서 이진 탐색 트리의 최솟값은 제일 위에 있는 노드에서 왼쪽 트리만 탐색하면 찾을 수 있다. 반대로 최대값은 젤 위에 있는 노드에서 오른쪽 트리만 탐색하면 찾을 수 있다.

이진 탐색 트리 관련 코드 설명

노드 클래스

class TreeNode { 
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

 

이진 탐색 트리 클래스

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const newNode = new TreeNode(value);
        if (this.root === null) {
            this.root = newNode;
            return;
        }
        this.insertNode(this.root, newNode);
    }

    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

    search(value) {
        return this.searchNode(this.root, value);
    }

    searchNode(node, value) {
        if (node === null) {
            return false;
        }
        if (value < node.value) {
            return this.searchNode(node.left, value);
        } else if (value > node.value) {
            return this.searchNode(node.right, value);
        } else {
            return true;
        }
    }

    delete(value) {
        this.root = this.deleteNode(this.root, value);
    }

    deleteNode(node, value) {
        if (node === null) {
            return null;
        }
        if (value < node.value) {
            node.left = this.deleteNode(node.left, value);
            return node;
        } else if (value > node.value) {
            node.right = this.deleteNode(node.right, value);
            return node;
        } else {
            // 노드가 하나의 자식만 있거나 자식이 없을 때
            if (node.left === null) {
                return node.right;
            } else if (node.right === null) {
                return node.left;
            }

            // 노드가 두개의 자식이 있을 때
            node.value = this.minValueNode(node.right).value;
            node.right = this.deleteNode(node.right, node.value);
            return node;
        }
    }

    minValueNode(node) {
        let current = node;
        while (current.left !== null) {
            current = current.left;
        }
        return current;
    }

    inOrderTraversal(node, callback) {
        if (node !== null) {
            this.inOrderTraversal(node.left, callback);
            callback(node.value);
            this.inOrderTraversal(node.right, callback);
        }
    }
}

const bst = new BinarySearchTree();

bst.insert(10); // (1)
bst.insert(1); // (2)
bst.insert(23); // (3)
bst.insert(8); // (4)
bst.insert(59); // (5)

console.log(bst.search(10)); // true

bst.inOrderTraversal(bst.root, value => console.log(value)); 
// Output : 1, 8, 10, 23, 59

이진 탐색 트리의 활용

• 데이터베이스의 인덱스 구조로 사용되어 효율적인 데이터 검색을 가능하게 한다.
• 다양한 정렬 및 검색 알고리즘의 기초로 사용된다.
• 텍스트 편집기와 같은 애플리케이션에서 빠른 문자열 검색을 지원
• 일정 관리 시스템에서 이벤트를 효율적으로 관리하고 검색할 수 있다.

이진 탐색 트리 - 시간 복잡도

• 데이터를 찾거나 추가할 때, 현재 위치의 데이터와 크기를 비교하여 왼쪽 혹은 오른쪽으로 진행하면서 노드의 위치를 찾는다.
• 비교 연산은 트리의 높이 만큼 수행하게 된다. 따라서 계산 시간은 O(log n)이 된다.
• 다만, 트리가 한쪽으로 치우쳐서 세로로 늘어진 모양이 되면 높이가 높아져 계산 시간이 O(n)이 된다.

이진 탐색 트리, 더 나아가기

• 균형 이진 탐색
  • 트리가 한쪽으로 치우치면 형태를 수정하여 항상 균형을 유지하는 것, 검색 효율을 높인다.
• B 트리
  • 이진 탐색 트리의 경우 각 노드의 자식 노드가 최대 두 개 였는데, 이를 m개(m은 미리 정해 둔 상수)로 확장하고 자식 노드 수에 자유도를 부여하여 트리의 균형을 맞춤

결론

이렇게 그림으로 이해하는 알고리즘 책을 통해 기본 자료구조를 정리할 수 있었다. 자료구조는 물론 알고리즘 모두 해당 개념의 원리를 잘 이해해야 응용할 수 있다고 생각한다. 이 자료구조 개념 정리를 통해 앞으로 기능 구현시 어떤 자료구조, 알고리즘을 활용하여 시간복잡도를 단축시킬 수 있고, 성능을 최적화할 수 있는지 고민하고 다양한 문제 해결 방법을 연구하고자 한다.

 

🔗 Reference

• 그림으로 이해하는 알고리즘 - 도서
• 모던 자바스크립트 Deep Dive - 도서