Binary Search Tree

Binary Search Tree(BST - 이진검색트리) 는 비어있거나 아래의 속성을 만족하는 binary tree 입니다. 자세하게 Binary Search (이진 검색)과 Linked List를 결합한 자료구조입니다. 이진 검색의 검색능력을 유지하면서 빈번한 값의 삽입, 삭제가 가능하도록 고안되었습니다. 이진검색의 경우 검색에 소요되는 시간복잡도는 O(log₂n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. linked list의 경우 자료 입력, 삭제에 필요한 시간복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 복잡도가 발생합니다.

정의

1. 각각의 모든 node 들의 key는 중복된 값이 아님 (unique)
2. 기존의 binary tree는 순서가 없지만 BST는 순서가 존재
3. parent node의 왼쪽은 부모보다 작은 값이고 오른쪽은 부모보다 큰 값임
4. 왼쪽, 오른쪽의 서브 트리또한 BST임

Search

1. 찾고자 하는 Key와 root node값이 같으면 성공
2. Key가 root node 값보다 작다면 (key < root node) 왼쪽의 sub tree로 이동
3. Key가 root node 값보다 작다면 (key > root node) 오른쪽의 sub tree로 이동
4. 1~3번 반복
5. 만약 조건에 맞는 데이터가 없으면 실패 (tree에 값이 존재하지 않는 경우)

위 그림에서 120 값을 찾는 예시입니다. 

1.  root node(=100)와 찾고자 하는 값 (=120) 비교
2. root node보다 찾고자 하는 값이 더 크므로 (100 < 120) 오른쪽 subtree로 이동
3. 오른쪽 subtree의 노드값(=150)과 찾고자 하는 값(=120)과 비교
4. 찾고자 하는 값이 더 작으므로 (150 > 120) 왼쪽 subtree로 이동
5. 120값이므로 검색 성공

Insert

값을 삽입하고자 하거나 찾고자 하는 값이 없을 경우 루트노드에서 시작, 값을 비교해가면서 tree의 가장 마지막까지 간 다음 값을 입력

예시

위 그림에서 80을 넣고자 하면 아래와 같은 위치에 삽입

Delete

1. 첫 단계는 지우고자 하는 값이 해당 tree에 있는지 search
2. 지우고자 하는 값이 leaft node(가장 마지막)에 위치해있으면, 그냥 지우면 됨
3. internal node라면 다음과 같이 분기가 됨
   1. 지워야 하는 node가 child node를 1개 가지고 있는 경우, internal node를 지운 후 해당자리에 child node를 옮김
   2. 지워야 하는 node가 child node를 2개 가지고 있는 경우, 왼쪽의 subtree에서 가증 큰 노드 또는 오른쪽 subtree에서 가장 작은 노드를 옮김

예시

50 (leaf node) 삭제

75 (internal node 이며 1개의 child node 존재) 삭제

150 (internal node 이며 2 child node 존재) 삭제

1. 왼쪽의 subtree에서 가장 큰 노드를 이동

2. 오른쪽 subtree에서 가장 작은 노드를 이동

internal node이며 child node를 2개 가지고 있는 경우 삭제하는 방법은 2가지가 있지만 여기서 조건적으로 효율적인 방법이 존재. 1, 2번의 방법 중 트리의 height를 줄일 수 있는 방법을 채택하는 것이 향후 트리 검색의 속도를 향상시킬 수 있음

복잡도

BST는 검색, 삽입, 삭제 모두 O(h)임. h는 BST의 높이(height)

BST에서는 inorder(LVR) 검색 방식을 사용

BST는 평균(최상) 시간복잡도가 O(log₂n)이지만 최악의 경우 O(n)임. (skewed tree이면 node의 수만큼 시간이 소요됨)

• tree가 complete binary tree거나 full binary tree이면 O(log₂n), skewed tree이면 O(n)

위 O(N)의 경우때문에 노드가 얼마 되지 않아도 검색속도가 나오지 않을 가능성이 존재함. 이 때문에 AVL Tree가 고안됨