| category | tag | |
|---|---|---|
计算机基础 |
|
红黑树特点 :
- 每个节点非红即黑；
- 根节点总是黑色的；
- 每个叶子节点都是黑色的空节点（NIL 节点）；
- 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
- 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。
红黑树的应用：TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。
为什么要用红黑树？ 简单来说红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。详细了解可以查看 漫画：什么是红黑树？（也介绍到了二叉查找树，非常推荐）
相关阅读：《红黑树深入剖析及 Java 实现》（美团点评技术团队）