AVL 添加元素时的问题
来源：12-4 旋转操作的基本原理
dyq666
2020-04-01
我感觉 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 的情况呢 ?
写回答
1回答
-
我不是特别确定我有没有理解你的问题。
“T3 的高度也是 h+1, 那么添加之前的 x 的高度就是 h+2, 那么添加元素之后的 x 的高度就是 h+3 了。”
这是不一定的，向 x 中添加一个元素，x 的高度不一定上升。x 不一定是一棵满二叉树。
另外，这里所说的旋转操作的状态，只是当前整棵树的一种状态而已，不仅仅添加元素可能导致这种状态，删除操作也可能导致这种状态。
继续加油！：）
012020-04-01
相似问题