-
BST에서 위와 같은 Skewed Tree의 경우 복잡도가 O(n)이 나오는 한계점을 해결하기 위해 AVL Tree가 고안됨. AVL 은 해당 자료구조를 만든 사람의 앞글자를 하나씩 따서 만든 것(..)
AVL Tree 예시
AVL Tree
Not AVL Tree
용어
- 노드의 height: h
- balance factor: bf (왼쪽 서브트리의 height - 오른쪽 서브트리의 hegiht)
- empty height: -1
특징
- AVL 트리는 BST이면서 동시에 균형을 유지하고 있음
- 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하 (왼쪽과 오른쪽 서브트리의 height 계산 결과가 1, 0, -1 이외라면 해당 트리는 AVL 트리가 아님 - 만약 height가 없는 경우는 -1)
- 즉, 모든 노드들은 balance factor 를 알고 있음
- 균형을 유지하고 있기 때문에 이진 검색 시의 효율성을 보장
문제는 이러한 균형을 맞추려 하다 보니 유지하는 방법이 복잡함. 예를 들어, 노드 삽입이나 삭제로 인해 왼쪽과 오른쪽 서브트리의 height의 계산결과가 2, -2가 나온 경우, 트리를 rotation 시켜줘야 함
rotation에는 2가지 관점이 있는데 AVL 트리를 height balance로 유지하는 것과 binary search tree로 유지하는 관점이 있음. 관점은 나뉘어 있지만 가장 중요한 것은 rotation 시키면서 트리의 height를 낮춰야 복잡도가 줄어듦
rotation의 방법은 4가지로 1번만 rotation 시키는 LL, RR와 2번 rotation 시키는 LR, RL이 존재.
Single Rotation
LL (Right)
왼쪽은 차이가 2이고 오른쪽은 0이므로 왼쪽이 무너진 경우. 이 경우는 오른쪽으로 트리를 회전시켜주면 해결
RR (Left)
왼쪽은 차이가 0이고 오른쪽은 2이므로 오른쪽이 무너진 경우. 이 경우는 왼쪽쪽으로 트리를 회전시켜주면 해결
Double Rotation
위에서 본 LL, RR과는 달리 방향이 일정하지가 않기 때문에 첫 회전에서는 LL 또는 RR로 방향을 맞춘 다음 다시 회전시켜 높이의 균형을 유지시켜줌
RL (Right & Left)
가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 RR의 형태를 이루기 때문에 자리를 바꾼 후, RR 로 회전을 한번 더 시킴.
LR(Left & Right)
가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 LL의 형태를 이루기 때문에 자리를 바꾼 후, LL 로 회전을 한번 더 시킴.
장단점
- 검색, 삽입, 삭제 모두 O(logN)이며 항상 균형을 맞춤
- 프로그래밍하기가 어렵고 디버깅 또한 어려움.
- 위 검색, 삽입, 삭제가 빠르긴 하지만 균형을 맞추는데에 시간이 듦
- 대규모 tree를 이룬 후 검색하는 것은 DB에서 주로 발생하는데 DB는 이미 B-Tree 자료구조를 사용 중임
