File tree 1 file changed +11
-7
lines changed
1 file changed +11
-7
lines changed Original file line number Diff line number Diff line change 78
78
* ** 6 红黑树**
79
79
80
80
- 红黑树特点:
81
- 1. 每个节点非红即黑;
82
- 2. 根节点总是黑色的;
83
- 3. 每个叶子节点都是黑色的空节点(NIL节点);
84
- 4. 如果节点是红色的,则它的子节点必须是黑色的(反之不一定);
85
- 5. 从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
81
+ 1. 每个节点非红即黑;
82
+ 2. 根节点总是黑色的;
83
+ 3. 每个叶子节点都是黑色的空节点(NIL节点);
84
+ 4. 如果节点是红色的,则它的子节点必须是黑色的(反之不一定);
85
+ 5. 从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
86
86
87
87
- 红黑树的应用:
88
88
89
89
TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。
90
+
91
+ - 为什么要用红黑树
92
+
93
+ 简单来说红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。详细了解可以查看 [漫画:什么是红黑树?](https://juejin.im/post/5a27c6946fb9a04509096248#comment)(也介绍到了二叉查找树,非常推荐)
90
94
91
- - 推荐文章
95
+ - 推荐文章:
92
96
- [漫画:什么是红黑树?](https://juejin.im/post/5a27c6946fb9a04509096248#comment)(也介绍到了二叉查找树,非常推荐)
93
97
- [寻找红黑树的操作手册](http://dandanlove.com/2018/03/18/red-black-tree/)(文章排版以及思路真的不错)
94
98
- [红黑树深入剖析及Java实现](https://zhuanlan.zhihu.com/p/24367771)(美团点评技术团队)
95
99
* ** 7 B-,B+,B* 树**
96
100
97
101
[ 二叉树学习笔记之B树、B+树、B* 树 ] ( https://yq.aliyun.com/articles/38345 )
98
102
99
- [《B-树,B+树,B*树详解》](https://blog.csdn.net/aqzwss/article/details/53074186)
103
+ [ 《B-树,B+树,B* 树详解》] ( https://blog.csdn.net/aqzwss/article/details/53074186 )
100
104
101
105
[ 《B-树,B+树与B* 树的优缺点比较》] ( https://blog.csdn.net/bigtree_3721/article/details/73632405 )
102
106
You can’t perform that action at this time.
0 commit comments