红黑树

2022-06-10 IT知识红黑树

亦余心之所善兮，虽九死其犹未悔。这篇文章主要讲述红黑树相关的知识，希望能为你提供帮助。
红黑树（一）

① 下面这棵树是否是红黑树?

回顾红黑树必须满足以下5条性质

节点是RED或者BLACK
根节点是BLACK
叶子节点(外部节点，空节点)都是BLACK
RED节点的子节点都是BLACK
4.1 RED节点的parent 都是BLACK
4.2 从根节点到叶子节点的所有路径_上不能有2个连续的RED节点
从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

按照规则5来进行分析，38的右边是没有叶子节点的，但是其实是子叶子null的，也就是从根节点到38右边的子叶子是null，黑色只有2个，其他都是3个，很明显这不是一颗红黑树。

② 红黑树的等价变换

38 和 80 上升一层。就转成了一颗B树。4阶B树。

红黑树和4阶B树(2-3-4树) 具有等价性
BLACK节点与它的RED子节点融合在一起，形成1个B树节点
红黑树的BLACK节点个数与4阶B树的节点总个数相等
【红黑树】网上有些教程:用2-3树与红黑树进行类比，这是极其不严谨的，2-3树并不能完美匹配红黑树的所有情况，只有4阶B树才能完美匹配。

推荐阅读

上一篇：实战篇（如何查看mysql里面的锁）

下一篇：春眠不觉晓，Redis数据类型知多少（String,List,Set,SortedSet,Hash,Bitmap,HyperLogLogs）