data-structures - 手动平衡 BST 树

Question

我已经完成了手动请求的树（bst>avl）的平衡，我想知道这真的很容易，所以我不确定我是否正确地完成了它。

        一个
       / \
      b e3
     / \
    e1 e2

初始状态是：“a”是“b”（左）和“e3”（右）的父级，“b”是“e1”（左）和“e2”（右）的父级。

应用右旋转给我们：

        b
       / \
     e1a
         / \
       e2 e3

'b' 代替 'a'，左边有子 'e1'，右边有 'a' 子，'a' 在左边得到 'b' 的 'e2'。

所以问题：

1. 如果 e1 本身是包含其他元素的子树或节点，我还能做这种旋转吗？
2. 2. 如果没有e2和e3，我还能做这个轮换吗？

例 11；12;16

     16
     /
   13
  /
10

初始状态：16 是 13 的父级，13 是 10 的父级。我可以这样做：13 是 10（左）和 16（右）的父级

我知道这很简单，但是假设它很清楚，理论通常不会涵盖这些事情，但并不适合所有人。感谢帮助，

Answer 1

是的，真的。考虑 order 属性：左后代 < 节点和节点 < 右后代。注意旋转如何保持这一点；将 a 和 b 与轮换前的 e1、e2 和 e3 进行比较，并检查轮换后的顺序和后代关系。在放弃之前，我会让你思考如何。