1. 개요

각 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드만 있고, 각 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드만 있다.
좌우 서브트리는 각각이 다시 이진 탐색 트리이다.
따라서 이진 탐색 트리에서 최소값을 찾으려면 트리에서 가장 왼쪽으로 가면 되고, 가장 큰 값을 찾으려면 트리에서 가장 오른쪽으로 가면 된다.

2. 이진 트리 탐색

이진 트리의 모든 노드를 방문하여 어떠한 작업을 진행하는 것을 이진 트리 탐색이라고 한다. 대표적으로는 중위순회, 전위순회, 후위순회가 있다.
왼쪽 자식 노드를 L, 오른쪽 자식 노드를 R, 내 노드를 P라고 할 떄

• 중위순회(in-order traverse): L-P-R
• 전위순회(pre-order traverse): P-L-R
• 후위순회(post-order traverse): L-R-P
  순서로 방문한다.
  내 노드(P) 기준으로 중위, 전위, 후위라는 이름이 붙는다고 생각하면 기억하기 쉬울 것 같다. 왼쪽 노드는 오른쪽 노드보다 먼저 방문!

아래 트리를 각각의 방법으로 순회해보자.

중위순회

방문 순서 : 1-3-4-6-7-8-10-13-14

전위순회

방문 순서 : 8-3-1-6-4-7-10-14-13

후위순회

방문 순서 : 1-4-7-6-3-13-14-10-8

3. 노드의 후임자, 선임자

후임자(successor): 해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드 ex) 위의 노드에서 8의 후임자는 ? 10

선임자(predecessor): 해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드 ex) 위의 노드에서 6의 선임자는 ? 4

4. 검색, 삽입, 삭제

검색

검색하고자 하는 값을 루트 노드와 먼저 비교한다.

• 검색하고자 하는 값 === 루트노드의 값 : 루트노드 리턴.
• 검색하고자 하는 값 < 루트노드의 값: 왼쪽 서브트리에서 재귀적으로 검색
• 검색하고자 하는 값 > 루트노드의 값인 경우 : 오른쪽 서브트리에서 재귀적으로 검색

삽입

삽입을 하기 전 검색 수행 => 검색 후 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여 왼쪽이나 오른쪽에 새로운 노드 삽입.

삭제

삭제하기 전 검색 수행 => 검색 후 일치하는 노드가 있어야 삭제 수행

• 자녀가 0개일 때 : 해당 노드 단순 삭제, 삭제될 노드를 가리키고 있던 레퍼런스도 없애야 함.
• 자녀가 하나 있을 때 : 해당 노드를 삭제한 뒤 자식 노드를 고 자리로 고대로 옮김. 삭제될 노드를 가리키던 레퍼런스가 자녀 노드를 가리키도록 변경.
• 자녀가 둘일 때 : 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값, 또는 오른쪽 서브트리에서 가장 작은 값으로 대체함.

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

best case

insert, delete, search: θ(1)

루트 노드를 추가, 루트 노드를 삭제, 검색하고자 하는 값이 루트노드에 있음.

average case

insert, delete, search : O(logN)

왼쪽 서브트리와 오른쪽 서브트리 중 선택한 쪽만 집중하면 되므로, 노드를 1/2씩 줄여나가는 것과 같음.

worst case

insert, delete, search : θ(N)

이진 탐색 트리가 왼쪽 또는 오른쪽으로 편향되어 있는데, insert, delete, search를 함에 있어 리프노드까지 가야할 경우이다.

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

장점

• 삽입, 삭제가 유연하다. (레퍼런스만 재조정하면 되니까)
• 삽입, 삭제, 검색이 (편향되지 않은 경우) 빠르다. (좌우 서브트리로 나뉘어서 모든 노드를 확인할 필요가 없어지고 시간 복잡도도 θ(N)보다 작은 O(logN)이 될 수 있음.)
• in-order traverse를 하면 값의 순서대로 노드 순회 가능.

단점

• 트리가 한쪽으로 편향되어 있는 경우 삽입, 삭제, 검색 수행 시간 악화됨.
  => 이러한 문제를 해결해야 할 경우 스스로 균형을 잡는 이진 탐색 트리를 사용

참고:
https://www.youtube.com/watch?v=i57ZGhOVPcI&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=8
쉬운 코드

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC
위키백과

면접을 위한 CS 전공지식 노트(주홍철 저)