[자료구조] Binary Search Tree

정의

다음과 같은 조건을 만족하는 binary tree를 binary search tree(BST) 라고 한다.

1. left subtree의 element들이 root element보다 작을 것.

2. right subtree의 element들이 root element보다 클 것.

 

 

가령, 1,2,3,4,5,6,7을 위 BST로 구현하면 다음과 같이 될 것이다. 

 

특징

1. 앞서 binary tree를 포스팅하면서 binary tree의 순회 방식에는 pre-, in- , post- order의 3 가지 형태가 있다고 했었다. 이 중 inorder traversal은 root node의 방문 순서가 중간에 오는 방식이다. (left -> root -> right node 순서로 방문)

 

따라서, BST를 inorder traversal을 통해 탐색하면, 모든 node들의 element들을 오름차순으로 나열한 것과 같은 결과가 나온다.

 

2.탐색, 삽입, 삭제 연산의 수행 시간이 모두 O(h)이다. (h: BST의 높이)

 

특정 element를 탐색하려는 경우, 최악의 경우는 해당 element를 담은 node가 leaf node인 경우이고, 이 경우 root node로부터 시작하여 h step 만큼 타고 내려가야 하므로 탐색(search)은 O(h)의 time complexity를 갖는다.

 

새로운 element를 삽입하면, root node로부터 leaf node에 이를 때까지 다음과 같은 과정을 통해 새로운 node가 삽입될 위치를 결정한다.

- 현재 node의 element 보다 작으면 left subtree로 이동

- 현재 node의 element 보다 크면 right subtree로 이동

 

 

위 그림은 검은색 BST에 element가 35인 새로운 node를 삽입하는 과정을 그림으로 표현한 것이다. 따라서, 새로운 node가 삽입될 때는 h step을 거쳐 leaf node로 삽입되므로 삽입 연산의 time complexity는 O(h)이다.

 

삭제 연산의 경우 몇 가지 case를 고려해야 한다.

 

1. leaf node 삭제

2. sub tree(child)가 하나뿐인 node 삭제

3. sub tree가 두 개 다 온전히 있는 node 삭제.

 

먼저 leaf node를 삭제하는 경우 그냥 삭제해 버리면 그만이고, sub tree가 하나뿐인 node를 삭제하는 경우는 해당 node의 위치에 subtree를 붙이면 된다. 

 

그러나 만일 2개 subtree를 온전히 다 가진 node를 삭제하는 경우, 해당 node를 left-subtree의 최대값 또는 right-subtree의 최소값으로 교체하여야 한다. 그리고 그 값은 각각 left subtree의 가장 오른쪽 leaf node, right subtree의 가장 왼쪽 leaf node이고, 이들을 찾기 위해서 최대 h step만큼 Tree를 타고 내려가야 하므로 삭제 연산의 Time complexity가 O(h)이다.