59 lines
2.6 KiB
Markdown
59 lines
2.6 KiB
Markdown
# 红黑树 （red-black tree）
|
||
|
||
红黑树（Red Black Tree） 是一种自平衡二叉查找树。一种特化的[AVL树](../3-平衡树AVL/README.md)，在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 它可以在O(log n)时间内做查找，插入和删除。
|
||
|
||
它的每个结点都被“着色”为红色或者黑色，这些结点的颜色被用来检测树的平衡性。
|
||
|
||
|
||
### 应用场景
|
||
|
||
* C++ STL的map和set
|
||
* java 中 HashMap、TreeMap 的底层实现，当HashMap中元素大于8个时，HashMap底层存储实现改为红黑树，以提高元素搜索速度。
|
||
关于 HashMap 实现解析参考 [这里](../../3%20HashTable/HashMap%20in%20Java.md)
|
||
* 广泛应用Linux 的进程管理、内存管理，设备驱动及虚拟内存跟踪
|
||
* epoll的的的实现采用红黑树组织管理的的的sockfd，以支持快速的增删改查
|
||
* Nginx的的的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器
|
||
|
||
|
||
### RB tree 特点
|
||
|
||
* 每个节点非红即黑
|
||
* 根节点是黑的
|
||
* 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的
|
||
* 如果一个节点是红的，那么它的两儿子都是黑的
|
||
* 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点
|
||
* 每条路径都包含相同的黑节点
|
||
|
||
|
||
在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）；通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍；
|
||
|
||
因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树）。相对于要求严格的[AVL树](../3-平衡树AVL/README.md)来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。
|
||
|
||
|
||
也就是说，红黑树牺牲掉一定的平衡性（牺牲查找性能），换来了 插入，删除操作时 更少的旋转次数带来的开销。
|
||
|
||
|
||
### 红黑树 & B+ 树对比
|
||
|
||
* 红黑树多用在内部排序，即全放在内存中的
|
||
* B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构； 这也是为什么 mysql索引使用b+树而不使用红黑树
|
||
|
||
|
||
为什么使用 红黑树 而不是 B+ 树呢？原因如下：
|
||
|
||
* 没有范围查找, 不需要 B+
|
||
* 不需要多路平衡树，使用二路平衡，实现简单，且红黑树能兼顾 查找，删除操作的性能
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|