删除根节点后重新平衡 2-3 树的正确方法
Proper way to Re-Balance a 2-3 Tree after deleting the root node
目标是从根节点中删除 22 并重新平衡树。
首先我删除了 22,并用它的顺序后继者 28 替换它。
其次,我通过将空节点向左移动来重新平衡生成的树。结果树如下。
上移28是否正确,最后我是否正确平衡了左侧?
22,34
/ | \
16 28 37
/ \ / \ / \
15 21 25 33 35 43
[28],34
/ | \
16 * 37
/ \ / \ / \
15 21 25 33 35 43
34
/ \
16,28 37
/ | \ / \
15 21,25 33 35 43
谢谢!
从
中删除22
22,34
/ | \
16 28 37
/ \ / \ / \
15 21 25 33 35 43 ,
我们用它的 in-order 继任者 25
替换它,留下一个洞 (*
)。
25,34
/ | \
16 28 37
/ \ / \ / \
15 21 * 33 35 43
我们不能通过借用来修复这个洞,所以我们将它的 parent 合并到它的兄弟中,把洞向上移动。
25,34
/ | \
16 * 37
/ \ | / \
15 21 28,33 35 43
这个洞现在有两个兄弟,所以我们可以重新分配 parent 的其中一个钥匙。
34
/ \
16,25 37
/ | \ / \
15 21 28,33 35 43
(我在this set of lecture notes工作。除非是为了考试,否则不要费心记住这里的细节。即便如此......我真的希望数据结构课程没有强调平衡搜索树到他们所做的程度。)
目标是从根节点中删除 22 并重新平衡树。
首先我删除了 22,并用它的顺序后继者 28 替换它。
其次,我通过将空节点向左移动来重新平衡生成的树。结果树如下。
上移28是否正确,最后我是否正确平衡了左侧?
22,34
/ | \
16 28 37
/ \ / \ / \
15 21 25 33 35 43
[28],34
/ | \
16 * 37
/ \ / \ / \
15 21 25 33 35 43
34
/ \
16,28 37
/ | \ / \
15 21,25 33 35 43
谢谢!
从
中删除22
22,34
/ | \
16 28 37
/ \ / \ / \
15 21 25 33 35 43 ,
我们用它的 in-order 继任者 25
替换它,留下一个洞 (*
)。
25,34
/ | \
16 28 37
/ \ / \ / \
15 21 * 33 35 43
我们不能通过借用来修复这个洞,所以我们将它的 parent 合并到它的兄弟中,把洞向上移动。
25,34
/ | \
16 * 37
/ \ | / \
15 21 28,33 35 43
这个洞现在有两个兄弟,所以我们可以重新分配 parent 的其中一个钥匙。
34
/ \
16,25 37
/ | \ / \
15 21 28,33 35 43
(我在this set of lecture notes工作。除非是为了考试,否则不要费心记住这里的细节。即便如此......我真的希望数据结构课程没有强调平衡搜索树到他们所做的程度。)