1

我正在关注Algorithms Princetion robert et al 的参考资料,电子书来学习算法。我无法弄清楚红黑树中的删除,任何帮助都会很棒。这本书讨论了对删除进行编码,就像在 2-3 棵树中完成的那样。我无法建立相关性。谢谢

4

2 回答 2

1

参考维基百科,这里给出了详细的解释:

http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal

于 2013-06-30T09:46:08.390 回答
0

Sedgewick 的论文说得很漂亮,在我看来:http ://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

delete 背后的直觉是这样的:红黑树只是 2-3-4 树或 2-3 树的编码,具体取决于您如何实现它(红色链接用于构造 3- 和 4-节点使用普通的 2 节点)。删除时,我们在向下的过程中执行旋转,以确保最终从叶 3 节点或 4 节点中删除目标(这可以通过简单地删除目标元素来完成)。然后在返回树的过程中可能会有一些修复旋转以恢复树不变量。

干杯!

于 2013-07-01T23:25:44.193 回答