6. Binary Search Tree

Binary Search Tree란?

Binary Search Tree(BST, 이진 탐색 트리)는 다음과 같은 조건을 만족하는 이진 트리를 말한다.

 

노드 L을 left child, 노드 R을 right child로 갖는 노드 A가 있을 때, key(L) ≤ key(A) ≤ key(R)을 만족한다.

 

즉, 모든 노드의 key 값은 left child의 key 값보다 크거나 같고, right child의 key 값보다 작거나 같다.

 

따라서 BST를 inorder traversal(전위 순회)를 통해 탐색하면 key 값이 작은 순서대로 방문하게 된다.

 

 

Search

BST에서 원하는 key 값을 찾으려면 다음과 같은 작업을 반복하면 된다.

 

찾으려는 노드를 T, 현재 방문중인 노드를 C라고 했을 때

key(T)<key(C) 이면, left child로 이동하고,

key(T)>key(C) 이면, right child로 이동한다.

 

이런 식으로 root 노드부터 원하는 key 값을 찾을 때까지 이동하면 된다.

 

 

위와 같은 BST에서 key 값이 3인 노드를 찾아보자.

 

 

먼저 root 노드인 6번 노드는 3보다 크기 때문에 left child인 4번 노드로 이동한다.

4번 노드도 3보다 크기 때문에 left child인 2번 노드로 이동한다.

2번 노드는 3보다 작기 때문에 right child인 3번 노드로 이동한다.

원하는 key 값인 3번 노드를 찾았으니 종료한다.

 

이와 같이 검색은 최악의 경우 트리의 높이 만큼의 시간이 필요하다. 따라서 시간복잡도는 O(h)이다.

 

 

Insert

삽입은 검색과 같은 방법을 노드가 비어있을 때까지 수행하면 된다.

 

 

위 노드에 key 값이 10인 노드를 insert 해보자.

 

 

 

먼저 root 노드인 6번 노드는 10보다 작으므로 right child인 9번 노드로 이동한다.

9번 노드도 10보다 작으므로 right child인 11번 노드로 이동한다.

그리고 11번 노드는 10보다 크므로 left child로 이동해야 하는데 비어있으므로 해당 자리에 노드를 삽입한다.

 

이처럼 삽입도 검색과 똑같은 과정이 필요하므로 O(h)의 시간이 걸린다.

 

 

Delete

삭제 역시 먼저 삭제하려는 노드를 key 값을 통해 찾아야 한다.

그 후 삭제하려는 노드의 child가 없을 때, child가 하나일 때, child가 둘일 때로 나누어 진행한다.

 

1) child가 없을 때

 

위와 같은 BST에서 3번 노드는 child가 없기 때문에 삭제해도 정상적으로 BST가 유지된다.

 

 

따라서 그냥 삭제해주면 된다.

 

 

2) child가 하나일 때

 

예를 들어 위와 같은 BST에서 11번 노드를 삭제할 경우에는 child를 빈 자리로 옮겨주면 된다.

 

 

11번 노드를 삭제하고 삭제한 자리에 child 노드인 12번 노드로 채워주면 정상적으로 BST가 유지된다.

 

 

2) child가 2개일 때

위와 같이 2개의 child를 갖고 있는 9번 노드를 삭제할 때는 right child subtree에서 가장 작은 값의 노드로 대체한다.

 

이 노드는 right child subtree를 inorder traversal(중위 순회)를 통해 탐색할 때 첫번째로 방문하는 노드이다.

 

위 BST에서는 10번 노드가 right child subtree에서 가장 작은 값의 노드이다.

 

 

이제 대체할 노드를 찾았다면 삭제할 노드를 없애준 뒤 해당 자리를 대체 노드로 채워주면 된다.

 

삭제 역시 삭제할 노드를 탐색할 때 걸리는 시간 때문에 O(h)의 시간복잡도를 갖는다.