详解Java数据结构之平衡二叉树

什么是平衡二叉树？

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1，这样可以保证在最坏情况下，查找、插入、删除等操作的时间复杂度都是O(log n)。

平衡二叉树的基本性质

1. 左子树和右子树的高度差不超过1。

2. 平衡二叉树的左右子树也是平衡二叉树。

如何实现？

平衡二叉树的实现有多种，其中比较常见的是AVL树和红黑树。

AVL树

AVL树是一种严格平衡的二叉树，它的平衡条件是：对于AVL树上的任意结点，它的左子树和右子树的高度差不超过1。

红黑树

红黑树是一种非严格平衡的二叉树，它的平衡条件是：红黑树上的任意结点，到它的叶子节点的路径上，黑色结点数目相同。红黑树通过旋转和变色来保证平衡。

平衡二叉树的应用

平衡二叉树常用于需要高效查找、插入、删除操作的场景，比如数据库索引、缓存等。

示例如何定义一棵平衡二叉树

以下是用Java代码定义一棵基于AVL树的平衡二叉树：

public class AVLTree<T extends Comparable<T>> {
    private static class AVLNode<T> {
        T element;
        AVLNode<T> left;
        AVLNode<T> right;
        int height;
        AVLNode(T theElement, AVLNode<T> lt, AVLNode<T> rt) {
            element = theElement;
            left = lt;
            right = rt;
            height = 0;
        }
    }

    private AVLNode<T> root;

    public AVLTree() {
        root = null;
    }

    public void insert(T x) {
        root = insert(x, root);
    }

    private AVLNode<T> insert(T x, AVLNode<T> t) {
        if (t == null) {
            return new AVLNode<>(x, null, null);
        }

        int compareResult = x.compareTo(t.element);

        if (compareResult < 0) {
            t.left = insert(x, t.left);
            if (height(t.left) - height(t.right) == 2) {
                if (x.compareTo(t.left.element) < 0) {
                    t = rotateWithLeftChild(t);
                } else {
                    t = doubleWithLeftChild(t);
                }
            }
        } else if (compareResult > 0) {
            t.right = insert(x, t.right);
            if (height(t.right) - height(t.left) == 2) {
                if (x.compareTo(t.right.element) > 0) {
                    t = rotateWithRightChild(t);
                } else {
                    t = doubleWithRightChild(t);
                }
            }
        } else {
            // element is already in the tree, do nothing
        }
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        return t;
    }

    private int height(AVLNode<T> t) {
        return t == null ? -1 : t.height;
    }

    private AVLNode<T> rotateWithLeftChild(AVLNode<T> k2) {
        AVLNode<T> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        k1.height = Math.max(height(k1.left), k2.height) + 1;
        return k1;
    }

    private AVLNode<T> rotateWithRightChild(AVLNode<T> k1) {
        AVLNode<T> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
        k2.height = Math.max(height(k2.right), k1.height) + 1;
        return k2;
    }

    private AVLNode<T> doubleWithLeftChild(AVLNode<T> k3) {
        k3.left = rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }

    private AVLNode<T> doubleWithRightChild(AVLNode<T> k1) {
        k1.right = rotateWithLeftChild(k1.right);
        return rotateWithRightChild(k1);
    }

    public void remove(T x) {
        root = remove(x, root);
    }

    private AVLNode<T> remove(T x, AVLNode<T> t) {
        if (t == null) {
            return t;
        }

        int compareResult = x.compareTo(t.element);

        if (compareResult < 0) {
            t.left = remove(x, t.left);
            if (height(t.right) - height(t.left) == 2) {
                if (height(t.right.right) >= height(t.right.left)) {
                    t = rotateWithRightChild(t);
                } else {
                    t = doubleWithRightChild(t);
                }
            }
        } else if (compareResult > 0) {
            t.right = remove(x, t.right);
            if (height(t.left) - height(t.right) == 2) {
                if (height(t.left.left) >= height(t.left.right)) {
                    t = rotateWithLeftChild(t);
                } else {
                    t = doubleWithLeftChild(t);
                }
            }
        } else if (t.left != null && t.right != null) {
            t.element = findMin(t.right).element;
            t.right = remove(t.element, t.right);
            if (height(t.left) - height(t.right) == 2) {
                if (height(t.left.left) >= height(t.left.right)) {
                    t = rotateWithLeftChild(t);
                } else {
                    t = doubleWithLeftChild(t);
                }
            }
        } else {
            t = (t.left != null) ? t.left : t.right;
        }

        if (t != null) {
            t.height = Math.max(height(t.left), height(t.right)) + 1;
        }
        return t;
    }

    private AVLNode<T> findMin(AVLNode<T> t) {
        if (t == null) {
            return null;
        }
        if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }
}

示例说明

假设我们有以下整数序列需要插入到一棵基于AVL树的平衡二叉树中：1, 2, 3, 4, 5, 6, 7, 8。

AVLTree<Integer> avlTree = new AVLTree<>();
avlTree.insert(1);
avlTree.insert(2);
avlTree.insert(3);
avlTree.insert(4);
avlTree.insert(5);
avlTree.insert(6);
avlTree.insert(7);
avlTree.insert(8);

在插入完上述整数序列后，我们可以使用以下代码检查平衡二叉树的平衡性：

private static <T extends Comparable<T>> boolean checkBalance(AVLTree.AVLNode<T> t) {
    if (t == null) {
        return true;
    }
    int leftHeight = height(t.left);
    int rightHeight = height(t.right);
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    return checkBalance(t.left) && checkBalance(t.right);
}

private static <T extends Comparable<T>> int height(AVLTree.AVLNode<T> t) {
    return t == null ? -1 : t.height;
}

boolean isBalanced = checkBalance(avlTree.root);

如果isBalanced等于true，则说明平衡二叉树插入所有整数后仍然平衡。

接下来，我们尝试从平衡二叉树中删除元素8：

avlTree.remove(8);

然后，我们可以使用以下代码检查AVL树的平衡性：

boolean isBalanced = checkBalance(avlTree.root);

如果isBalanced等于true，则说明AVL树删除元素8后仍然平衡。