二叉查找树介绍

image.png

上面这张图就是一个二叉查找树。二叉查找树有如下几条特性

• （1）.左子树上所有结点的值均小于或等于它的根结点的值。
• （2）.右子树上所有结点的值均大于或等于它的根结点的值。
• （3）.左、右子树也分别为二叉排序树

查找的时候就根据以上特性，查找的最大长度就是树的高度。
为了避免形成一条直线，需要调整树的形态，就有了红黑树。

红黑树

红黑树其实就是一种自平衡的二叉查找树。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

• 性质1. 节点是红色或黑色。
• 性质2. 根节点是黑色。
• 性质3 每个叶节点（NIL节点，空节点）是黑色的。
• 性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

• 性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

  
  image.png

那么红黑树是怎么维护这个二叉查找树的自平衡性的呢？

红黑树通过“变色”和“旋转”来维护红黑树的规则，变色就是让黑的变成红的，红的变成黑的，旋转又分为“左旋转”和“右旋转”。