[자료구조] AVL 트리의 개념과 회전연산

아는벌·2023년 2월 28일

자료구조

목록 보기

8/8

AVL 트리

트리 높이의 균형을 유지하는 이진탐색트리

임의의 노드 x에 대해 x의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진탐색트리
트리가 한 쪽으로 치우쳐 자라나는 현상을 방지
삽입/삭제로 인해 균형이 깨지면 회전 연산을 통해 트리의 균형을 유지
균형 이진트리를 만들면 트리의 높이는 O(logN) -> 탐색, 삽입, 삭제 연산의 수행시간 O(logN) 보장

균형인수(BK; Balance Factor)

균형인수(BK) = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이

BF 이해를 돕기위한 그림이다. 노드 7은 왼쪽 서브트리의 높이는 3, 오른쪽 서브트리의 높이는 1이므로 BF는 2(= 3-1)가 되고, 노드 6은 왼쪽 서브트리의 높이는 2, 오른쪽 서브트리의 높이는 0으로 BF는 0(= 2-0)이다.

AVL트리는 모든 노드의 BF가 -1, 0, 1 중 하나여야 한다. 이를 벗어난다면 균형이 깨진 것을 의미하며 이때 회전으로 균형을 맞춘다.

AVL트리의 회전연산

AVL 트리에서 삽입/삭제 연산 수행 시 트리의 균형을 유지하기 위해 회전연산 사용

rotateRight

왼쪽 방향의 서브트리가 높아서 불균형이 발생할 때 서브트리를 오른쪽 방향으로 회전하기 위한 메소드

private Node rotateRight(Node n) {
	Node x = n.left;
    n.left = x.right;
    x.right = n;
    n.height = tallerHeight(height(n.left), height(n.right))+1; // 높이갱신
    x.height = tallerHeight(height(x.left), height(x.right))+1; // 높이갱신 
    return x;	// 회전 후 x가 n의 이전 자리로 이동되었으므로
}

노드의 왼쪽 자식노드 x(n.left)를 노드 n의 자리로 옮기고,
노드 n을 노드 x의 오른쪽 자식노드로(x.right) 만든다.

rotateLeft

오른쪽 방향의 서브트리가 높아서 불균형이 발생할 때 서브트리를 왼쪽 방향으로 회전하기 위한 메소드

private Node rotateLeft(Node n) {
	Node x = n.right;
    n.right = x.left;
    x.left = n;
    n.height = tallerHeight(height(n.left), height(n.right))+1; // 높이갱신
    x.height = tallerHeight(height(x.left), height(x.right))+1; // 높이갱신 
    return x;	// 회전 후 x가 n의 이전 자리로 이동되었으므로
}