Table of Contents
목차
이진 탐색 트리 Binary Search Tree (BST)
- 이진 트리:
정렬 여부와 관계 없이 모든 노드가 둘 이하의 자식을 갖는 단순한 트리 형태 - 이진 탐색 트리: 정렬된 트리
- 노드의 왼쪽 서브트리: 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄짐
- 노드의 오른쪽 서브트리: 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이워짐
- 이렇게 왼쪽과 오른쪽의 값들이 각각 값의 크기에 따라 정렬되어 있는 트리가 이진 탐색 트리
시간 복잡도
\(O(log_{2}n)\): 매우 좋은 편
- 1억 개의 아이템도 단 27번이면 모두 찾아낼 수 있다
[ex] 49를 찾아라
- 해당 노드가 49보다 크면 이 노드의 왼쪽(더 작은 쪽) 탐색
- 해당 도드가 49보다 작으면 이 노드의 오른 쪽(더 큰 쪽) 탐색
[최악의 경우]
BST는 이처럼 랜덤하게 생성해도 대부분의 경우 균형이 잘 맞는 아름다운 형태로 트리를 표현할 수 있지만,
운이 나쁘면 트리의 모양이 균형을 제대로 이루지 못할 수 있음
균형이 많이 깨지면 탐색 시에 O(n) 에 근접한 시간이 소요될 수 있음
- 이렇게 되면 연결 리스트와 다르지 않음
[ex] 1을 찾아라
- 1 을 찾기 위해서는 루트부터 맨 끝까지 차례대로 모두 탐색해야 하므로 비효율적
자가 균형 이진 탐색 트리 Self-Balancing Binary Search Tree
따라서 위의 ‘최악의 경우 트리’는 균형을 맞춰 줄 필요가 있다.
그래서 고안해낸 것이 바로 ‘자가 균형 이진 탐색 트리’
의미
자가 균형(또는 높이 균형) 이진 탐색 트리는 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리
- 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지
- 즉 높이를 가능한 한 낮게 유지하는 것이 중요(주로 중간값이 루트)
[예시] 다음 그림과 같이 불균형과 균형의 차이는 크게 높이로 구분 가능 - 1): 루트의 높이가 6으로, 균형이 맞지 않는 트리
- 2): 루트의 높이가 3으로, 높이를 가능한 한 작게 유지한 트리
이처럼 루트의 높이로 불균형과 균형을 구분 가능
AVL tree
이와 같이 높이 균형을 맞춰주는 자가 균형 이진 탐색 트리의 대표적인 형태
6월 안에 설명 추가 예정
레드-블랙 tree
자바의 해시맵 또한 효율적인 저장 구조를 위해 해시 테이블의 개별 체이닝 Separate Chaining 시연결 리스트와 함께 레드-블랙 트리를 병행해 저장하는 구조로 구현되어 있음 6월 안에 설명 추가 예정