개념
AVL 트리
- 이진탐색트리(BST)의 한 종류
- 스스로 균형을 잡는 트리
- balance factor를 통해 균형 유지
이진 트리(binary)
각 노드의 자녀 노드 수가 최대 2개 (left child/right child) 인 트리
이진 탐색 트리 (Binary Search Tree)
모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가진다
and 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다
BF(x) = h(lSubtree(x)) - h(rSubtree(x))
임의의 노드 x에 대해서 성립함
- BF = Balance Factor
- h = height(높이)
- lSubtree = Left Subtree
- rSubtree = Right Subtree
특징
BF(x) ∈ {-1, 0, 1}
임의의 노드 x에 대해서 성립함
AVL 트리의 균형 잡기
- 트리에 삽입 or 삭제 후에,
BF(x) ∉ {-1, 0, 1} 인 노드가 생기면 균형을 맞추는 작업을 수행
- 루트 노드에서 특정 노드를 (삽입/삭제) 처리하고,
(삽입/삭제)가 발생한 위치에서 루트 노드로 거꾸로 올라가면서 BF를 확인했을 때,
균형이 깨졌다면 재조정을 해준다.
동작 방식 예시
오른쪽-오른쪽 편향의 경우
왼쪽-왼쪽 편향의 경우
오른쪽-왼쪽 편향의 경우
왼쪽-오른쪽 편향의 경우
이진 탐색 트리의 시간 복잡도
*N = 트리의 노드 수
순서: best / avg / worst
- insert: Θ(1) / O(logN) / Θ(N)
- delete: Θ(1) / O(logN) / Θ(N)
- search: Θ(1) / O(logN) / Θ(N)
AVL 트리의 시간 복잡도 (장점/단점)
순서: best / avg / worst
- insert: Θ(1) / O(logN) / O(logN)
- delete: Θ(1) / O(logN) / O(logN)
- search: Θ(1) / O(logN) / O(logN)
장점:
AVL 트리는 균형을 엄격하게 맞추기 때문에, 최악의 경우의 시간 복잡도가 개선되었다단점:
(삽입/삭제)를 할 때마다 트리 균형을 확인하고, 만약 균형이 깨졌을 경우,
트리 구조를 재조정하기에 이때 시간이 꽤 소요된다
Red-Black 트리
AVL 트리의 단점을 해결
