代码之家 › 专栏 › 技术社区 › Limer

在红黑树中插入_重新平衡

red-black-tree tree algorithm

Limer · 技术社区 · 7 年前

我不这么认为!

所以我们将父亲的颜色设置为黑色,叔叔的颜色设置为黑色,父亲的颜色设置为红色,并将父亲的父亲设置为当前节点,然后继续。

经过上述操作后,再次出现情况1。

让我们想象一下:如果它总是变成情况1,旋转的次数将不仅仅是2,甚至更多。

我的上述说法正确吗?我想证实我的想法。

1 回复 | 直到 7 年前

SoronelHaetir 7 年前

B(0%需要两次旋转)

b r(25%需要两次旋转)

b r r(0%需要两次旋转)

b b

b b r r(0%需要两次旋转)

在可以进行两次旋转的步骤中,也可以在不需要第二次旋转的情况下填充树。如果插入位置始终是最大值而不是随机值,则两个旋转插入的数量为0,但您将在大约50%的时间内旋转一次。

推荐文章

root · 计数算法

2 年前

Ash · 递归列表拆分和索引

3 年前

Someone · 如何实际删除节点?

3 年前

bb ef · 如何使用递归从列表中删除某些内容?python

7 年前

Linkmaster · 在用于BST的类中是否可能有类成员变量BST?

7 年前

Adam Morad · 方案更改树值

7 年前

A Akshat · 如何为函数中的结构分配动态内存插槽,该结构可以从程序中的任何位置访问

7 年前

johnny 5 · 角度将ViewChild绑定到类中的属性

7 年前

user2467011 · 为什么给定的二叉树是用空节点构造的?

7 年前

Yuki.kuroshita · 从二叉树中删除节点及其所有子节点,而不使用树数据结构

7 年前