이진탐색트리(Binary Search Tree)

1. 개념

모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작고 오른쪽 서브 트리는 해당 노드의 값보다 크다.

 

 

2. 순회

순회란? 이진탐색트리에 있는 모든 노드들을 한 번씩 방문하는 것. 이진탐색트리에서는 주로 중위선회(Inorder Traversal)를 사용한다.

 

- 중위선회

루트 노드부터 시작해서 일단은 왼쪽 노드를 따라서 간다. 더 이상 왼쪽 노드가 존재하지 않는 시점의 노드까지 간 후 해당 노드를 출력한다. 그리고 그 노드의 오른쪽 노드로 옮겨간다. 만약 이 때 옮겨갈 오른쪽 노드가 존재하지 않는다면 한 단계 위 레벨의 노드로 움직인다. 그리고 맨 처음 한 것과 같이 왼쪽에 있는 맨 마지막 노드로 옮겨간다. 그리고 또 오른쪽 노드로 움직인다. 이것을 계속해서 반복한다. 

 

 

3. 노드의 후임자(Successor), 선임자(Predecessor)

후임자: 해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드

선임자: 해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드

 

 

4. 이진탐색트리의 삽입/삭제/검색

- 삽입

맨 처음 루트 노드를 하나 설정을 해놓고 루트 노드보다 크면 오른쪽, 작으면 왼쪽에 새로운 노드를 삽입한다. 그리고 또 다른 노드를 삽입할 때는 루트 노드, 그리고 첫번째로 삽입한 노드와 크기를 비교하면서 크면 오른쪽 작으면 왼쪽에 넣는 방식을 유지한다.

 

- 삭제

삭제하기 위해선 우선 삭제하려는 노드가 있는지 검색을 하고 있으면 삭제를 한다. 삭제는 검색을 동반한다는 특징에 주목하는 것이 좋다.

 

(1) 자녀 노드를 가지지 않는 노드를 삭제할 때는 삭제될 노드를 가리키던 레퍼런스가 가리키는 것이 없도록 만들어주는 방식으로 처리한다. 

(2) 자녀 노드 하나를 가지는 노드를 삭제할 때는 삭제하려는 노드의 부모 노드가 삭제하려는 노드의 자식 노드를 바로 가리키도록 만들어주는 방식으로 처리한다. 

(3) 자녀 노드 두 개를 가지는 노드를 삭제할 때는 삭제될 노드의 오른쪽 서브 트리에서 가장 작은 값을 원래 삭제될 노드의 자리로 끌어올린다(대체 시킨다).

 

 

5. 이진탐색트리의 시간복잡도

	최고	평균	최악
삽입	O(1)	O(logN)	O(N)
삭제	O(1)	O(logN)	O(N)
검색	O(1)	O(logN)	O(N)

(N은 트리의 노드 수)

 

 

6. 이진탐색트리의 장점, 단점

장점

- 삽입, 삭제가 유연하다. 

- 값의 크기에 따라 좌우 서브 트리가 나눠지기 때문에 삽입, 삭제, 검색이 (보통의 경우에) 빠르다.

 

단점

- 최악의 경우에 시간복잡도가 너무 크다.

- 트리가 구조적으로 편향될 시 삽입, 삭제, 검색 등의 여러 동작의 수행 시간이 오래 걸린다.  => 이걸 극복하기 위해 스스로 균형을 잡는 이진 탐색 트리가 사용된다. (Ex. Red-Black 트리)

 

 

 

[Thanks to]

- 유튜브 쉬운 코드