[JAVA자료구조] AVL트리의 구현

AVL 노드 클래스

class AVLNode {
    int key;
    AVLNode left, right;
    int height;

    AVLNode(int key) {
        this.key = key;
        this.left = null;
        this.right = null;
        this.height = 1; // 노드의 높이
    }
}

 

AVL 트리 클래스

 

class AVLTree {
    private AVLNode root;

    // 루트 노드 반환
    public AVLNode getRoot() {
        return root;
    }

    // 노드의 높이 가져오기
    private int getHeight(AVLNode node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    // 노드의 균형 인수 계산
    private int getBalance(AVLNode node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    // 오른쪽 회전
    private AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;

        // 회전 수행
        x.right = y;
        y.left = T2;

        // 높이 업데이트
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));

        return x;
    }

    // 왼쪽 회전
    private AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;

        // 회전 수행
        y.left = x;
        x.right = T2;

        // 높이 업데이트
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));

        return y;
    }

    // 좌측-우측 회전
    private AVLNode leftRightRotate(AVLNode node) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 우측-좌측 회전
    private AVLNode rightLeftRotate(AVLNode node) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    // 트리에 노드 삽입
    public AVLNode insert(AVLNode node, int key) {
        // 일반 이진 탐색 트리 삽입
        if (node == null) {
            return new AVLNode(key);
        }

        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        } else {
            return node; // 중복된 키는 허용하지 않음
        }

        // 높이 업데이트
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        // 균형 확인 및 조정
        int balance = getBalance(node);

        // 좌측-좌측 케이스
        if (balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }

        // 좌측-우측 케이스
        if (balance > 1 && key > node.left.key) {
            return leftRightRotate(node);
        }

        // 우측-우측 케이스
        if (balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }

        // 우측-좌측 케이스
        if (balance < -1 && key < node.right.key) {
            return rightLeftRotate(node);
        }

        return node;
    }

    // 트리에 노드 삽입을 시작하는 메서드
    public void insert(int key) {
        root = insert(root, key);
    }
}