[자료구조] - 이진 검색 트리 (Binary Search Tree - BST)

 

 

 

 

 

 

이진 검색 트리 (Binary Search Tree - BST)

이진 검색 트리는 이진트리(Binary Tree)의 한 종류이며, 비어있거나 다음 조건을 만족해야 합니다.

1. 모든 원소는 Key를 가지고 있으며, 어떠한 원소도 동일한 키를 가지지 않습니다. 즉 Key는 유일합니다.
2. 트리의 루트는 비어있지 않은 왼쪽 서브트리의 있는 Key보다 큰 값을 가집니다.
2. 트리의 루트는 비어있지 않은 오른쪽 서브트리의 있는 Key보다 작은 값을 가집니다.
4. 왼쪽 서브트리와 오른쪽 서브트리는 또다시 이진검색트리입니다.

 

 

이진 검색 트리는 AVL트리, 2-3트리, B트리, 레드-블랙 트리 등, 앞으로 배울 여러 트리들의 기본이 되는 자료구조이므로 확실하게 알고 넘어가야 합니다.

BST의 한가지 형태

 

 

 

 

 

 

 

 

 

시간복잡도

이진 검색 트리는 원소의 삽입과 삭제, 검색에 있어서 평균적으로 log n의 시간 복잡도를 가집니다.

	정렬되지 않은 배열	정렬된 배열	이진검색트리(BST)
삽입	$$O(1)$$	$$O(n)$$	$$O(log\;n)$$
삭제	$$O(n)$$	$$O(n)$$	$$O(log\;n)$$
검색	$$O(n)$$	$$O(log\;n)$$	$$O(log\;n)$$

 

그러나 이진 검색 트리는 원소들이 삽입되는 순서에 따라, 최악의 경우 한쪽으로 치우친 사향 이진 트리가 될 수도 있습니다.

사향 BST

이러한 경우 LinkedList와 별반 다를것이 없는 구조가 되며, 시간 복잡도는 O(n)으로 증가합니다.

이러한 문제점을 해결하기 위해 BST의 균형을 맞추어주는 다음 트리들을 사용합니다. 

AVL Tree,  2-3 Tree ,  Red-Black Tree,  B-tree, ...

 

 

 

 

 

 

 

 

 

 

시간 복잡도와 트리의 높이의 관계

이진 검색 트리에서는 삽입, 삭제, 검색 모두 $log \;n$ 의 시간 복잡도를 가집니다.

 

이진트리의 노드의 개수가 n일 때  완전 이진트리의 경우 높이는 $[log2(n)]+1$ 이며,

따라서 작업의 총 횟수는 $log_2(n)$ 번을 넘지 않습니다.

 

따라서 삽입, 삭제, 검색의 시간복잡도는 평균적으로 트리의 높이만큼의 시간 복잡도를 가집니다.

 

그러나 모든 상황에서 이진 검색 트리가 완전 이진 트리가 되기는 어렵습니다.

평균적으로 데이터가 랜덤하게 들어오는 경우 완전 이진 트리에 수렴하겠으나,

트리가 한쪽으로 치우친 편향 이진 트리(skewed binary tree)의 경우 시간 복잡도는 O(n) 까지 증가할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

이진 검색 트리의 삽입

삽입은 간단합니다. 

 

삽입할 값의 Key와 루트의 Key를 비교하여, 추가하려는 Key의 값이 작으면 왼쪽으로, 크다면 오른쪽으로 진행하여, 다음 위치에 노드가 존재하지 않는다면 추가합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이진 검색 트리의 삭제

세가지 경우로 나눠서 보도록 하겠습니다.

 

 

 

잎 노드의 삭제

 

잎 노드의 경우 바로 삭제가 가능합니다.

 

 

 

 

 

자식이 1개인 노드의 삭제

노드를 삭제한 뒤, 자식 노드를 부모 노드 위치로 옮겨주면 됩니다.

 

 

 

 

 

자식이 2개인 노드의 삭제

노드를 삭제한 후, 해당 노드의 좌측 서브트리 중 최대값을 찾아 삭제한 노드의 위치를 대신합니다.
이때 좌측 서브트리의 입장에서는 노드가 하나 삭제되는 형태인데, 이는 잎 노드 혹은 자식 노드가 1개인 노드의 삭제로 생각할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이진 검색 트리 오름차순으로 출력하기

완전 이진 트리를 오름차순으로 출력하기 위해서는 중위 탐색(Inorder traversal)을 진행하면 됩니다.

중위 탐색의 순서는 left -> root -> right의 순서로, 이는 BST 입장에서 left는 root보다 작은 값, right는 root보다 큰 값이므로, 오름차순의 출력 순서와 동일합니다.

 

 

 

 

 

 

이진 검색 트리 내림차순으로 출력하기

완전 이진 트리를 내림차순으로 출력하기 위해서는 중위 탐색을 역으로 진행하면 됩니다. 

즉 right -> root -> left의 순서로 출력하면 이는 내림차순이 됩니다.

 

 

 

 

 

 

 

 

 

 

 

자바로 구현

https://ttl-blog.tistory.com/707

[Java] 자바로 이진 검색 트리(BST) 구현하기

 

 

 

 

 

 

 

이진 검색 트리 시뮬레이터

https://www.cs.usfca.edu/~galles/visualization/BST.html

Binary Search Tree Visualization