数据结构-红黑树

Red Black Tree

性质

1. 每个结点可红可黑。
2. 根结点是黑色。
3. 叶结点（null）是黑色。
4. 红色结点的孩子是黑色。
5. 任意结点到叶结点的路径都包含相同数量的黑色结点。

6. 红黑树不是完美平衡二叉查找树，左右子树高度差可能大于1。

自平衡

• 左旋：右孩子V变为当前结点P的父结点，当前结点P变为右孩子V的左孩子，右孩子V的左子树R变为当前结点的右子树。

• 右旋：左孩子F变为当前结点P的父结点，当前结点P变为左孩子F的右孩子，左孩子F的右子树K变为当前结点的左子树。

• 变色：结点黑红互转。

插入

• 空树：

30张图带你彻底理解红黑树