on
#8 트리(Tree) 3 - AVL 트리
#8 트리(Tree) 3 - AVL 트리
1. AVL 트리
이진 탐색 트리를 활용한 데이터의 탐색은 분명 O(logN) 까지의 성능을 보일 수 있지만 트리가 한 방향으로 치우쳐
생성될 경우 최악의 경우 O(N) 까지 성능이 떨어질 수 있다. 반대로 이진 탐색 트리가 항상 균형 이진 트리가 되도록
할 수 있다면 항상 O(logN)의 성능을 보장할 수 있을 것이다. AVL 트리는 삽입, 삭제가 이뤄져도 항상 균형 상태를
유지하는 자가 균형 이진 탐색 트리이다.
2. AVL 트리의 특징
어떤 노드를 기준으로 하더라도 좌, 우 서브트리의 높이(깊이)가 2 이상의 차이를 보이지 않는다.
노드의 삽입/삭제가 발생할 때마다 매번 서브트리의 회전을 통해 균형을 맞춘다.
균형을 거의 완벽하게 유지하기 때문에 탐색속도는 빠르지만 삽입/삭제의 속도가 이후에 설명할
Red-black 트리에 비해 느린편이다.
Red-black 트리에 비해 느린편이다. 삽입/삭제/탐색 모두 O(logN)을 보장한다.
3. 회전 알고리즘
① LL 회전
위 그림과 같이 기준이 되는 루트노드(1)의 좌측 서브트리와 우측 서브트리의 높이차이가 1보다 크고
좌측 자식 노드 기준으로 좌측 서브트리의 높이가 우측 서브트리의 높이보다 큰 상태를 LL상태 라고 한다.
좌측 자식 노드 기준으로 좌측 서브트리의 높이가 우측 서브트리의 높이보다 큰 상태를 라고 한다. LL 회전은 LL 상태에서 일어난다.
먼저 루트 노드(1)의 왼쪽 자식노드를 왼쪽 자식노드(2)의 오른쪽 자식노드(null) 로 한다.
원래 왼쪽 자식노드였던 2번 노드의 오른쪽 자식노드를 루트노드였던 1로 한다.
② RR 회전
위 그림과 같이 기준이 되는 루트노드(1)의 우측 서브트리와 좌측 서브트리의 높이차이가 1보다 크고
우측 자식 노드 기준으로 우측 서브트리의 높이가 좌측 서브트리의 높이보다 큰 상태를 RR 상태 라고 한다.
우측 자식 노드 기준으로 우측 서브트리의 높이가 좌측 서브트리의 높이보다 큰 상태를 라고 한다. RR 회전은 RR 상태에서 일어난다.
먼저 루트 노드(1)의 오른쪽 자식노드를 오른쪽 자식노드(2)의 왼쪽 자식노드(null) 로 한다.
원래 오른쪽 자식노드였던 2번 노드의 왼쪽 자식노드를 루트노드였던 1로 한다.
③ LR 회전
위 그림과 같이 루트노드 기준 좌측 서브트리 높이가 우측 서브트리보다 2이상 높고 좌측 자식노드 기준
우측 서브트리의 높이가 좌측 서브트리보다 높은 상태를 LR 상태라고 한다.
우측 서브트리의 높이가 좌측 서브트리보다 높은 상태를 LR 상태라고 한다. LR 회전은 LR 상태에서 일어난다.
LL, RR 회전을 알고있다면 여기서부터는 간단하다. 루트노드(1)의 좌측 자식노드(2)를 기준으로 RR 회전을
실행한 뒤, 루트 노드(1)를 기준으로 LL 회전을 실행해주면 된다.
④ RL 회전
위 그림과 같이 루트노드 기준 우측 서브트리 높이가 좌측 서브트리보다 2이상 높고 우측 자식노드 기준
좌측 서브트리의 높이가 우측 서브트리보다 높은 상태를 RL 상태라고 한다.
좌측 서브트리의 높이가 우측 서브트리보다 높은 상태를 RL 상태라고 한다. RL 회전은 RL 상태에서 일어난다.
LR 회전과 반대로 루트노드(1)의 우측 자식노드(2)를 기준으로 LL 회전을 실행한 뒤, 루트노드(1)를 기준으로
RR 회전을 실행해주면 된다.
4. AVL 트리의 연산
삽입/삭제(Insert, Delete) 이진 탐색 트리의 방식대로 데이터를 삽입/삭제한다. 루트 노드부터 시작하여 균형 재조정함수를 호출하여 균형을 재조정한다.
균형 재조정(Rebalance) 루트 노드로부터 시작 좌측 서브트리에 대해 균현 재조정 함수 재귀호출 우측 서브트리에 대해 균형 재조정 함수 재귀호출 좌측 서브트리와 우측 서브트리의 높이를 구한다. 만약 두 서브트리의 높이차이가 2 이상이라면 현재 루트노드를 기준으로 트리가 어느 상태인지 파악한다. 각 상태에 맞는 회전(LL, RR, LR, RL)을 실행한다. 루트 노드를 환한다.
from http://scala0114.tistory.com/109 by ccl(A) rewrite - 2021-10-07 17:26:55