红黑树是一个比较难的数据结构。一般很少研究插入、删除等具体操作步骤。如果遇到面试官让你手写红黑树，直接走人。所以，更多的是考查你对红黑树的理解。最估计的估计就是为什么在有二搜索树/平衡树的情况下还需要红黑树。今天，你只需要花一分钟时间，你就会知道如何回答这个问题。一、二叉搜索树的缺点二叉搜索树，相信大家都接触过，二叉搜索树的特点是左子树的节点值小于父节点，而右子树的节点值子树比父节点大，如图是根据二叉搜索树的特点。当我们搜索某个节点时，可以采用类似二分查找的思路快速找到某个节点。对于一个有n个节点的二叉搜索树，一般情况下，搜索的时间复杂度是O(logn)。之所以正常，是因为二叉查找树可能出现了极端情况。比如这种情况也符合二叉查找树的条件。但是此时的二叉搜索树已经近似退化为链表，这样一棵二叉搜索树的搜索时间复杂度一下子就变成了O(n)。可想而知，决不能让这种事情发生。为了解决这个问题，我们扩展了平衡二叉树。2.平衡二叉树平衡二叉树的诞生就是为了解决二叉查找树退化为链表的问题。平衡树具有以下特点：它具有二叉查找树的所有特点。每个节点的左子树和右子树的高度差最多等于1。例如：图1是平衡树，而图2不是（节点的高度标注在右边）。对于图2，由于节点9的左孩子的高度为2，右孩子的高度为0，两者相差大于1。平衡树基于这个特性可以保证不会有大量节点偏向一侧。如何对平衡树进行构造、插入、删除、左旋、右旋等操作，这里不再赘述。因此，通过平衡树，我们解决了二叉查找树的不足。对于具有n个节点的平衡树，最坏情况下的查找时间复杂度也是O(logn)。3.有了平衡树，为什么还需要红黑树？平衡树虽然解决了二叉搜索树退化为近似链表的缺点，可以将搜索时间控制到O(logn)，但并不是最优的，因为平衡树要求每个节点的左子树和右子树最多等于1，这个要求太严格了，每次插入/删除一个节点，几乎都会破坏平衡树的第二条规则，然后我们都需要调整左右转动使其再次成为平衡树。显然，如果在插入删除非常频繁的场景下，需要频繁调整平衡树，这会大大降低平衡树的性能。为了解决这个问题，出现了红黑树。红黑树具有以下特点：具有二叉搜索树的特点。根节点为黑色；每个叶子节点都是一个黑色的空节点（NIL），即叶子节点不存储数据。相邻节点不能同时为红色，即红色节点被黑色节点隔开。每个节点，以及从该节点到其可达叶节点的所有路径，都包含相同数量的黑色节点。比如下图（注意图中黑色和空的叶子节点没有画出来）（图片来自极客时间）正是因为红黑树的这个特性，使得它能够在最坏的情况下。O(logn)时间复杂度来找到一个节点。至于为什么时间复杂度可以保证为O(logn)，这里就不细说了，以后的文章可能会讲到。但是与平衡树不同的是，红黑树不会像平衡树那样在插入、删除等操作中频繁打破红黑树的规则，因此不需要频繁调整，这就是为什么我们大多数情况下使用红黑树的原因。不过单论搜索效率的话，平衡树比红黑树快。因此，我们也可以说红黑树是一种不太严格的平衡树。也可以说是一种折衷方案。如果你看懂了我上面说的，面试的时候能说出来，应该就够了。我当时就是这么回答的。4.总结所以，最后的答案是，平衡树是为了解决二叉查找树退化成链表的情况，红黑树是为了解决平衡树在操作中需要频繁调整的情况，比如如插入和删除。不过还有很多其他的知识点可以在红黑树上进行测试。比如红黑树有哪些应用场景？在集合容器中，HashMap、TreeMap等，内部结构使用红黑树。还有就是构造一个有n个节点的红黑树。时间复杂度是多少？不同场景下红黑树和哈希表的选择？红黑树的特点是什么？红黑树各种操作的时间复杂度如何？如果这些你都明白了，应该差不多就够了。如果你以后有时间，我会为你详细解释这些问题。最好求理解，不要死记硬背。
