Java Collections Framework - 红黑树

女爷i 2022-05-31 14:19 162阅读 0赞

# **红黑树在Java中的应用** #

在Java集合类中，TreeMap和TreeSet的底层就是基于红黑树实现的，在JDK 1.8中如果HashMap和ConcurrentHashMap的某Bucket的链表的数量大于8，就会自动转换成红黑树结构，所以红黑树是一种应用很广的二叉查找树。

红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

--------------------

# **二叉查找树** #

二叉查找树（Binary Sort Tree）具备什么特性呢？

> 1.左子树上所有结点的值均小于或等于它的根结点的值。  
> 2.右子树上所有结点的值均大于或等于它的根结点的值。  
> 3.左、右子树也分别为二叉排序树。

下图就是个典型的二叉查找树  
![这里写图片描述][70]

二分查找正是用的这个思想，查找所需要的最大次数等于树的高度。

但是二叉查找树也存在缺陷，可能变成以下的情况  
![这里写图片描述][70 1]

这样整个二叉查找树就几乎变成线性的了。

--------------------

# **红黑树** #

因为二叉查找树可能出现上面的情况，所以红黑树应运而生。红黑树是一种自平衡的二叉查找树。  
具有一下特性：

> 1、每个节点要么红色，要么是黑色；  
> 2、根节点一定是黑色的；  
> 3、每个空叶子节点必须是黑色的；  
> 4、从每个叶子到根的所有路径上不能有两个连续的红色节点  
> 5、任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等

![这里写图片描述][70 2]

只要满足以上5个特性的二叉树都是红黑树，当有新的节点加入时，有可能会破坏其中一些特性，需要通过左旋或右旋操作调整树结构，重新着色，使之重新满足所有特性。

--------------------

# **AVL 树** #

AVL是一种高度平衡的二叉树，AVL树中任何节点的两个子树的高度最大差别为一.  
![这里写图片描述][70 3]  
AVL过度的要求树的平衡，在一些场景中性能不如红黑树。

[70]: /images/20220531/dfd5f262e91d4e8b8de13cb59da8eae0.png
[70 1]: /images/20220531/f8dc6f4a66f94190912ccf9c495612f2.png
[70 2]: /images/20220531/403409f2035b4cdab6fbdb12e67cb988.png
[70 3]: /images/20220531/1c5480ed725e410b85cc28035104d709.png

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关红黑树(Java)

红黑树红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Ba

超、凢脫俗/ 2023年07月04日 12:41/ 0 赞/ 78 阅读

相关树：红黑树

1，红黑树引入红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1，超过后需要进行左旋或者右旋操作再次对树进行平衡，虽然这样能够解决二叉树退化为链表的缺

╰半橙微兮°/ 2023年02月28日 01:25/ 0 赞/ 175 阅读

相关红黑树

红黑树的定义每个节点要么是红色，要么是黑色。根节点必须是黑色，每个叶子节点是黑色（叶子节点包含NULL）。红色节点不能连续（红色节点的孩子和父亲

Dear 丶/ 2022年12月13日 04:18/ 0 赞/ 38 阅读

相关红黑树

红黑树（Red Black Tree）是一种自平衡二叉查找树，红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能，它虽然

谁践踏了优雅/ 2022年06月15日 12:57/ 0 赞/ 520 阅读

相关红黑树

> 3.3 Balanced Search Trees > [http://algs4.cs.princeton.edu/33balanced/][http_algs4.c

╰+攻爆jí腚メ/ 2022年06月09日 12:48/ 0 赞/ 371 阅读

相关 Java Collections Framework - 红黑树

红黑树在Java中的应用在Java集合类中，TreeMap和TreeSet的底层就是基于红黑树实现的，在JDK 1.8中如果HashMap和ConcurrentHash

女爷i/ 2022年05月31日 14:19/ 0 赞/ 163 阅读

相关红黑树

红黑树概念红黑树，又被称为对称二叉B树。 [红黑树模型][Link 1] 其本质是一种二叉查找树，单它在二叉查找树的基础上额外添加了一个标记（颜色），同时具

拼搏现实的明天。/ 2022年04月10日 02:39/ 0 赞/ 462 阅读

相关红黑树

先Mark，后续补充： [https://juejin.im/entry/58371f13a22b9d006882902d][https_juejin.im_entry_58

柔情只为你懂/ 2022年01月30日 14:57/ 0 赞/ 365 阅读

相关红黑树

二叉查找树（BST） 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。下

川长思鸟来/ 2021年10月24日 01:48/ 0 赞/ 420 阅读

相关红黑树

1. 从 2-3 树说起一棵标准的 BST （二叉查找树 / 二叉搜索树）是长这个样子的： BST 其中，这棵二叉查找树中的每个结点也叫 2-结点，2-结点就表示树...

系统管理员/ 2020年11月29日 04:30/ 0 赞/ 867 阅读