红黑树中的旋转操作
一直在使用 Eric Roberts 的《编程抽象》教科书来强化 DSA 技能。有一个实施红黑树的练习。还有一个图红黑树中的旋转 我不明白为什么左边的树是右边树的镜像版本，满足成为合法红黑树的条件。从根到左的所有路径必须包含相同数量的黑色节点。 在图片中，我用红色突出显示了路径。 N2-> N1-> T3 给我们一个黑色节点，不包括空指针 T3。但是N2-> N1-> N4 - 用绿色突出显示给出两个黑色节点。矛盾。 是否必须对左树执行一些其他操作才能使其满足所有 RB 树属性？
Have been using Eric Roberts' Programming Abstractions textbook to strengthening DSA skills. There is an exercise to implement Red-Black tree. And there is a figure Rotations in a red black tree.
I don't see why the tree on the left, which is a mirrored version of the tree on the right satisfy conditions for being a legitimate Red -Black tree. All paths from the root to a left must contain the same number of black nodes.
In the picture I highlighted the path with red. N2 -> N1 -> T3 gives us one black node, excluding null pointer T3. But N2 -> N1 -> N4 - highlighted with green gives two black nodes. Contradiction.
Must some other operations be performed on the left tree to make it satisfy all R-B trees properties?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我是盲目的，因此无法直接对您发布的图片发表评论。但是，执行插入或删除操作时，树可能会（但不需要）失衡。只有当完成插入或删除修复时，才确保树木条件有效。没有序列，有效树上的单个旋转本身会导致不同的有效树。
您是否确定图形不简单地说明树旋转操作的含义，而没有评论所得树是否有效？
I am blind and so cannot comment directly on the pictures you've posted. However, when an insert or remove operation is performed the tree may (but need not) become imbalanced. Only when the insert or remove fix-up is complete are you guaranteed that the tree conditions will be valid. There is no sequence where a single rotation on a valid tree, by itself, will result in a different valid tree.
Are you certain that the graphic is not simply illustrating what is meant by the tree rotation operation without commenting on whether the resulting tree is valid?