[자료구조] AVL 트리

AVL 트리

 

• 노트가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리
• 각 노드의 BF (Balance Factor : 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이)를 [-1, 0, 1]만 가지게 하여 균형 유지 
• 균형이 깨진 경우 BF가 +/- 면 왼/오른쪽 서브 트리에 이상
• 회전 연산 : 단순 회전(LL, RR), 이중 회전(LR, RL)

 

 

1. LL (Left-Left)

 

• 회전 1회
• 오른쪽 방향으로 회전

 

 

2. RR (Right-Right)

 

• 회전 1회
• 왼쪽 방향으로 회전

 

 

3. LR (Left-Right)

 

• 회전 2회
• RR 회전 후 LL 회전

 

 

4. RL (Right-Left)

 

• 회전 2회
• LL 회전 후 RR 회전

 

 

public Node rightRotate(Node node) {
        Node lNode = node.left;

        node.left = lNode.right;
        lNode.right = node;

        node.height = Math.max(height(node.left), height(node.right)) + 1;
        lNode.height = Math.max(height(lNode.left), height(lNode.right)) + 1;

        return lNode;
}

 public Node leftRotate(Node node) {
        Node rNode = node.right;

        node.right = rNode.left;
        rNode.left = node;

        node.height = Math.max(height(node.left), height(node.right)) + 1;
        rNode.height = Math.max(height(rNode.left), height(rNode.right)) + 1;

        return rNode;
}

public Node lrRotate(Node node) {
    node.left = leftRotate(node.left);
    return rightRotate(node);
}

public Node rlRotate(Node node) {
    node.right = rightRotate(node.right);
    return leftRotate(node);
}

public int getBalance(Node node) {
    if (node == null) {
        return 0;
    }

    return height(node.left) - height(node.right);
}

 

public Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key, null, null);
        }

        if (key < node.key) {
            node.left = insert(node.left, key);
        } else {
            node.right = insert(node.right, key);
        }

        node.height = Math.max(height(node.left), height(node.right)) + 1;

        int balance = getBalance(node);
        // LL
        if (balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }

        // RR
        if (balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }

        // LR
        if (balance > 1 && key > node.left.key) {
            return lrRotate(node);
        }

        // RL
        if (balance < -1 && key < node.right.key) {
            return rlRotate(node);
        }

        return node;
}

 

public Node delete(Node node, int key) {
        if (node == null) {
            return null;
        }

        if (key < node.key) {
            node.left = delete(node.left, key);
        } else if (key > node.key) {
            node.right = delete(node.right, key);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                Node predecessor = node;
                Node successor = node.left;

                while (successor.right != null) {
                    predecessor = successor;
                    successor = successor.right;
                }

                predecessor.right = successor.left;
                node.key = successor.key;
            }
        }

        node.height = Math.max(height(node.left), height(node.right)) + 1;

        int balance = getBalance(node);
        // LL
        if (balance > 1 && getBalance(node.left) > 0) {
            return rightRotate(node);
        }

        // RR
        if (balance < -1 && getBalance(node.right) < 0) {
            return leftRotate(node);
        }

        // LR
        if (balance > 1 && getBalance(node.left) < 0) {
            return lrRotate(node);
        }

        // RL
        if (balance < - 1 && getBalance(node.right) > 0) {
            return rlRotate(node);
        }

        return node;
}