红黑树
目录
¶概述
R-B Tree，全称是 Red-Black Tree，又称为红黑树，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)
🎶通过对任何一条从根到叶子的简单路径上各个节结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因而使近似于平衡的
✨红黑树特性
- 每个节点要么是黑色要么是红色
- 根节点是黑色
- 每个叶子节点（NIL）是黑色
- 如果一个结点是红色的，则它的两个子节点都是黑色的
- 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
🎶red-black注意点
- 这里叶子节点，是指为空(NIL 或 NULL)的叶子节点
- 确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树
👴红黑树只想做到一件事，确保路径长度不会出现倍数关系
¶附录
数据结构与算法:实现红黑树的基本思想
平衡二叉树和红黑树最差情况性能分析
红黑树
Java 面试之 HashMap 的红黑树
红黑树-美团
红黑树比 AVL 树具体更高效在哪里？
红黑树与普通的平衡二叉树除了颜色到底有什么区别？为什么要引入红黑树，它比普通的平衡二叉树究竟好在哪？
红黑树(一)之 原理和算法详细介绍
教你初步了解红黑树