那些年面试官问你的红黑树----->(浅谈)

在了解红黑树之前，先要了解二叉树，又叫二叉查找树、二叉搜索树、二叉排序树。二叉树顾名思义: 是一种每个节点最多有两个子节点的树，同时遵循 左节点的值<父节点的值<右节点的值 这样的规律。

二叉树有如下几个特点：

• 节点的左子节点小于节点本身

• 节点的右子节点大于节点本身

• 左右节点同样为二叉搜索树

下图就是一棵典型的二叉树：

它是一种查找次数小于等于树高的数据结构。如图中树有4层，即树高为4，当我们需要查找8时，经过的路线是这样的：

1、8<9，往左查找

2、8>5，往右查找

3、8>7，往右查找

4、8=8，找到结果

总共查找4次，等于树高。这棵树不管怎么找，查找次数总是小于等于树高。

二叉树的插入同样遵循上述规则，会一步一步对比，从而找到插入的位置，可以想象上图中的8不存在，而是需要插入一个8，结果与上述路线一致。

二叉树的删除会涉及到无子节点和有子节点两种情况，无子节点直接删除即可，有子节点会需要用左边最大值或右边最小值替换当前删除节点，具体不细聊。

当二叉树插入数值不均衡时，会出现树结构的变形与查找性能的损耗，比如现在二叉树有8，9，12三个值，然后需要插入7，6，5，4，3这五个值时，产生的结构如下图所示:

树高会不合理的增高，查找效率也无法得到保证。红黑树就是为了解决这种情况而诞生的。

红黑树又称为自平衡二叉树，它符合二叉树的规则同时比它的规则更加的复杂，具体规则如下：

1、所有节点都是红色或黑色

2、根节点为黑色

3、所有叶子都是黑色(NIL节点)

4、每个红色节点必须有两个黑色的子节点。（不能有两个连续的红色节点。）

5、从任一节点到其每个叶子的所有简单路径(不要回退)都包含相同数目的黑色节点。

具体样子如下图所示：

解释一下几个规则的含义：

1和2很好理解，节点都是红和黑，根节点是黑色的。

3所有叶子都是黑色的，叶子与叶子节点是两个概念，叶子不是一个节点，可以理解为没有数值的空节点，也就是图中的NIL。

4也很好理解，红色节点的子节点都是黑色的，这就保证了没有两个连续的红色节点。

5稍微解释一下，简单路径就是说一次到底，不要回退，叶子就是NIL，比如从8这个节点出发，不管是去1下面的叶子，11下面的叶子，还是6下面的叶子，都是经过一个黑色节点，从任何节点出发都是一样的规则，经过相同数量的黑色节点。

以上5个规则，加上二叉树的规则，就组成了红黑树这一极具特点的树型数据结构。