红黑树的高度和深度区别,红黑树的原理动态图

首页 > 经验 > 作者:YD1662022-11-14 14:34:32

当我们插入值为66的节点的时候,示意图如下:

红黑树的高度和深度区别,红黑树的原理动态图(9)

很明显,这个时候结构依然遵循着上述5大特性,无需启动自动平衡机制调整节点平衡状态。

如果再向里面插入值为51的节点呢,这个时候红黑树变成了这样。

红黑树的高度和深度区别,红黑树的原理动态图(10)

这样的结构实际上是不满足性质4的,红色两个子节点必须是黑色的,而这里49这个红色节点现在有个51的红色节点与其相连。

这个时候我们需要调整这个树的结构来保证红黑树的平衡。

首先尝试将49这个节点设置为黑色,如下示意图。

红黑树的高度和深度区别,红黑树的原理动态图(11)

这个时候我们发现黑高是不对的,其中 60-56-45-49-51-null 这条路径有 4 个黑节点,其他路径的黑色节点是 3 个。

接着调整红黑树,我们再次尝试把45这个节点设置为红色的,如下图所示:

红黑树的高度和深度区别,红黑树的原理动态图(12)

上一页12345下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.