[자료구조] 트리, AVL 트리

AVL Tree (AVL은 발명자 세명의 이름에서 따왔다)

자가 균형 이진 탐색 트리.

이진 탐색 트리에서, 노드들이 삽입시 한쪽으로 편향되면 결국 탐색에서 O(N)의 시간이 걸리게 된다.

• * 그림 : 편향트리.

---

이진 탐색 트리의 편향트리를 극복하기 위해 재구성(회전, Rotate)을 통해 트리를 균형있게 만든다.

AVL 트리는 다음과 같은 특징을 가진다.

1. 이진 탐색 트리(BST)의 속성을 가진다.
2. 왼쪽, 오른쪽 서브 트리의 높이차이가 최대 1이다.
3. 삽입, 삭제 등 어떤 시점에서 높이 차이가 1보다 커지면 회전(Ratation)을 통해 균형을 맞춰 높이를 1로 맞춘다.
4. AVL 트리는 높이를 logN으로 유지하기 떄문에 삽입, 검색 ,삭제의 시간 복잡도는 O(log N) 이다.

AVL 트리는 균형이 무너졌는지에 대해 판단할 떄 Balance Factor (BF) 라는 것을 이용합니다.

• AVL 트리는 모든 노드의 BF가 -1, 0, 1중 하나여야 합니다. 이를 벗어나면 균형이 깨진것이고, 회전이 필요합니다.

Banlace Factor(BF)

• 균형이 무너졌는지 확인하는것.

  > BF(K) = height(left(k)) - height(right(k))

• k의 왼쪽 서브트리 높이 - k의 오른쪽 서브트리 높이

  > BF가 1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한 단계 높은것.  
  > BF가 0이면 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같은것.  
  > BF가 -1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한 단계 낮은것.

• 즉 BF값이 범위를 벗어났을 떄 양수이면 왼쪽 서브트리가 더 높이가 높은것

• 음수이면 오른쪽 서브트리가 더 높이가 높은것

  • ex ) -2, -3 이면 음수이므로 오른쪽 서브트리의 높이가 더높은것
  • ex) 2, 3 이면 양수이므로 왼쪽 서브트리의 높이가 더 높은것

• 

• 그림 : 트리의 높이

• 

• 그림 : 각 트리의 높이에 따른 BF(K) 값

  • 10 : 왼쪽 서브트리 높이 1, 오른쪽 서브트리 높이 1 . 1-1 = 0
  • 30 : 자식이 없으므로 높이 0
  • 20 : 왼쪽 서브트리 높이 2 오른쪽 서브트리 높이 1. 2-1 = 1
  • 50 : 왼쪽 서브트리 높이 3 오른쪽 서브트리 높이 2. 3-2 = 1
  • 70 : 왼쪽 서브트 리 높이 0 오른쪽 서브트리 높이 1. 0 - 1 = -1

회전(Rotation)

AVL 트리는 균형이 무너지면(BF(K)값이 0, -1, 1 이 아니면 ) 회전을 하여 균형을 맞춘다.

이때 사용하는것이 회전이다.

검색 및 순회 연산은 BF를 변경하지 않지만 삽입 및 삭제 연산에서는 BF가 변경될 수 있다.

불균형 노드를 기준으로 서브트리의 위치를 변경하는 작업이 Rotation이다

삽입 삭제 시 노드들의 배열에 따라 4가지 (LL, LR, RR, RL) 불균형이 발생할 수 있으며,
각 상황마다 회전하는 방향이 다르다

• 좌회전과 우회전을 먼저 봅시다.

좌회전

• 
• 균형이 깨진 노드 z
• z노드를 오른쪽 자식노드의 왼쪽으로 이동 -
• z 노드의 오른쪽 자식노드 y가 새 부모 노드가 됨.

우회전

• 
• 균형이 깨진 노드 z
• z노드를 z의 왼쪽 자식노드인 y노드의 오른쪽 자식으로 이동
• z노드의 왼쪽 자식노드인 y가 새 부모 노드가 됨.

LL, RR ,LR , RR 을 보기전에 다시한번 기억해둬야 하는 내용

BF가 1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한 단계 높은것.
BF가 0이면 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같은것.
BF가 -1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한 단계 낮은것.

• 즉 BF값이 범위를 벗어났을 떄 양수이면 왼쪽 서브트리가 더 높이가 높은것
• 음수이면 오른쪽 서브트리가 더 높이가 높은것
  • ex ) -2, -3 이면 음수이므로 오른쪽 서브트리의 높이가 더높은것
  • ex) 2, 3 이면 양수이므로 왼쪽 서브트리의 높이가 더 높은것

LL 회전 (Left Left) -> 우회전한다.

• BF값이 양수로 범위를 벗어난 경우 (2)
• 왼쪽 서브트리의 높이가 오른쪽 서브트리의 높이보다 더 높은경우
• BF값을 벗어난 노드를 z,
• z의 아들을 y
• y의 아들을 x (x는 z의 손자)

LL 회전은 y가 왼쪽 자식노드이고, x가 왼쪽 자식노드일 경우 회전한다

• Right Rotation (우회전)
• 
• 해당 노드인 z를 기준으로 우회전 하면 불균형이 해소된다.

1. y노드의 오른쪽 자식 노드를 z로 변경
2. z노드 왼쪽 자식 노드를 y 노드의 오른쪽 서브트리로 변경
3. y가 새로운 루트 노드

RR 회전(Right Right) -> 좌회전한다

• BF값이 음수로 범위를 벗어난 경우( -2)
• 오른쪽 서브트리의 높이가 왼쪽 서브트리의 높이보다 더 높은 경우
• BF 값을 벗어난 노드를 z
• z의 아들을 y
• y의 아들을 x (x는 z의 손자)

RR 회전은 y가 z의 오른쪽 자식이고, x가 오른쪽 자식 노드일경우 회전한다

• Left Rotation(좌회전)
• 
• 해당 노드인 z를 기준으로 좌회전하면 불균형이 해소된다
• 1. y노드의 왼쪽 자식 노드를 z 노드로 변경
• 2. z노드 오른쪽 자식 노드를 y노드 왼쪽 서브트리로 변경
• 3. y가 새로운 루트노드

LR (Left Right) - 2번의 Rotation. left -> right 순으로 두번 수행한다

• BF 값이 양수로 범위를 벗어남
• BF의 왼쪽 자식노드가 오른쪽 자식 노드를 갖고 있는 경우
• BF 값을 벗어난 노드를 z
• z의 아들을 y
• y의 아들을 x (x는 z의 손자)

LR 회전은 y가 z의 왼쪽 자식이고 x가 y의 오른쪽 자식 노드일경우 left -> right 순으로 2번 회전한다

• 
• 1. 왼쪽 자식 노드인 y를 기준으로 좌회전
• 2. 본인인 z 기준으로 우회전

y = z.left;
y = rotateLeft(y);
z = rotateRight(z);

RL(RIght Left )- 2번의 Rotation. right left 순으로 두번 수행한다

• BF 값이 음수로 범위를 벗어남
• BF의 오른쪽 자식 노드가 왼쪽 자식 노드를 갖고 있는 경우
• BF 값을 벗어난 노드를 z
• z의 아들을 y
• y의 아들을 x (x는 z의 손자)

RL 회전은 y가 z의 오른쪽 자식이고 x가 의 왼쪽 자식일떄 right -> left 순으로 두번 회전한다.

• 

1. 오른쪽 자식 노드인 y를 기준으로 우회전
2. 본인인 z 기준으로 좌회전

y = z.right;
y = rotateRight(y);
z = rotateLeft(z);

자바 소스코드 구현 - 접기/펼치기

@Getter @Setter
@NoArgsConstructor @AllArgsConstructor
public class Node {

    private int key;
    private int height;
    private Node left;
    private Node right;

    public Node(int key) {
        this.key = key;
    }
}

package tree;

/**
 * @author : ysk
 */
public class AVLTree {

    private Node root;

    private void updateHeight(Node n) {
        n.setHeight(1 + Math.max(height(n.getLeft()), height(n.getRight())));
    }

    private int height(Node n) {
        return n == null ? -1 : n.getHeight();
    }

    private int getBalanceFactor(Node n) {
        return n == null ? 0 : height(n.getRight()) - height(n.getLeft());
    }

    private Node rotateLeft(Node z) { // z 본인, 할아버지. y 본인의 오른쪽노드. x  손주 y의 왼쪽 노드
        Node y = z.getRight();
        Node x = y.getLeft();

        // y의 왼쪽 자식 노드를 z로 지정
        y.setLeft(z);
        // z의 오른쪽 자식 노드를 x로 지정
        z.setRight(x);

        updateHeight(z);
        updateHeight(y);

        return y; // 새로운 루트 노드 반환
    }

    private Node rotateRight(Node z) { // z 본인, 할아버지. y 본인의 왼쪽노드 . x  손주 y의 왼쪽 노드
        Node y = z.getLeft();
        Node x = y.getRight();

        y.setRight(z);
        z.setLeft(x);

        updateHeight(z);
        updateHeight(y);

        return y; // 새로운 루트노드
    }

    private Node insert(int key) {

        Node newNode = new Node(key);

        if (root == null) {
            root = newNode;
            return newNode;
        }

        Node rootNode = root;

        while (true) {
            if (key < rootNode.getKey()) {
                if (rootNode.getLeft() != null) {
                    rootNode = rootNode.getLeft();
                } else {
                    rootNode.setLeft(newNode);
                    return newNode;
                }
            } else if(key > rootNode.getKey()) {
                if (rootNode.getRight() != null) {
                    rootNode = rootNode.getRight();
                } else {
                    rootNode.setRight(newNode);
                    return newNode;
                }
            } else {
                throw new IllegalArgumentException("has Contain, value : " + key);
            }
        }

    }

    public void insertNode(Integer... values) {
        for (Integer value : values) {
            insertNode(value);
        }
    }

    public Node insertNode(int key) {

        Node insertNode = insert(key);
        updateHeight(insertNode);
        return rebalance(insertNode);
    }

    private Node rebalance(Node node) {

        int balanceFactor = this.getBalanceFactor(node);

        if (balanceFactor < -1) { // RR : 현재 노드 기준으로 오른쪽 서브트리가 더 커서 발란스가 작아진경우
            if (getBalanceFactor(node.getLeft()) <= 0) {
                node = rotateRight(node);
            } else { // LR
              node.setLeft(rotateLeft(node.getLeft()));
              node = rotateRight(node);
            }
        }

        if (balanceFactor > 1) { // LL
            if (getBalanceFactor(node.getRight()) > 0) { // LL
                node = rotateLeft(node);
            } else { // RL
                node.setRight(rotateRight(node.getRight()));
                node = rotateLeft(node);
            }
        }

        return node;
    }

    public Node searchNode(int key) {
        Node node = root;

        while(node != null) {
            if (key == node.getKey()) {
                return node;
            } else if (key < node.getKey()) {
                node = node.getLeft();
            } else {
                node = node.getRight();
            }
        }
        return null;
    }

    public Node getRoot() {
        return this.root;
    }

    public void inOrder(Node node) {
        if (node != null) {
            if (node.getLeft() != null) {
                inOrder(node.getLeft());
            }
            System.out.print(node.getKey() + ", ");
            if (node.getRight() != null) {
                inOrder(node.getRight());
            }
        }

    }

    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        avlTree.insertNode(3, 5, 4, 7, 9, 11, 15, 14, 10, 2, 99, 98, 94, 90, 18, 19, 23, 25, 53, 70, 88, 46, 64, 72);
        Node root = avlTree.getRoot();
        avlTree.inOrder(root);
    }
}

참고

https://yoongrammer.tistory.com/72

https://galid1.tistory.com/176

https://www.happycoders.eu/algorithms/avl-tree-java/

https://www.baeldung.com/java-avl-trees

https://www.zerocho.com/category/Algorithm/post/583cacb648a7340018ac73f1