JAVA——比较难和底层的面试题 - JAVA高级部分JAVA高级部分

104 阅读 0 评论 69 点赞

我是靠谱客的博主动人篮球，这篇文章主要介绍JAVA——比较难和底层的面试题 - JAVA高级部分JAVA高级部分，现在分享给大家，希望可以做个参考。

JAVA高级部分

红黑树的实现原理和应用场景；

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
1.（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
2.红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
参考链接：https://www.cnblogs.com/skywang12345/p/3245399.html
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html