AVL 添加元素时的问题

Question

我感觉 T3 的高度只可能为 h. 如果此时 T3 的高度是 h+1, 那么添加之前 T3 的高度也是 h+1, 那么添加之前的 x 的高度就是 h+2, 那么添加元素之后的 x 的高度就是 h+3 了, 和图中有冲突, 所以 T3 的高度只能为 h.

另外, 如果 T3 的高度只能为 h, 那么 x 的平衡因子就只能为 1 了. 我又尝试了一些例子, 在 LL 的情况下, 我没有找到根平衡因子为 2, 但左孩子平衡因子为 0 的情况. 在 RR 的情况下, 我也没有找到根平衡因子为 -2, 但右孩子平衡因子为 0 的情况.

是不是并不存在平衡因子为 0 的情况呢 ?

Answer 1

liuyubobobo 2020-04-01 15:36:08

我不是特别确定我有没有理解你的问题。

“T3 的高度也是 h+1, 那么添加之前的 x 的高度就是 h+2, 那么添加元素之后的 x 的高度就是 h+3 了。”

这是不一定的，向 x 中添加一个元素，x 的高度不一定上升。x 不一定是一棵满二叉树。

另外，这里所说的旋转操作的状态，只是当前整棵树的一种状态而已，不仅仅添加元素可能导致这种状态，删除操作也可能导致这种状态。

继续加油！：）

• 提问者 dyq666 #1

  > “T3 的高度也是 h+1, 那么添加之前的 x 的高度就是 h+2, 那么添加> 元素之后的 x 的高度就是 h+3 了。”
  
  这个我指的是在 LL 的条件下,  因为添加元素之后 y 的平衡因子从 1 变为 2 了, 所以 x 的高度肯定 + 1.
  
  > 另外，这里所说的旋转操作的状态，只是当前整棵树的一种状态而 
  > 已，不仅仅添加元素可能导致这种状态，删除操作也可能导致这种 
  > 状态。
  
  哦, 我只在添加的情景下思考了旋转操作. 可能学完删除就没有这个问题了, 谢谢 :)