数据结构属于理解一些源码和技术所必备的知识，比如要读懂 Java 语言中 TreeMap 和 TreeSet 的源码就要懂红黑树的数据结构，不然是无法理解源码中关于红黑树数据的操作代码的，比如左旋、右旋、添加和删除操作等。因此本课时我们就来学习一下数据结构的基础知识，方便看懂源码或者是防止面试中被问到。 我们本课时的面试题是，红黑树和二叉树有什么区别？ #### 典型回答 要回答这个问题之前，我们先要弄清什么是二叉树？什么是红黑树？ 二叉树（Binary Tree）是指每个节点最多只有两个分支的树结构，即不存在分支大于 2 的节点，二叉树的数据结构如下图所示：  这是一棵拥有 6 个节点深度为 2（深度从 0 开始），并且根节点为 3 的二叉树。 二叉树有两个分支通常被称作“左子树”和“右子树”，而且这些分支具有左右次序不能随意地颠倒。 一棵空树或者满足以下性质的二叉树被称之为二叉查找树： * 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； * 若任意节点的右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值； * 任意节点的左、右子树分别为二叉查找树。 如下图所示，这就是一个标准的二叉查找树：  二叉查找树（Binary Search Tree）也被称为二叉搜索树、有序二叉树（Ordered Binary Tree）或排序二叉树（Sorted Binary Tree）等。 红黑树（Red Black Tree）是一种自平衡二叉查找树，它最早被称之为“对称二叉 B 树”，它现在的名字源于 1978 年的一篇论文，之后便被称之为红黑树了。 所谓的平衡树是指一种改进的二叉查找树，顾名思义平衡树就是将二叉查找树平衡均匀地分布，这样的好处就是可以减少二叉查找树的深度。 一般情况下二叉查找树的查询复杂度取决于目标节点到树根的距离（即深度），当节点的深度普遍较大时，查询的平均复杂度就会上升，因此为了实现更高效的查询就有了平衡树。 非平衡二叉树如下图所示：  平衡二叉树如下图所示：  可以看出使用平衡二叉树可以有效的减少二叉树的深度，从而提高了查询的效率。 红黑树除了具备二叉查找树的基本特性之外，还具备以下特性： * 节点是红色或黑色； * 根节点是黑色； * 所有叶子都是黑色的空节点（NIL 节点）； * 每个红色节点必须有两个黑色的子节点，也就是说从每个叶子到根的所有路径上，不能有两个连续的红色节点； * 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。 红黑树结构如下图所示：  #### 考点分析 红黑树是一个较为复杂的数据结构，尤其是对于增加和删除操作来说，一般面试官不会让你直接手写红黑树的具体实现。如果你只有很短的时间准备面试的话，那么我建议你不要死磕这些概念，要学会有的放矢，因为即使你花费很多的时间来背这些概念，一转眼的功夫就会彻底忘掉，所以你只需要大概地了解其中的一些概念和明白大致的原理就足够了。 和此知识点相关的面试题还有以下这些： * 为什么工程中喜欢使用红黑树而不是其他二叉查找树？ * 红黑树是如何保证自平衡的？ #### 知识扩展 * [ ] 红黑树的优势 红黑树的优势在于它是一个平衡二叉查找树，对于普通的二叉查找树（非平衡二叉查找树）在极端情况下可能会退化为链表的结构，例如，当我们依次插入 3、4、5、6、7、8 这些数据时，二叉树会退化为如下链表结构：  当二叉查找树退化为链表数据结构后，再进行元素的添加、删除以及查询时，它的时间复杂度就会退化为 O(n)；而如果使用红黑树的话，它就会将以上数据转化为平衡二叉查找树，这样就可以更加高效的添加、删除以及查询数据了，这就是红黑树的优势。 > 小贴士：红黑树的高度近似 log2n，它的添加、删除以及查询数据的时间复杂度为 O(logn)。 我们在表示算法的执行时间时，通常会使用大 O 表示法，常见的标识类型有以下这些： * O(1)：常量时间，计算时间与数据量大小没关系； * O(n)：计算时间与数据量成线性正比关系； * O(logn)：计算时间与数据量成对数关系； * [ ] 自平衡的红黑树 红黑树能够实现自平衡和保持红黑树特征的主要手段是：变色、左旋和右旋。 左旋指的是围绕某个节点向左旋转，也就是逆时针旋转某个节点，使得父节点被自己的右子节点所替代，如下图所示：  在 TreeMap 源码中左旋的实现源码如下： ``` // 源码基于 JDK 1.8 private void rotateLeft(Entry<K,V> p) { if (p != null) { // 右子节点 Entry<K,V> r = p.right; // p 节点的右子节点为 r 的左子节点 p.right = r.left; // r 左子节点如果非空，r 左子节点的父节点设置为 p 节点 if (r.left != null) r.left.parent = p; r.parent = p.parent; // r 父节点等于 p 父节点 // p 父节点如果为空，那么讲根节点设置为 r 节点 if (p.parent == null) root = r; // p 父节点的左子节点如果等于 p 节点，那么 p 父节点的左子节点设置 r 节点 else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; } } ``` 左旋代码说明：在刚开始时，p 为父节点，r 为子节点，在左旋操作后，r 节点代替 p 节点的位置，p 节点成为 r 节点的左孩子，而 r 节点的左孩子成为 p 节点的右孩子。 右旋指的是围绕某个节点向右旋转，也就是顺时针旋转某个节点，此时父节点会被自己的左子节点取代，如下图所示：  在 TreeMap 源码中右旋的实现源码如下： ``` private void rotateRight(Entry<K,V> p) { if (p != null) { Entry<K,V> l = p.left; // p 节点的左子节点为 l 的右子节点 p.left = l.right; // l 节点的右子节点非空时，设置 l 的右子节点的父节点为 p if (l.right != null) l.right.parent = p; l.parent = p.parent; // p 节点的父节点为空时，根节点设置成 l 节点 if (p.parent == null) root = l; // p 节点的父节点的右子节点等于 p 节点时，p 的父节点的右子节点设置为 l else if (p.parent.right == p) p.parent.right = l; else p.parent.left = l; l.right = p; p.parent = l; } } ``` 右旋代码说明：在刚开始时，p 为父节点 l 为子节点，在右旋操作后，l 节点代替 p 节点，p 节点成为 l 节点的右孩子，l 节点的右孩子成为 p 节点的左孩子。 对于红黑树来说，如果当前节点的左、右子节点均为红色时，因为需要满足红黑树定义的第四条特征，所以需要执行变色操作，如下图所示：  由于篇幅有限，我这里只能带你简单地了解一下红黑树和二叉树的基本概念，想要深入地学习更多的内容，推荐查阅《算法》（第四版）和《算法导论》等书籍。 #### 小结 我们本课时介绍了二叉树、二叉查找树及红黑树的概念，还有红黑树的五个特性。普通二叉查找树在特殊情况下会退化成链表的数据结构，因此操作和查询的时间复杂度变成了 O(n)，而红黑树可以实现自平衡，因此它的操作（插入、删除）和查找的时间复杂度都是 O(logn)，效率更高更稳定，红黑树保证平衡的手段有三个：变色、左旋和右旋。 #### 课后问答 * 1、红黑树，为什么要有红色和黑色？2、执行变色操作的目的是？ 讲师回复： 红黑树本质上是一种平衡树，执行变色是为了维持节点的平衡。 * 2、红黑树的高度最多是 2log（n），这个可以怎么理解？ 讲师回复： 红黑树的高度取决于节点的个数哦~ * 3、红黑树比AVL树的优点是什么？ 讲师回复： AVL属于早期的平衡树，红黑树可以简单的理解为包含了 AVL 的特性，同时有新增了颜色的属性用于存储更多的信息。