为什么有了二叉查找树/平衡树，还需要红黑树？

当我们有二叉搜索树/平衡树时，为什么还需要红黑树？ ？如果我想让你在红树和黑树上手写面试官，就再见。这就是为什么你对红黑树的理解受到更多考验。一个常见的问题是当你有二叉搜索树/平衡树时，为什么还需要红黑树？ 这个问题，今天给你，只需要一分钟就能弄清楚如何回答这个问题。

1。二叉搜索树的缺点

二叉搜索树，我想大家都遇到过。二叉搜索树的特点是儒家节点的值小于父节点，而右子树节点的值大于父节点，如图

基于二叉搜索树的特点，当我们查找某个节点时，可以采用类似二分查找的思路来快速找到该特定节点。在n个节点的二叉搜索树中，一般情况下搜索时间复杂度为O(logn)。之所以说正常情况下

是，是因为二叉搜索树可能会出现

这样的极端情况。这种情况也满足二叉搜索树条件，但是二叉搜索树目前大致退化为链表，这样的二叉搜索树的搜索时间复杂度突然变成了O(n)。可想而知，我们绝对不能让这种情况发生。为了解决这个问题，我们推导出了平衡二叉树。

2。平衡二叉树

平衡二叉树是为了解决二叉搜索树变成链表的问题而创建的。平衡树具有以下属性

1。它具有二叉搜索树的所有功能。

2。左子树与每个节点的右子树的高度差最多为1。

例如：图1是平衡树，但图2不是（节点右边的标记是节点的高度）

。

在图2中，因为节点9的左孩子的高度为2，右孩子的高度为0。它们之间的差值大于1。

基于这个性质，平衡树可以确保大量节点不偏向一侧。这里我就不解释平衡树如何建立、添加、删除、左移、右移等操作。如果想了解更多，可以看我之前写的文章：【漫画】以后面试官问你AVL树的事，就把这篇文章扔掉吧。把这个给他。

所以通过平衡树我们解决了二叉搜索树的缺点。在有 n 个节点的平衡树中，最坏情况的搜索时间复杂度也是 O(logn)。

既然有了平衡树，为什么还需要红黑树呢？

虽然平衡树解决了二叉搜索树变成近似链表的缺点，并且可以将搜索时间控制到O(logn)，但它并不是最优的，因为平衡树需要每个左子树和。 node 右子树的高度差最多为 1。这个要求太严格了，以至于每次添加/删除一个节点，都几乎打破了平衡树的第二条规则，然后我们都要通过左转和右转。 进行调整，使其再次成为符合要求的平衡树。

如果场景中有频繁的增删，平衡树自然需要频繁调整，这会明显降低平衡树的性能。为了解决这个问题，开发了红黑树，红黑树具有以下性质：

1。它具有二叉搜索树的性质。

2。根节点为黑色；

3。每个叶子节点都是一个黑色空节点（NIL），意味着叶子节点不存储任何数据。

4。相邻节点不能同时为红色，即红色节点被黑色节点隔开。

5。对于每个节点，从该节点到其可达叶节点的所有路径都包含相同数量的黑色节点。

比如下图（注意图中黑色和空的叶子节点没有画出来）（图片来自极客时光）

正是因为红黑木的这个特性，才可以在最坏的情况下使用。这种情况下，找到节点的时间复杂度也是O(logn)。至于为什么时间复杂度可以保证为O(logn)，这里就不详细说了，可以在以后的文章中介绍。

但是，与平衡树不同，红黑树在插入和删除操作时不会经常违反红黑树的规则，像平衡树一样，所以不需要经常调整，这就是我们在大多数情况下使用红黑树的原因。

不过，如果只想谈搜索效率的话，平衡树比红黑树要快。

所以我们也可以说红黑树是一种不太紧平衡的树。也可以称为折衷方案。

如果你明白我上面说的并且能在采访中说出来，那就足够了。这就是我当时的回答。

总结

所以最终答案是，平衡树是为了解决二叉搜索树退化为链表的情况，而红黑树解决的是平衡树在运行过程中需要频繁调整的情况插入、删除等操作。

然而，关于红黑树还有许多其他可测试的数据点。比如红黑树有哪些应用场景？在集合容器中，HashMap、TreeMap等，内部结构采用红黑树。构建一棵包含n个节点的红黑树的时间复杂度是多少？不同场景下红黑树和哈希表有什么选择？红黑树有什么特点？各种红黑树操作的时间复杂度是多少？

如果你明白了所有这些，你就差不多完成了。如果以后有时间，我会详细向大家解释这些问题。这里最好要求理解而不是死记硬背。