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

~ 红黑树是处于二叉树和平衡二叉树之间的一种折中方案的算法。说起来红黑树也算是比较难理解的一个数据结构了吧，因为其本身的增删节点，除了左旋右旋还需要变色的复杂操作。

为什么有平衡二叉树这种适合适合查找的数据结构在，还需要红黑树呢？还是先从二叉树说起。

二叉查找树的特点就是 左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大。

二叉树的查询颇有 二分查找 的思想，如果查询一个节点，n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O（logn）。为什么说是正常情况，因为上面的树其实不只是二叉树而且还是平衡二叉树。

那如果不正常的情况下，二叉树是啥样的呢？下面是一种退化为类似链表的二叉树的极端情况。这样的二叉查找树的查找时间复杂度顿时变成了 O(n)，类似于在做全表扫描，为了避免这种情况的发生，平衡二叉树在这种情况下登场了。平衡二叉树除了具有二叉树的全部特性外，加了一个规则，就是每个节点的左子树和右子树的高度差至多等于1。

嗯，这样的话就不会出现一棵链表了。平衡二叉树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。这样平衡二叉树对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)。平衡二叉树通过 构建、插入、删除、左旋、右旋 等操作来达到平衡。

MySQL索引中 B树和B+树是基于平衡二叉树的进一步改进 。B+树索引按照存储方式的不同分为 聚集索引 和 非聚集索引。

二叉树的算法实现 其实就是要插入的节点都开始和根节点比，小的放节点左边大的右边，如果位置上已经有节点了就再迭代，把当前节点作为根节点来判断放左右，直到有空位置为止。

有了平衡二叉树这么优秀的结构为什么还需要红黑树，因为平衡二叉树要求 每个节点的左子树和右子树的高度差至多等于1 ，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树规则，进而我们都需要通过 左旋 和 右旋 来进行调整，使之再次成为一颗符合要求的平衡树。如果频繁增删就会带来性能问题。所以红黑树出现了。

红黑树特性：

1、具有二叉查找树的特点。

2、根节点是黑色的；

3、 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据 。

4、 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。

5、 每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。（限制了高度）

下面是两棵红黑树的例子（黑色的空叶子节点没有画出）：

上面的例子似乎有点平衡二叉树的味道，但它并不是必须满足平衡二叉树的深度差不超过1的条件，如下面的例子。

红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。但与平衡树不同的是，红黑树在插入、删除等操作， 不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整。 意思是查效率相当，但改效率高于平衡树，这也是我们为什么大多数情况下使用红黑树的原因。只不过据说单单在查找方面的效率的话，平衡树会比红黑树快点。

综上，可以说 红黑树是一种不大严格（没有深度差要求）的平衡树 。也可以说是一个折中方案。

那么红黑树如何进行左旋，右旋和变色来达到平衡呢 ?笔者也还没完全吃透，不过理解了上面的这些应该也够驰骋沙场了。

参考文献：

腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？

红黑树旋转

---

通河县15197384080： 有二叉排序树为何要平衡二叉树 - ？
万欢安可： 因为二叉排序树最坏时的性能为O(n),如果n个关键字随意排列,接近一半的情况会导致这个结果,而不是理论的O(log2n)那个平衡二叉树最坏时也只是1.5log2n

通河县15197384080： 平衡二叉树的作用 - ？
万欢安可： 我们知道,对于一般的二叉搜索树(Binary Search Tree),其期望高度(即为一棵平衡树时)为log2n,其各操作的时间复杂度(O(log2n))同时也由此而决定.但是,在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化...

通河县15197384080： 为什么要构建平衡二叉树,的主要目的为? - ？
万欢安可： 因为正常的二叉排序树弄得不好查找性能近似于O(n),使用平衡二叉树则可以保证查找性能不超过1.5log2n

通河县15197384080： 什么是平衡二叉树 - ？
万欢安可： 形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ,其严格定义是:一棵空树是平衡二叉树;若 T 是一棵非空二叉树,其左、右子树为 TL 和 TR ,令 hl 和 hr 分别为左、右子树的深度.当且仅当 ①TL 、 TR 都是平衡二叉树;② | hl - hr |≤ 1;时,则 T 是平衡二叉树.

通河县15197384080： 平衡二叉树比其他二叉树有什么好处 - ？
万欢安可： 首先平衡二叉树是特殊的二叉排序树,他的结点元素间存在着偏序关系. 其次相对于一般的二叉排序树,平衡二叉树的左右子树的深度差也有不超过1层的约束. 这样使得平衡树是同种元素序列情况下的深度最小的二叉排序树.这可以减少二叉树元素查找的深度,从而提升平均查找效率.

通河县15197384080： 红黑树算法为什么需要左旋和右旋 - ？
万欢安可： 红黑树是平衡二叉树的一种,它有很好的性质,树中的结点都是有序的,而且因为它本身就是平衡的,所以查找也不会出现非常恶劣的情况,基于二叉树的操作的时间复杂度是O(log(N)).Linux内核在管理vm_area_struct时就是采用了红黑树来维...

通河县15197384080： 平衡二叉树怎么理解啊? - ？
万欢安可： 这要涉及到满二叉树与完全二叉树的问题 满二叉树是将一个n层二叉树完全排满的二叉树,第n层有2^n个元素;n层完全二叉树是将n层满二叉树最后一层从后向前依次去处少于2^n个元素;完全二叉树是平衡二叉树的一个特例,平衡二叉树是将完全二叉树的最后一层元素任意排在空位上的一种二叉树.如下图所示,左为满二叉树,右为完全二叉树:

通河县15197384080： 平衡二叉树概念 - ？
万欢安可： 我觉得平衡二叉树,不一定必须是二叉搜索树.但它的概念之所以提出来,就是为了提高搜索效率的 要求二叉树达到平衡,就是要在搜索的时候,不至于沿着某个子树搜索下去 极端不平衡的二叉树,退化成线性表了,搜索就变成“遍历”了

通河县15197384080： 平衡二叉树插入 已经存在a '再插入a 会引起什么变化? - ？
万欢安可： 形态没有变化,因为属于重复的关键字,如果要插入重复的关键字,需要用索引等次关键字技术 二叉排序树和平衡二叉树一般插入前需要先查找,如果查找失败,才会插入,查找成功则不会插入

通河县15197384080： 满二叉树为什么不是平衡树 - ？
万欢安可： 满二叉树不是平衡树的原因: (1)满二叉树:除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树. (2)平衡树,即平衡二叉树,又被称为AVL树(区别于AVL算法),它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.平衡树,左子节点与右子节点对称.