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

이진탐색트리(BST)란?

이진 트리의 한 종류로, 아래의 특징을 만족한다.

1. 각 node는 뚜렷한 데이터 값을 갖는다.
2. 더 작거나 또는 더 큰 값으로 key 값이 분류될 수 있다.
3. 모든 node는 오른쪽 서브 트리보다 작고, 왼쪽 서브 트리보다 크다.

Binary Search Tree

 

 

node 탐색하기

node를 탐색하는 방법은 간단하다.

1. 현재 node가 target이 아니라면, 크기 비교를 한다.
2. 작다면 왼쪽 서브 트리로, 크다면 오른쪽 서브 트리로 이동한다.
3. 만약 해당 노드가 leaf노드라면 false를 반환한다.
4. 위 과정을 반복하면서 target을 찾는다.

 

node 추가하기

node를 추가하는 방법도 쉽다.

탐색하는 방법과 유사하게 tree를 내려가면서 해당 값이 들어갈 자리를 찾아서 추가해주면 된다.

 

예를 들어 16이라는 값을 추가한다고 하면

1. 45 vs 16을 비교 -> left 서브 트리로 이동
2. 9 vs 16을 비교 -> right 서브 트리로 이동
3. 17 vs 16을 비교 -> left 서브 트리로 이동
4. 더이상 내려갈 곳이 없으니 17의 왼쪽 node로 16을 추가

 

node 삭제하기

삭제하는 방법은 3가지 경우를 고려해서 삭제한다.

1. 자식 없는 leaf node의 경우
2. 자식이 1개인 경우
3. 자식이 2개인 경우

1. 자식이 없는 leaf node인 경우

부모가 가리키던 값을 null값으로 바꿔서 삭제하기

leaf node인 13을 제거하는 경우

 

2. 자식이 1개인 경우

부모가 바로 그 자식과 연결되도록 바꾸기

자식이 있는 13을 제거하는 경우

3. 자식이 2개인 경우

오른쪽 서브 트리에서 가장 작은 값 또는 왼쪽 서브 트리에서 가장 큰 값을 골라 제거하고자 하는 대상의 자리로 복사

그 후 복사한 값이 원래 있던 자리의 node의 상태에 따라 1, 2의 방법으로 해당 자리의 node를 제거

root인 45를 제거하는 경우