手动平衡 BST 树
我已经按照手工要求完成了树的平衡（bst>avl），我想知道这真的很容易，所以我不确定我是否做得正确。
a
/ \
b e3
/ \
e1 e2初始状态为： “a”是“b”（左）和“e3”（右）的父级，“b”是“e1”（左）和“e2”（右）的父级。
应用右旋转给我们：
b
/ \
e1 a
/ \
e2 e3'b'代替'a'，子代'e1'在左边，'a'子代在右边，'a'得到左边'b'的'e2'。
所以问题是：
- 如果 e1 本身是包含其他元素的子树或节点，我仍然可以进行这种旋转吗？
- 2. 如果e2和e3不存在，我还可以进行这种轮换吗？
实施例11； 12;16
16
/
13
/
10
初始状态：16 是 13 的父级，13 是 10 的父级。 我可以这样做吗：13 是 10（左）和 16（右）的父级
我知道这很简单，但假设很清楚，理论通常不会涵盖这些事情，但并不适合所有人。 感谢您的帮助，
I've done balancing of the tree(bst>avl) requested by hand and I wonder that it was really easy, so I am not sure whether I've done it correctly.
a
/ \
b e3
/ \
e1 e2initial state is:
'a' is parent of 'b'(left) and 'e3'(right), 'b' is a parent of 'e1'(left) and 'e2'(right).
applying right rotation gives us:
b
/ \
e1 a
/ \
e2 e3'b' in place of 'a' with child 'e1' on the left and 'a' child on the right, 'a' gets 'e2' of 'b' on the left.
So the questions:
- If e1 is itself a subtree or node containing other elements, can I still do this rotation?
- 2. If e2 and e3 are absent, can I still do this rotation?
example 11; 12;16
16
/
13
/
10
intial state: 16 is a parent of 13 and 13 is a parent of 10.
Can I do from it: 13 is a parent of 10(left) and 16(right)
I know it's simplistic, but theory often does not cover these thing assuming it's clear, well not for everyone.
Thanks for help,
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对一切都是肯定的，真的。考虑一下 order 属性：左后代 <节点和节点<右后裔。注意旋转如何保留这一点；将a和b与轮换前的e1、e2、e3进行比较，并检查轮换后的顺序和后代关系。在放弃之前我会让你考虑一下如何。
Yes to everything, really. Think about the order property: left descendants < node and node < right descendants. Note how the rotation preserves this; compare a and b to e1, e2 and e3 before the rotation, and check the order and descendent relationships after the rotation. I'll let you ponder how before giving it away.