红黑树红黑树和AVL 树一样都是平衡二叉搜索树。但是 AVL 树 比红黑树更加严格AVL 树要求左右子树的高度差 1 而红黑树只能保证最长路径不超过最短路径的 2 倍。AVL 树通过旋转控制平衡为了达到它严格的规定需要旋转的次数较多。红黑树通过旋转 变色控制平衡同时也因为规定比较宽松所以旋转的次数少。在插入方面显然是红黑树更具有效率优势。在查找方面由于 AVL树 比 红黑树 更平衡一些所以效率更快但它们的效率都是 O (log n)级别的所以红黑树瑕不掩瑜多数情况下使用的都比比AVL树更多。红黑树的规则上面提到红黑树能保证最长路径不超过最短路径的 2 倍。它是如何做到的呢这和红黑树的构造规则相关如下1.每个节点不是红色就是黑色。2.根节点是黑色的。3.如果一个节点是红色的它的两个孩子必须是黑色即不能连续出现两次红色节点。4.对于任意一个节点从该节点到其所有NULL节点的简单路径上均包含相同数量的黑色节点。这四条规则共同约束了树的结构最终保证了红黑树的核心性质从任意节点出发到其所有叶子节点的最长路径不会超过最短路径的 2 倍。举一些例子仔细观察你会发现这些树都满足了红黑树的规则同时它们也做到了最长路径不超过最短路径的2倍。红黑树的调整AVL树于1962年诞生红黑树比它晚了 10 年所谓前人栽树后人乘凉红黑树 的旋转调整逻辑和 AVL树 完全一致AVL树在上一篇博客讲过那么我们接下来所需要讨论就是红黑树的专属调整逻辑变色。在讲调整逻辑之前我们得先搞清楚什么情况下需要调整。从第一个规则可知新插入的节点非黑即红我们来分类讨论黑当插入节点为黑色时我们会违法第四个规则因为插入一个黑色节点无论如何都不能保持每条路径上的黑色节点相同了注意走到空节点才算一条路径所以绝对不能插入黑色节点。没错即使插入节点是 root 我们也应该插入红色节点然后再让它变色。红既然不能插入黑色那么插入的必然就是红色节点了。但是插入红色节点的情况有两种通过父节点来区分。父节点为黑没有违法任何规则即满足红黑树故无需调整。父节点为红违反第三个规则此时我们就需要进行调整了。那么如何调整呢先看图上图是一颗新插入了节点的红黑树为了方便说明我们对调整所需的相关节点进行标记新节点为 c意为current表示当前节点新节点的父节点为 p 意为parent表示父节点父节点的兄弟为 u意为uncle表示 “叔叔” 节点父节点的父节点为 g意为grandparent意为 “爷爷” 节点。对红黑树的调整最关键的就是 “叔叔” 节点。在上面这颗树中 p 和u 存在且为红色g 为黑色此时我们将 p 和 u 变为黑色g 变为红色完美解决啦但当 u 不存在或者u 为黑色的时候单纯的变色是无法解决问题的比如u 不存在时此时树的结构违反第四个规则。从根节点到 g 再到 g 的右孩子这条路径比其他路径少一个黑节点。那么怎么办答案是旋转只需要对 g 为根节点的树进行一次右单旋即可解决问题。当 c 节点插入在 p 的不同位置时使用的旋转方法不同u 为黑色时u 是黑色节点的情况是什么样的按照之前的逻辑既然我们需要调整了那么 c 与 p 必然是红色节点g 必然是黑色节点如果 u 是黑色原来的树不是违反规则了吗我们难道能给一颗违反规则的树插入节点吗我们当然不能给一颗违反规则的树插入节点但是想象一下当我们某次调整时对 g 进行变色本来是黑色的 g 变成了 红色。此时如果 g 的父节点也是红色那么我们的调整并没有将树调整好需要继续向上进行我们将 g 设置为 c 当前节点就有可能出现新的 c 节点的 u 节点为黑色的情况。对于这样一颗树我们要做的是 变色加旋转 。经过 变色加旋转 处理的不需要继续向上调整。这里给出插入的核心代码因为代码量比较大这里只贴了核心代码的一部分另一部分逻辑类似。