我正在关注Algorithms Princetion robert et al 的参考资料，电子书来学习算法。我无法弄清楚红黑树中的删除，任何帮助都会很棒。这本书讨论了对删除进行编码，就像在 2-3 棵树中完成的那样。我无法建立相关性。谢谢
问问题
86 次
2 回答
1
参考维基百科，这里给出了详细的解释：
于 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 回答