이진 탐색 트리란?
이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종입니다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐습니다.
이진 탐색 트리는 정렬된 이진트리로써 다음과 같은 속성을 가지고 있습니다.
- 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함됩니다
- 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함됩니다.
- 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 여야합니다.
- 중복된 키를 허용하지 않습니다.
데이터 검색
- 루트에서 시작합니다.
- 검색 값을 루트와 비교합니다. 루트보다 작으면 왼쪽에 대해 재귀하고 크다면 오른쪽으로 재귀합니다.
- 일치하는 값을 찾을 때까지 절차를 반복합니다.
- 검색 값이 없으면 null을 반환합니다.
데이터 삽입
- 새 데이터는 항상 리프 노드에 최종삽입됩니다.
- 루트에서 시작합니다.
- 삽입 값을 루트와 비교합니다. 루트보다 작으면 왼쪽으로 재귀하고 크다면 오른쪽으로 재귀합니다.
- 리프 노드에 도달한 후 노드보다 크다면 오른쪽에 작다면 왼쪽에 삽입합니다.
데이터 삭제
3가지 경우가 존재합니다.
1. 삭제할 노드가 리프 노드이다.
2. 삭제할 노드의 자식이 하나다.
3. 삭제할 노드의 자식이 둘이다.
1.
그냥 노드만 삭제하면 됩니다.
2.
노드를 삭제하고 자식 노드를 삭제된 노드의 부모에 직접 연결합니다.
3.
- 삭제할 노드의 오른쪽 서브트리를 찾습니다.
- 해당 서브트리를 중위 순회하여 나온 가장 첫번째 노드(successor)와 위치를 바꿉니다.
- successor를 삭제합니다.
한계점
다만, 트리의 높이가 한쪽으로 치우쳐져 있다면, 시간복잡도는
O(N)으로 다른 선형 구조의 탐색과 동일하게 되어버립니다.
이를 해결하기 위해 AVL Tree, Red-Black Tree 등의 자료 구조가 존재합니다.
