奈学：红黑树 (RedBlackTree) 的概述

1. AVL树与红黑树



  AVL树是一种自平衡的二叉查找树，又称平衡二叉树。AVL用平衡因子判断是否平衡并通过旋转来实现平衡，它的平衡的要求是：所有节点的左右子树高度差不超过1。AVL树是一种高平衡度的二叉树，执行插入或者删除操作之后，只要不满足上面的平衡条件，就要通过旋转来保持平衡，而的由于旋转比较耗时，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况。  由于维护这种高度平衡所付出的代价可能比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。  红黑树(Red Black Tree)，它一种特殊的二叉查找树，是AVL树的特化变种，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 红黑树的平衡的要求是：从根到叶子的最长的路径不会比于最短的路径的长超过两倍。 因此，红黑树是一种弱平衡二叉树，在相同的节点情况下，AVL树的高度<=红黑树。  红黑树是用弱平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，降低了对旋转的要求，从而提高了性能，所以对于查询，插入，删除操作都较多的情况下，用红黑树。



2. 红黑树的定义



AVL树的定义如下：



1. 它一定是一棵二叉排序树；

2. 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，递归定义。



相对于AVL树，红黑树的定义明显更加复杂：



1. 它一定是一棵二叉排序树；

2. 每个节点或者为黑色或者为红色；

3. 根节点一定为黑色；

4. 如果一个节点是红色的，那么它的子节点要么是null要么是黑色的（也就是说，不能有两个相邻的红色节点，即红色节点的父、左子、右子节点只能是黑色节点）。

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



根据上面的定义，可以推算出：



1. 因为黑色节点数量要一样，红色不能连着来，从而路径全黑时最短，红黑交替时最长。因此可以推算出：红黑树从根到叶子节点的最长的路径不会比于最短的路径的长超过两倍。红黑树是一种弱平衡二叉树，在相同的节点情况下，AVL树的高度<=红黑树。

2. 红黑树的高度最坏情况下为2log(N+1)。因此它也可以在O(log n)时间内做查找，插入和删除。



  有一些红黑树定义还有一个性质：“红黑树中叶子节点为最后的空节点，并且每个叶子节点是黑色的”。该定义并不会对之前的定义产生影响，其目的更多是为了简化平衡操作的情况，平衡时可以认为：null就是黑色节点。此时只需要考虑红和黑这两种情况就行，而不用考虑非红非黑的null。如下图（源自网络）：





3. 红黑树的应用



  红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。  实际上，Robert Sedgewick在《算法（第4版）》 中说过，红黑树等价于2-3树。其中2-节点等价于普通平衡二叉树的节点，3-节点本质上是非平衡性的缓存。  也就是说在添加、删除节点之后需要重平衡时，相当于2-节点 与3-节点间的转换，由于3-节点的缓存作用，能够吸收一部分不平衡性，从而减少旋转次数，减少重平衡时间。  尽管由于红黑树的最大高度高于AVL树导致此查询时稍慢，但是差距不大，而添加、删除数据时红黑树快于AVL树，红黑树的旋转次数为O(1)，即最多旋转3次；而AVL的旋转次数为O(logN)，即最多向上旋转至根节点。整体来看，红黑树的综合效率高于AVL树，红黑树比AVL树的应用范围更广泛！AVL的应用：



1. Windows NT内核



红黑树的应用：



1. JDK1.8及之后版本的Map实现，比如HashMap、TreeMap。

2. 广泛用于C++的STL中,map和set都是用红黑树实现的.

3. 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.

4. IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查.

5. ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器。



文章来源于：奈学开发者社区，如有侵权，请联系我删除~