红黑树
红黑树介绍
数据结构的学习本来就比较难了，红黑树是又将难度上升一个档次的知识点
红黑树(英语: Red-black tree)是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构
- 它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J.Guibas和罗伯特·塞奇威克于1978年写的一篇论文
红黑树。除了符合二叉搜索树的基本规则外，还添加了一下特性:
- 节点是红色或黑色(AVL树给每个节点一个权值，RB树给每个节点一个颜色)
- 根节点是黑色
- 每个叶子节点都是黑色的空节点(null节点，空节点)
- 第三条性质要求每个叶节点(空节点)是黑色的
- 这是因为在红黑树中，黑色节点的数量表示从根节点到叶子节点的黑色节点数量
- 每个红色节点的两个子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 第四条性质保证了红色节点的颜色不会影响树的平衡，同时保证了红色节点的出现不会导致连续的红色节点
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
- 第五条性质是最重要的性质，保证了红黑树的平衡性
这些规则会让人一头雾水
- 完全搞不懂规则叠加起来，怎么让一棵树平衡的
- 但是它们还是被一些聪明的人发明出来了
红黑树相对平衡
前面的性质约束，确保了红黑树的关键特性:
- 从根到叶子的最长可能路径，不会超过最短可能路径的两倍长
- 结果就是这个树基本是平衡的
- 虽然没有做到绝对的平衡，但是可以保证在最坏的情况下，依然是高效的
为什么可以做到最长路径不超过最短路径的两倍呢?
- 性质五决定了最短路径和最长路径必须有相同的黑色节点
- 路径最短的情况：全部是黑色节点n
- 路径最长的情况：黑色节点的数量也是n，中间全部是红色节点 n - 1
- 性质二：根节点是黑节点
- 性质三：叶子节点都是黑节点
- 性质四：两个红色节点不能相连
- 最短路径为 n - 1(边的数量)
- 最长路径为 (n + n - 1) - 1 = 2n - 2
- 所以最长路径一定不超过最短路径的2倍
红黑树性能分析
事实上，红黑树的性能在搜索上是不如AVL树的，为什么呢？
我们来看一下右边的红黑树:
- 首先，它符合是一颗红黑树吗？符合
- 这个时候我们插入节点30，会被插入到哪里呢？
- 27的右边，并且节点30是红色节点时，依然符合红黑树的性质
- 也就是对于红黑树来说，它不需要进行任何操作
那么AVL树会怎么样呢？
- 如果是AVL树必然要对17、25、27节点进行右旋转
- 事实上右旋转是一系列的操作
但是红黑树的高度比AVL树要高:
- 所以如果同样是搜索30，那么红黑树需要搜索4次，AVL树搜索3次
- 所以红黑树相当于牺牲了一点点的搜索性能，来提高了插入和删除的性能
AVL树和红黑树的选择
- AVL树是一种平衡度更高的二叉搜索树，所以在搜索效率上会更高
- 但是AVL树为了维护这种平衡性，在插入和删除操作时，通常会进行更多的旋转操作，所以效率相对红黑树较低
- 红黑树在平衡度上相较于AVL树没有那么严格，所以搜索效率上会低一些
- 但是红黑树在插入和删除操作时，通常需要更少的旋转操作，所以效率相对AVL树较高
- 它们的搜索、添加、删除时间复杂度都是O(logn)，但是细节上会有一些差异
开发中如何进行选择呢?
- 选择AVL树还是红黑树，取决于具体的应用需求
- 如果需要保证每个节点的高度尽可能地平衡，可以选择AVL树
- 如果需要保插入/证删除操作的效率，可以选择红黑树
在早期的时候，很多场景会选择AVL树，目前选择红黑树的越来越多(AVL树依然是一种重要的平衡树)
- 比如操作系统内核中的内存管理
- 比如Java的TreeMap、Treeset底层的源码