Binary Search Trees(1)

Binary Search Trees(BST)

Property:

노드의 left subtree에 있는 원소들의 value는 노드의 value보다 작다.

노드의 right subtree에 있는 원소들의 value는 노드의 value보다 크다.

BST의 예

BST의 Operation

1. Check BST

Check BST

어떠한 노드에 대해서 left subtree의 모든 원소들의 value들은 노드의 value보다 작아야 하고, right subtree의 모든 원소들의 value들은 노드의 value보다 커야한다.

이를 확인하기 위해서 upper bound와 lower bound를 설정한다. left subtree의 upper bound는 노드의 value보다 1 작은 값이고, right subtree의 lower bound는 노드의 value와 같다.

이를 recursive하게 구현하여 모든 원소에 대해 lower bound와 upper bound를 설정해 원소의 value가 bound안에 들어가는지 확인한다. 

만약 모든 원소가 bound 안에 들어간다면 BST임을 확인할 수 있다.

 

2. BST Search

BST에서 찾고자 하는 value가 있을 때 현재 노드의 value와 비교하여 크다면 오른쪽 subtree에서 다시 찾고, 작다면 왼쪽 subtree에서 다시 찾는다.

같다면 현재 노드를 반환하고 search는 종료된다.

 

3. BST Insert

Insert

새로운 데이터는 leaf node에 붙인다.

root에서부터 시작하여 insert할 element의 value와 현재 노드의 value를 비교하여 크면 right subtree에서 반복, 작다면 left subtree에서 반복한다.

만약 현재 노드가 null이라면 그 자리에 element를 insert한다.

 

4. BST Remove

Remove를 할 때는 단순히 원소를 제거만 해서는 안된다. 제거되는 원소의 subtree들을 BST property에 맞게 재배치를 해주어야 하기 때문이다.

BST Remove

만약 삭제하는 원소의 자식이 없다면 그냥 제거하면 된다.

자식이 1개라면 그냥 삭제하는 원소의 부모와 자식을 연결시켜주면 된다.

문제는 자식이 2개인 경우이다.

자식이 2개인 경우는 right subtree에서 가장 작은 원소를 찾는다(right subtree에서 가장 왼쪽에 있는 원소).

그 후 그 원소와 삭제할 원소를 swap하고 바뀐 위치에서 삭제할 원소를 삭제한다.

 

 

Time Complexity

Tree의 높이를 d라고 하자.

그렇다면 각 operation의 Time Complexity는 다음과 같다.

Find : O(d)

Insert : O(d)

Delete : O(d)

 

만약 tree가 balanced되어 있다면 O(d) = O(logn)이다. 그러나 worst case의 경우(모든 원소가 자식이 1개인 경우) O(d) = O(n)과 같다.

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업