1.红黑树的由来

红黑树是一种平衡二叉树，我们直到红黑树是由二叉查找树演变而来的，

1， 左子树上所有的节点的值均小于或等于他的根节点的值

2， 右子数上所有的节点的值均大于或等于他的根节点的值

3， 左右子树也一定分别为二叉排序树

二叉查找树

但是有时候会出现这样的情况：

image.png

此二叉查找树的效率和线性查找差不多，效率十分低下，由此引出了红黑树，它是一种平衡二叉查找树。

2.红黑树

1.红黑树的定义和性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

从性质5又可以推出：

性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

2.红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。

右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。

变色：结点的颜色由红变黑或由黑变红。

image.png