[자료구조] AVL 트리 - 회전 연산을 통해 균형을 유지하다

 

AVL 트리

 

AVL 트리는 트리가 한쪽으로 치우치는 것을 방지하여 트리 높이의 균형을 유지한다는 특징이 있다.

즉, 삽입이나 삭제 시에 균형이 어긋나게 되면 스스로 회전 연산을 통해 균형을 유지하는,

자체 힐링이 가능한 트리이다.

 

 

 

 

이러한 AVL 트리(a.k.a 균형 트리)를 사용하는 이유는 탐색, 삽입, 삭제 연산 시에 균일한 수행 시간 O(logN)을 보장하기 때문인데, 이는 AVL 트리의 높이와 관계가 있다.

 

n개의 노드를 가진 AVL 트리의 높이는 O(logN)이다.

 

AVL 트리의 정확한 정의를 알아보자.

 

 

AVL 트리는 임의의 노드 x에 대해 x의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진 탐색 트리이다.

 

 

 

---

 

 

 

 

AVL 트리의 회전 연산

 

 

회전 연산의 경우

 

AVL트리는 회전 연산을 통해 균형을 유지할 수 있다고 했다.

 

이러한 회전 연산의 종류로는 크게 4가지가 있다.

 

LL-회전, RR-회전, LR-회전, RL-회전 연산을 사용한다.

 

 

각 경우가 무슨 말이냐 알기 위해서 균형 인수 라는 것에 대해 알아볼 필요가 있다.

 

균형 인수란 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이의 차 이다.

 

 

 

 

 

이러한 균형 인수의 절댓값이 만약 2를 넘긴다면, 이는 불균형적이라고 한다.

 

자 이제 우리는 LL, LR, RL, RR 회전의 경우를 이해할 수 있다.

 

 

LL회전은 균형인수가 +2가 되는 상황, 즉 왼쪽 서브 트리의 높이가 오른쪽 보다 2만큼 더 크다는 소리이다.

 

 

RR 회전은 -2가 되는 상황임을 자연스럽게 짐작할 수 있다.

즉, 오른쪽 트리의 높이가 왼쪽보다 2만큼 더 큰 상황이라는 것이다.

 

쉽게 생각 하자면 L은 +1이 되는 상황, R은 -1이 되는 상황으로 둘 수 있다.

 

그렇다면, LR회전과 RL 회전은 무엇인가?

 

 

트리가 위 예시처럼 서브트리도 왼쪽으로 치우쳐 진게 아닌 다른 경우도 있을 것이다.

 

그림을 한번 보자.

 

위에서 부터 내려오면서 이 트리 레벨을 2개씩 그룹지어 살펴보며 내려오면 이해하기 쉽다.

 

처음에 경우에는 +1의 경우이다. 왼쪽으로 치우쳐저 있으므로 L이다.

 

다음 레벨로 내려와서 살펴보면 오른쪽으로 치우쳐저 있다. 이는 R이다.

 

그래서 이 그림의 경우는 LR 회전의 경우라고 볼 수 있다.

 

 

 

RL 회전의 경우는 이와 반대되는 개념이므로 쉽게 생각할 수 있다.

 

 

 

 

 

 

 

회전 연산 함수

 

자, 이제 회전 연산 함수를 살펴보도록 하자.

 

기본적으로 두가지 연산으로 나뉜다.

rotateLeft(), rotateRight()

 

이 두개의 함수는 앞서 배웠던, LL, RR, LR, RL 회전에 있어 실질적으로 균형을 잡아준다.

 

이름만 보면 알 수 있듯이 실제 트리에서 오른쪽으로 회전, 왼쪽으로 회전 이라고 생각하면 이해하기 수월하다.

 

먼저 rotateRight 함수를 그림과 함께 코드로 살펴보자.

 

 

private Node rotateRight(Node n) {
	// Node x는 n의 왼쪽 노드이다. -> 실질적으로 이놈을 오른쪽으로 옮길 것이다.
	Node x = n.left;
    
    // 그렇게 하기 위해 x의 오른쪽 자식을 n의 왼쪽 자식으로 두고
    // 그래야 이진 트리 조건을 만족시키기 때문
  	n.left = x.right;
    
    // x의 오른쪽 자신은 n으로 둔다.(여기서 이동!)
    x.right = n;
    
    // n과 x의 높이 갱신
    n.height = tallerHeight(height(n.left), height(n.right) + 1;
    x.height = tallerHeight(height(x.left), height(x.right) + 1;
    
    return x;
}

 

 

 

rotateRight와 마찬가지로 rotateLeft도 비슷하게 진행된다.

 

기존의 n의 오른쪽 자식이었던 x를 n과 교체하여 왼쪽으로 회전시킨 것이다.

 

 

private Node roateLeft(Node n) {
	// x는 n의 오른쪽 자식이다. -> 실질적으로 n과 바꾸어 왼쪽 위로 올릴 녀석임
	Node x = n.right;
    
    // n의 오른쪽 자식은 x의 왼쪽 자식이 된다.
    // 이래야 이진 트리의 조건 만족
    n.right = x.left;
    
    // x의 왼쪽 자식은 n이 된다.(실질적 이동)
    x.left = n;
    
    // 높이 갱신
    n.height = tallerHeight(height(n.left), height(n.right)) + 1;
    x.height = tallerHeight(height(xleft), height(x.right)) + 1;
    return;
}

 

 

 

 

 

 

회전 수행

 

rotateLeft와 rotateRight의 함수를 이해하였다면, LL,RR, LR, RL 회전의 경우를 처리하는 것은 매우 쉽다.

 

• LL회전 : LL회전의 기준이 되는 맨 위 노드 rotateRight 수행
• RR회전 : RR회전의 기준이 되는 맨 위 노드 rotateLeft 수행
• LR회전 : 밑에서부터 rotateLeft, rotateRight 수행
• RL회전 : 밑에서부터 rotateRight, rotateLeft 수행

 

LL이나 RR일때는 앞글자 따서 반대로 생각하면서 외우고, LR과 RL은 그대로 생각하면서 외우는데 이때 밑에서 부터 수행한다고 생각하자.

 

LL이나 RR일때는 대충 알겠는데, LR과 RL은 살짝 헷갈릴 수 있다.

 

아래 그림처럼 n을 기준으로 먼저 rotateLeft를 실행하고 그다음으로 m을 기준으로 rotateRight를 수행하라는 뜻이다.

 

RL회전도 마찬가지로 생각할 수 있다.

 

 

즉, LR회전과 RL회전 경우의 구분은 위에서 부터 레벨 단위로 생각하면 쉽고,
실제 LR회전과 RL회전에서 함수 적용은 앞글자를 따고 밑에서 부터 rotateLeft, rotateRight 그리고 roateRight, rotateLeft를 적용하면 된다.

 

 

 

 

정확히 구분하려면,

 

LL회전은 균형인수가 +2이상이고 하위 노드도 +인 경우이며,

RR회전은 균형인수가 -2이하이고, 하위 노드는  -인 경우,

LR회전은 균형인수가 +2이상이고, 하위 노드는 반대로 -인 경우,

RL회전은 균형인수가 -2이하이고, 하위 노드는 반대로 +인 경우이다.

 

 

 

그냥 L은 균형인수 +, R은 균형인수 -일때 사용한다고 생각하자.

 

 

4종류의 회전의 공통점은 회전 후의 트리들이 모두 같다는 것.

그리고 각 회전 연산의 수행시간은 O(1)이라는 것이다.

 

 

 

 

---

 

 

 

AVL 트리의 삽입 연산

 

AVL 트리의 삽입 연산은 다음과 같은 과정을 따른다.

 

1. 이진 탐색 트리의 삽입과 동일하게 새 노드 삽입

 

2. 새 노드로부터 루트로 거슬러 올라가며 각 노드의 서브트리 높이 차이를 갱신

 

이때 가장 먼저 불균형이 발생한 노드를 발견하면, 이 노드를 기준으로 새 노드가 어디에 삽입되었는지에 따라 적절한 회전 연산을 수행한다.

 

 

AVL 트리를 위한 Node 클래스와 삽입 메서드를 살펴보자.

 

// AVL 트리를 위한 Node 클래스
public class Node {
	// Key, Value값과 왼쪽, 오른쪽 자식 노드 선언
	private Key id;
    private Value name;
    private int height;
    private Node left, right;
    public Node(Key newID, Value newName, int newHt) {
    	id = newID;
        name = newName;
        height = newHt;
        left = right = null;
    }
}

 

 

// 삽입 함수 호출
public void put(Key k, Value v) { root = put(root, k, v); }


private Node put(Node n, Key k, Value v) {

	// n이 null이라면 이는 root노드가 없는 것이므로 새로운 노드 반환, 높이는 1
    // 또는 삽입될 노드를 말함. 맨 마지막 이파리에 도달한 경우 생성
    // 이 경우, 리턴되므로 밑에 키 비교 부분은 넘어감
	if (n == null) return new Node(k, v, 1);
    
    // 키와 n를 비교
    int t = k.compareTo(n.id);
    
    // 만약 t가 0보다 작다면 k가 노드 n의 키보다 작은 것이므로 n의 왼쪽 자식에 해당 k키를 가진 노드 삽입
    if (t < 0) n.left = put(n.left, k, v);
    
    // 만약에 t가 0보다 크다면, k가 노드 n의 키보다 크므로, n의 오른쪽 자식에 삽입
    else if (t > 0) n.right = put(n.right, k, v);
    
    // t가 0인 경우인데, 이는 k가 이미 트리에 있는 경우이므로 value만 갱신
    else {
    	n.name = v;
        return n;
    }
    
    // n의 높이 갱신
    n.height = tallerHeight(height(n.left), height(n.right)) + 1;
    
    // 노드 n의 균형 점검 및 불균형을 바로 잡음. 여기서 각 회전 연산이 일어남
    return balance(n);
}

 

 

코드에 대한 주석을 읽으면 쉽게 이해할 수 있을 것이다.

 

사실 상 제일 중요한 balance 함수에 대해 알아야 한다.

 

바로 여기서 LL, RR, LR, RL회전이 일어나기 때문이다.

 

private Node balance(Node n) {
	// 노드 n의 왼쪽 서브트리가 높아서 불균형이 발생함 -> 즉, 2 이상인 경우
	if (bf(n) > 1) {
    
    	// n의 왼쪽 자식 노드의 오른쪽 서브트리가 높은 경우 -> 즉, -1 이하인 경우
    	// 이 조건문이 실행된다면 LR 회전임
    	if (bf(n.left) < 0) {
        	n.left = rotateLeft(n.left);
       	}
        // 이것만 실행된다면 LL회전
        n = rotateRight(n);
    }
    // 노드 n의 오른쪽 서브트리가 높아서 불균형이 발생함 -> 즉, -2 이하인 경우
    // 즉, rotateLeft 필요
    else if (bf(n) < -1) {
    
    	// n의 오른쪽 자식 노드의 왼쪽 서브트리가 높은 경우 -> 즉, 1 이상인 경우
        // 이 조건문이 실행된다면 RL 회전임
        // 즉, rotateRight가 필요
    	if (bf(n.right) > 0) {
        	n.right = rotateRight(n.right);
        }
        
        // 이것만 실행된다면 RR회전
        n = rotateLeft(n);
    }
    
    return n;
}



// 아래는 균형인수를 반환하는 bf 메서드와 다른 유틸리티 메서드
private int bf(Node n) {
	return height(n.left) - hegiht(n.right);
}

private int height(Node n) {
	if (n == null) return 0;
    return n.height;
}

private int tallerHeight(int x, int y) {
	if (x>y) return x;
    else return y;
}

 

 

 

---

 

 

AVL 트리의 삭제 연산

 

마지막으로 삭제 연산이다.

 

삭제 연산은 다음과 같은 단계를 따른다.

 

1. 이진 탐색 트리에서와 동일한 삭제 연산을 수행한다.

 

2. 삭제된 노드로부터 루트 방향으로 거슬러 올라가며 불균형이 발생한 경우 적절한 회전 연산을 수행한다.

 

이 때, 회전 연산 수행 후에 부모에서 불균형이 발생할 수 있고, 이러한 일이 반복되어 루트에서 회전 연산을 수행하는 경우도 발생한다.

 

 

삽입이건, 삭제건 결국 이진 탐색 트리이기 때문에 이진 탐색 트리에 대한 이해가 굉장히 필요하다.

 

 

 

삭제연산의 구현은 삭제 후, 불균형이 발생하면 반대쪽에 삽입이 이루어져 불균형이 발생한 것으로 취급한다.

 

 

다음 예제를 보자.

 

출처 : 교수님 강의 자료

 

 

40을 삭제하려고 하는 경우, 노드 30에서 불균형이 발생하게 된다.

이 경우 LR 회전을 시켜야 하는 상황이 된다.

 

즉, rotateLeft, rotateRight를 밑에서 부터 수행한다.

그러면 20의 왼쪽 자식이 10이 되고, 20의 오른쪽 자식이 30이 된다.

 

 

출처 : 교수님 강의 자료

 

그러면 위와 같은 꼴이 될 텐데

 

왼쪽 트리는 LR이 수행된 이후의 트리이다.

 

여기서 RL을 이제 수행해야하는데(이유는 균형인수가 위에서 부터 -2이하, 그 밑의 노드는 +이므로)

 

위와 같이 RL 회전을 수행하면 오른쪽 그림과 같은 형태가 된다.

 

 

 

 

---

 

 

수행 시간

 

AVL 트리에서의 탐색, 삽입, 삭제 연산은 공통적으로 루트부터 탐색을 시작하여 최악의 경우에 이파리까지 내려가고, 삽입이나 삭제 연산은 다시 루트까지 거슬러 올라가야한다.

 

이러한 특징 때문에 제일 처음 말했던 것처럼 탐색, 삽입, 삭제 연산의 수행 시간은 각각 AVL 트리의 높이에 비례한다고 했던 것이다. : O(logN)

 

트리를 1층 내려갈 때는 순환 호출하며, 1층을 올라갈 때, 불균형이 발생하면 적절한 회전 연산을 수행한다. 각각은 O(1)의 시간이 소요된다.

 

 

 

 

다양한 실험 결과에 따르면 AVL 트리는 거의 정렬된 데이터를 삽입한 후에 랜덤 순서로 데이터를 탐색하는 경우, 가장 좋은 성능을 보인다.

 

반대로 이진 탐색 트리는 랜덤 순서의 데이터를 삽입한 후에 랜덤 순서로 데이터를 탐색하는 경우 가장 좋은 성능을 보인다.