이진 탐색 트리 (BST : Binary Search Tree)

이진 탐색 트리 (BST : Binary Search Tree)

이진 탐색 트리(BST: Binary Search Tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다.

 

1. 각 노드에 중복되지 않는 키(key)가 있다.

2. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두개의 자식 노드를 갖는다.
3. 왼쪽 서브 트리는 부모 노드의 키보다 작은 키를 갖는다.
4. 오른쪽 서브 트리는 부모 노드의 키보다 큰 키를 갖는다.

 

 

이진 탐색 트리에서의 검색

1. 루트노드로 부터 시작한다.

2. 검색하려는 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 가서 찾는다.

3. 노드를 비교하면서 내려가다가 일치하는 값이 나오면 해당 노드를 반환한다.

4. 더이상 비교할 노드가 없으면 검색이 실패했음을 알린다. (NULL or NIL)

 

*Swift : NIL은 포인터가 아니라 특정 타입에 대한 값의 부재를 나타냄

 

이진 탐색 트리에서의 삽입

1. 삽입을 하기 전, 검색을 수행한다.
2. 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

 

이진 탐색 트리에서의 삭제

삭제할 노드의 경우에 따라 다르게 처리

• 리프 노드인 경우 : 대상 노드를 그냥 삭제한다.
• 자식 노드가 하나인 경우 : 대상 노드의 부모 노드와 자식 노드를 연결시켜준다.
• 자식 노드가 두 개인 경우 : 이진 탐색 트리의 성질을 깨지 않는 원소를 찾아 자리를 바꾼 후 삭제한다. 삭제 된 원소의 부모 자식을 연결 시킨다.