数据结构--二叉查找树与红黑树

二叉查找树

对于树中每个节点 X，左子树所有值小于 X，右子树所有值大于 X。平均深度 O(log n)。

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
    private BinaryNode<AnyType> root;

    private boolean contains(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) return false;
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) return contains(x, t.left);
        else if (compareResult > 0) return contains(x, t.right);
        else return true;
    }

    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) return new BinaryNode<>(x, null, null);
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) t.left = insert(x, t.left);
        else if (compareResult > 0) t.right = insert(x, t.right);
        return t;
    }
}

红黑树

自平衡的二叉查找树，解决 BST 极端情况下变为线性链表的问题。

性质

1. 根节点是黑色
2. 每个叶子节点都是黑色空节点（NIL）
3. 每个红色节点的两个子节点都是黑色（不能有连续红色节点）
4. 从任一节点到其每个叶子的所有路径包含相同数目的黑色节点（黑高相等）

插入调整

1. 调整右倾红色：左旋 + 变色
2. 左右均为红色：父变红，子变黑
3. 连续红色：右旋 + 变色