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

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

red-black-tree tree algorithm

0

Limer · 技术社区 · 7 年前

我不这么认为!

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

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

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

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

1 回复 | 直到 7 年前

1

0

SoronelHaetir 6 年前

B(0%需要两次旋转)

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

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

b b

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

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

推荐文章

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

7 年前

ideasman42 · 哪些操作可以通过将每个节点的“父节点”存储在红黑树中来简化?

7 年前

overexchange · 二进制堆数据结构-应用程序

8 年前

Feek · 红黑树~1个子删除

8 年前