red-black-tree
category: 计算机基础 tag:
- 数据结构
红黑树
红黑树特点 :
- 每个节点非红即黑;
- 根节点总是黑色的;
- 每个叶子节点都是黑色的空节点(NIL节点);
- 如果节点是红色的,则它的子节点必须是黑色的(反之不一定);
- 从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)。
红黑树的应用 :TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。
为什么要用红黑树? 简单来说红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。详细了解可以查看 漫画:什么是红黑树?(也介绍到了二叉查找树,非常推荐)
相关阅读 :《红黑树深入剖析及Java实现》(美团点评技术团队)
相关文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
8、 golang
-
9、 openharmony
-
10、 Vue中input框自动聚焦