红黑树的原理及特点有哪些?红黑树详解

TheDisguiser 2020-04-14 17:43:58 java常见问答 5927

学过数据结构的小伙伴们应该都知道二叉树的概念吧,二叉树有多种类型,如:完全二叉树、二叉搜索树、均衡二叉树、完美二叉树等;下面我们要了解的红黑树就是一颗近似平衡的二叉树,一起来看看吧。

红黑树的定义

红黑树,简称 R-B Tree。是一种不严格的平衡二叉查找树

顾名思义,在红黑树中的节点,一共要有两类,一类标记为黑色,一类标记为红色。除此之外,一棵红黑树还必须满足以下这样四个要求:

1. 红黑树根节点必须为黑色;

2. 红黑树每个叶子节点都要是黑色的空节点,也就是说,叶子节点不存储数据;

3. 在红黑树中任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;

4. 红黑树中每个节点,从该节点到达其可达叶子节点的所有路径,都要包含相同数目的黑色节点;

这里是两个红黑树的例子

红黑树的原理   特点   红黑树详解

为什么红黑树近似平衡?

首先,我们要知道二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树的高度大约是 log2n,所以如果要证明红黑树是近似平衡的,我们只需分析,红黑树的高度是否稳定地趋近 log2n 就好了。

我们来看个例子:假如我们将红色节点从红黑树中去掉,那单纯包含黑色节点的红黑树的高度会是多少呢?

在红色节点删除之后,一些节点就没有父节点了,它们会直接拿这些节点的祖父节点作为父节点。所以,之前的二叉树就变成了四叉树。

红黑树的原理   特点   红黑树详解

这时我们可以将有些节点拿出来组成一个完全二叉树,而完全二叉树的高度是 log2n ,很明显,我们的四叉树根本不会高于 log2n

我们现在知道只包含黑色节点的“黑树”的高度,那我们现在把红色节点加回去,高度会变成多少呢?

从以上的红黑树的例子与定义了解到,在红黑树中,红色节点不能够相邻,也就是说,有一个红色节点就要至少有一个黑色节点,将它与其他红色节点隔开。红黑树中包含最多黑色节点的路径不能超过 log2n,所以加入红色节点之后,最长路径不会超过 2log2n,也就是说,红黑树的高度近似 2log2n。

所以,得出红黑树的高度只比高度平衡的 AVL 树的高度(log2n)仅仅大了一倍,在性能上,下降得并不多。但是这样的结果其实不太精确,从实际上来说,还是红黑树的性能较好些。

以上就是本篇的所有内容了,想知道更多有关Java一些知识问答的相关内容,请多多关注本网站吧。