BST(Binary Search Tree)와 Find/Insert/Delete?

BST는 (sorted array라는 가정하에) 시간복잡도가 O(log n)이 걸리는 Binary Search를 활용한 트리 형태이다

 

하지만 그러한 Binary Search를 굳이 배열이 아닌 트리를 이용해서 구현하는 이유는?

- 다른 element에 비해 특정 element에 대한 검색을 많이 할 경우 ➡ 해당 element를 root에 가깝게 위치시키면 시간을 절약할 수 있음(ADT BST)

- Array에 element를 삽입 혹은 삭제하는 경우 ➡ 최악의 경우 O(n)시간이 소모된다

이러한 이유로 ㅇㅣ진 탐색트리를 이용한다

 

다시 정확하게 정의하자면, 

Binary Search Tree: 자식이 최대 2명이고, Binary Search를 가이드하는 형태를 띤 트리

BST의 가장 큰 특징은 key값 k를 가지는 non-leaf node p에 대해

p의 left subtree의 모든 node들의 key값은 k보다 작고, right subtree의 key값은 k보다 크다

는 것이다

BST의 연산은 다음과 같다

1️⃣ get(key) : key값을 가진 node가 있는 경우, 해당 node를 return

root node부터 탐색하면서 key값과 일치하는 node를 찾는 과정

현재 node의 key값을 기준으로, 다음에 left/right중 어느 subtree를 탐색할지 결정한다

current node의 key값이 찾으려는 key값이라면 해당 node를 반환한다

if 현재 node가 찾으려는 노드가 아니면서, leaf node라면? 찾으려는 key값은 BST에 존재하지 않는다

시간 복잡도 = O(h) (BST의 height)

 

2️⃣ insert(key) : key값을 가진 node가 없는 경우, 해당 node를 BST에 추가

해당 node가 삽입될 위치를 찾기 전 까지는 get연산과 유사하다

get연산과 똑같은 과정을 통해 새로운 key값이 들어갈 수 있는 위치를 탐색한 뒤,

이미 존재한다면 새로 추가해주지 않고 그냥 함수를 끝내고,

존재하지 않는다면 key값을 가진 새로운 node를 생성해서 현재 node의 left/right child로 추가해준다

(언제나 해당 tree의 leaf node가 된다)

시간 복잡도 = get + 삽입 = O(h) + O(1) = O(h)

 

3️⃣ delete(key) : key값을 가진 node가 있는 경우, 해당 node를 BST에서 제거

delete연산은 크게 3가지 상황으로 나뉜다

- 삭제할 node가 leaf node

- 삭제할 node가 하나의 child node를 가지고 있을 경우

- 삭제할 node가 두 개의 child node를 가지고 있을 경우

 

Case 1: 삭제할 node가 leaf(단말) node일 때

➡ 해당 node만을 tree에서 삭제하고 종료한다

 

Case 2: 삭제할 node의 child가 하나일 때

➡ 삭제할 node를 해당 node의 child node로 대체한다(해당 child를 root로 가지는 subtree가 한번에)

위와 같은 그림에서는 9의 left subtree(left child node)인 8을 9 자리에 대체한다

왼: case 1 / 오: case 2

 

Case 3: 삭제할 node의 child가 두 개일 때

➡ 삭제하려고 하는 node를 p라고 할 때, p의 right subtree중 leftmost node u

(right subtree의 root node에서 이동 불가능할 때 까지 계속 left로 이동할 때 도달하는 node)를 찾는다

p의 key값을 u의 key값으로 교체한 뒤, u를 삭제한다

(해당 과정은 left subtree - rightmost로도 적용 가능하다)

이 때, u의 child는 최대 1개!! (u를 찾는 과정에서 u의 left child는 존재할 수 없기 때문)

위의 그림에서 6(p)을 삭제한다고 할 때, u는 7이 된다(right subtree의 leftmost node)

p의 key값을 7로 바꾼 뒤, child가 1개인 u를 삭제한다(u의 right subtree를 u로 대체)

시간복잡도 = p와 p의 parent 찾기 + subtree와 left/rightmost node 찾기 + key값 대체 + 연결 부분 수정 = O(h) + O(h) + O(1) + O(1) = O(h)

 

이렇게, 모든 연산이 tree의 height인 O(h)의 시간복잡도를 가진다

왼 - Complete Binary Tree 

하지만, 오른쪽 그림과 같이 BST가 극도로 편향되어 있다면?

결국 시간복잡도 O(h) = O(n)이 되고 시간복잡도가 최악이 된다

 

그렇기 때문에 트리의 모양이 균형을 유지할 수 있도록, 연산하다가 균형이 무너졌다면 균형을 잡아주는 연산이 추가로 필요하다

그 내용은 다음 포스팅에 ...

 

 

출처 - 충북대학교 소프트웨어학과 자료구조 강의자료