AVLTree 实现

AVLTree.java

public class AVLTree {
    public static class Node {
        int data;
        Node leftChild;
        Node rightChild;
        int height;

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

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

    private static int reCalcHeight(Node p) {
        return Math.max(getHeight(p.leftChild), getHeight(p.rightChild)) + 1;
    }

    public static void printTree(Node root) {
        System.out.println(root.data);
        if (root.leftChild != null) {
            System.out.print("left: ");
            printTree(root.leftChild);
        }

        if (root.rightChild != null) {
            System.out.print("right: ");
            printTree(root.rightChild);
        }

    }

    public static Node insert(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }

        if (data <= root.data) { // 插入到左子树
            root.leftChild = insert(root.leftChild, data);
            // 平衡调整
            if (getHeight(root.leftChild) - getHeight(root.rightChild) > 1) {
                if (data <= root.leftChild.data) {  // 插入节点在失衡节点的左子树的左边
                     root = LLRotate(root);
                } else { // 插入节点在失衡节点的左子树的右边
                    root = LRRotate(root);
                }
            }
        } else { // 插入到右子树
            root.rightChild = insert(root.rightChild, data);
            if (getHeight(root.rightChild) - getHeight(root.leftChild) > 1) {
                if (data <= root.rightChild.data) { // 插入节点在失衡节点右子树的左边
                    root = RLRotate(root);
                } else { // 插入节点在失衡节点右子树的右边
                    root = RRRotate(root);
                }
            }
        }

        root.height = reCalcHeight(root);
        return root;
    }


    public static Node LRRotate(Node p) {
        System.out.println("LR旋转");
        p.leftChild = RRRotate(p.leftChild);
        return LLRotate(p);
    }

    public static Node RLRotate(Node p) {
        System.out.println("RL旋转");
        p.rightChild = LLRotate(p.rightChild);
        return RRRotate(p);
    }


    /**
     * LL旋转
     *
     *         30                 20
     *        / \               /   \
     *       20 40            10    30
     *      / \      --->    /    /   \
     *     10  25           5    25   40
     *    /
     *   5
     * @param p 失衡节点
     * @return 旋转后，新的根节点
     */
    public static Node LLRotate(Node p) {
        System.out.println("LL旋转");
        Node lSubtree = p.leftChild;
        p.leftChild = lSubtree.rightChild;
        lSubtree.rightChild = p;

        p.height = reCalcHeight(p);
        lSubtree.height = reCalcHeight(lSubtree);
        return lSubtree;
    }


    /**
     * RR旋转
     *      20                          30
     *     /  \                        /  \
     *    10  30        --->          20  40
     *       /  \                    /  \   \
     *      25  40                  10  25   50
     *            \
     *            50
     * @param p 失衡节点
     * @return  旋转后，新的根节点
     */
    public static Node RRRotate(Node p) {
        System.out.println("RR旋转");
        Node rSubtree = p.rightChild;
        p.rightChild = rSubtree.leftChild;
        rSubtree.leftChild = p;

        p.height = reCalcHeight(p);
        rSubtree.height = reCalcHeight(rSubtree);
        return rSubtree;
    }


    public static void main(String[] argv) {
        Node root = null;
        root = insert(root, 30);
        root = insert(root, 20);
        root = insert(root, 40);
        root = insert(root, 10);
        root = insert(root, 25);
        printTree(root);
        System.out.println("------------------------");
        root = insert(root, 5);
        printTree(root);
    }
}