- 이진 검색 트리는 검색과 삽입, 삭제에 평균
Θ(logn)
시간이 소요되지만 운이 나쁘면 트리 모양이 균형을 이루지 못합니다.- 균형이 많이 깨지면 다음과 같은 트리가 나타납니다.
- 이와 같은 경우는 검색과 삽입, 삭제에 평균
Θ(n)
시간이 소요됩니다.
균형 검색 트리
는 최악의 경우
에도 이진 트리의 균형이 맞도록 유지해서 작업들이 항상 O(logn)
시간을 보장합니다.이진 검색 트리
에서는 분기할 때 최대 2개로 제한되는데 이보다 더 많이 분기할 수 있는 트리들도 있다. 🠔 다진 검색 트리다진 검색 트리
에서는 균형
이 더 중요하다.AVL 트리
좌회전(t): 🠔 t: 회전의 중심 노드 RChild 🠔 t.right RLChild 🠔 RChild.left RChild.left 🠔 t t.right 🠔 RLChild t.height 🠔 max(t.right.height, t.left.height) + 1 RChild.height 🠔 max(RChild.right.height, RChild.left.height) + 1
우회전(t): 🠔 t: 회전의 중심 노드 LChild 🠔 t.left LRChild 🠔 LChild.left LChild.left 🠔 t t.left 🠔 LRChild t.height 🠔 max(t.left.height, t.right.height) + 1 LChild.height 🠔 max(LChild.right.height, LChild.left.height) + 1
EX) 좌회전으로 두 곳의 불균형을 해결하는 예
LL
LR
RR
RL
balanceAVL(t, type): switch type: case LL: 우회전(t) case LR: 좌회전(t.left) balanceAVL(t, LL) case RR: 좌회전(t) case RL: 우회전(t.right) balanceAVL(t, RR)
균형 이진 검색 트리
RB 트리
1. 부모 노드 p가 블랙일 경우
2. 부모 노드 p가 레드일 경우
pf) 레드나 블랙 색상을 고려하지 않고, 가장 이상적으로 꽉 채워진 트리의 Depth는 ⌊logn⌋+1이다.
그러므로, 레드 블랙 트리가 아무리 잘 만들어져도
루트에서 임의의 Leaf까지 이르는 경로에 존재하는 블랙 노드의 개수는 ⌊logn⌋+1을 넘을 수 없다.
레드 블랙 특성 3에 따라, 레드 노드는 두 개가 연속해서 존재할 수 없다.
그러므로 루트에서 임의의 Leaf에 이르느 경로에서 레드 노드는 블랙 노드의 개수보다 많을 수 없다.
즉, 루트에서 임의의 Leaf에 이르는 경로의 길이는 2(⌊logn⌋+1)을 넘을 수 없다.
이는 점근적으로 O(logn)에 비례한다.