红黑树 - 删除具有两个非叶子子节点的节点
我一直在实现我自己版本的红黑树，主要基于维基百科的算法（http ://en.wikipedia.org/wiki/Red-black_tree）。它的大部分内容相当简洁，但有一个部分我想澄清一下。
当从具有 2 个非叶（非 NULL）子节点的树中删除节点时，它表示将任一侧的子节点移动到可删除节点中，并删除该子节点。
基于此，我对从哪一边删除有点困惑。我是随机选择一边，还是交替选择一边，还是在以后每次删除时都坚持同一边？
I've been implementing my own version of a red-black tree, mostly basing my algorithms from Wikipedia (http://en.wikipedia.org/wiki/Red-black_tree). Its fairly concise for the most part, but there's one part that I would like clarification on.
When erasing a node from the tree that has 2 non-leaf (non-NULL) children, it says to move either side's children into the deletable node, and remove that child.
I'm a little confused as to which side to remove from, based on that. Do I pick the side randomly, do I alternate between sides, or do I stick to the same side for every future deletion?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果您对输入数据没有先验知识，您就无法知道哪一方对于成为新的中间节点或新的子节点更有利。
因此，您可以应用最适合您的规则（最容易编写/计算 - 可能“始终采用左边的规则”）。采用随机方案通常只会引入更多不需要的计算。
If you have no prior knowledge about your input data, you cannot know which side is more benefitial of being the new intermediate node or the new child.
You can therefore just apply the rule that fits you most (is easiest to write/compute -- probably "always take the left one"). Employing a random scheme typically just introduces more unneeded computation.