RedBlack树:我正在尝试理解删除redblack树中的节点？
RedBlack树:我正在尝试理解删除redblack树中的节点？
提问于 2013-06-30 17:39:22
我正在遵循Algorithms princetion robert et al, ebook的参考资料来学习算法。我不能弄清楚红黑树中的删除，任何帮助都是很好的。这本书谈到了按照2-3个树的方式对删除进行编码。我不能让correlation.thanks
回答 2
Stack Overflow用户
发布于 2013-06-30 17:46:08
参考维基百科，这里给出了详细的解释：
http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal
Stack Overflow用户
发布于 2013-07-02 07:25:44
在我看来，Sedgewick的论文说得很好：http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
delete背后的直觉是:红黑树只是2- 3- 4树或2-3树的编码，这取决于您如何实现它(红色链接用于使用普通的2-节点构造3-和4-节点)。在删除时，我们在向下的过程中执行轮换，以保证我们最终从叶3节点或4节点删除目标(这可以通过简单地删除目标元素来完成)。然后，在返回树的过程中可能存在一些修复旋转，以恢复树不变量。
干杯!
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17389031
复制相关文章
相似问题
腾讯云开发者
