关于AVL树的插入操作
about AVL tree insertion operation
AVL树插入的标准过程中，我们插入一个新节点后，会从下往上做调整，在这个过程中，是否有可能子树的高度增加一（因为插入和旋转操作），而子树（高度增加一后）仍然具有与 left/right 子树相同的高度？如果是这样，一个例子表示赞赏，如果不是，如果有人能解释原因，那就太好了。谢谢。 :)
这里引用了AVL树(https://en.wikipedia.org/wiki/AVL_tree)
此致，
林
来自 Wikipedia Binary Tree page：
A balanced binary tree has the minimum possible maximum height (a.k.a.
depth) for the leaf nodes, because for any given number of leaf nodes
the leaf nodes are placed at the greatest height possible.
One common balanced tree structure is a binary tree structure in which
the left and right subtrees of every node differ in height by no more
than 1
例如：
这是一棵平衡树。
如果我们插入1，它的高度会增加1。但它又是一棵平衡树。因为左右子树的高度相差不超过1.
顺便说一句，AVL树是一种自平衡的二叉搜索树。所以插入后不可能失去平衡。因为每次插入后，树都会通过必要的旋转来平衡自身。
我认为您错误地使用了术语 平衡。你认为平衡是没有高度差，但在定义上最多只有 1 个高度差。
您的问题：
In the standard process of AVL tree insertion, is it possible a sub-tree height increase by one (because of insertion and rotation operation), while the sub-tree (after height increase by one), still have the same height of left/right child?
如果我们有一棵左右分支高度相同的树，如果我们将一个节点插入到左分支的叶节点中，高度会增加，因为树的高度是maximum(height(left_branch, right_branch)).因为经过这个操作height(left_branch)等于height(right_branch)+1。所以，他们不可能相等。
简而言之，你的前提是height(left_branch) == height(right_branch)
您的操作是increasing height of left_branch by 1
所以 height(left_branch) == height(right_branch) 条件不再成立。
插入后不可能让sub-tree的左右child随着高度的变化保持不变。
让我们考虑一个简单的例子，在 sub-tree 中只有 <3 个节点。平衡因子的可能性是，
- +1 - 这是子树中的根节点，有 1 个左 Child 没有右 child
- -1 - 这是子树中的根节点，有 1 个右 Child 没有左 child
- 0 - 子树中的根节点在左右各有 1 个节点。
对于平衡因子为+1的子树，
- 如果我们往右插入就ok
- 如果我们向左插入，平衡因子变为2。所以我们需要平衡树，在这种情况下子树的高度会改变。
对于平衡因子为-1的子树，
- 如果我们插入左边就可以了
- 如果我们向右插入，平衡系数变为-2。所以我们需要平衡树，在这种情况下子树的高度会改变。
对于平衡因子为 0 的子树，
- 如果我们插入到左边，我们就可以了。高度已更改，但 child 节点也已更改。
- 如果我们插入右边，我们就可以了。高度已更改，但 child 节点也已更改。
因此，不可能在改变高度的同时保持左右 child 高度相同。
AVL树插入的标准过程中，我们插入一个新节点后，会从下往上做调整，在这个过程中，是否有可能子树的高度增加一（因为插入和旋转操作），而子树（高度增加一后）仍然具有与 left/right 子树相同的高度？如果是这样，一个例子表示赞赏，如果不是，如果有人能解释原因，那就太好了。谢谢。 :)
这里引用了AVL树(https://en.wikipedia.org/wiki/AVL_tree)
此致， 林
来自 Wikipedia Binary Tree page：
A balanced binary tree has the minimum possible maximum height (a.k.a. depth) for the leaf nodes, because for any given number of leaf nodes the leaf nodes are placed at the greatest height possible.
One common balanced tree structure is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1
例如：
这是一棵平衡树。
如果我们插入1，它的高度会增加1。但它又是一棵平衡树。因为左右子树的高度相差不超过1.
顺便说一句，AVL树是一种自平衡的二叉搜索树。所以插入后不可能失去平衡。因为每次插入后，树都会通过必要的旋转来平衡自身。
我认为您错误地使用了术语 平衡。你认为平衡是没有高度差，但在定义上最多只有 1 个高度差。
您的问题：
In the standard process of AVL tree insertion, is it possible a sub-tree height increase by one (because of insertion and rotation operation), while the sub-tree (after height increase by one), still have the same height of left/right child?
如果我们有一棵左右分支高度相同的树，如果我们将一个节点插入到左分支的叶节点中，高度会增加，因为树的高度是maximum(height(left_branch, right_branch)).因为经过这个操作height(left_branch)等于height(right_branch)+1。所以，他们不可能相等。
简而言之，你的前提是height(left_branch) == height(right_branch)
您的操作是increasing height of left_branch by 1
所以 height(left_branch) == height(right_branch) 条件不再成立。
插入后不可能让sub-tree的左右child随着高度的变化保持不变。
让我们考虑一个简单的例子，在 sub-tree 中只有 <3 个节点。平衡因子的可能性是，
- +1 - 这是子树中的根节点，有 1 个左 Child 没有右 child
- -1 - 这是子树中的根节点，有 1 个右 Child 没有左 child
- 0 - 子树中的根节点在左右各有 1 个节点。
对于平衡因子为+1的子树，
- 如果我们往右插入就ok
- 如果我们向左插入，平衡因子变为2。所以我们需要平衡树，在这种情况下子树的高度会改变。
对于平衡因子为-1的子树，
- 如果我们插入左边就可以了
- 如果我们向右插入，平衡系数变为-2。所以我们需要平衡树，在这种情况下子树的高度会改变。
对于平衡因子为 0 的子树，
- 如果我们插入到左边，我们就可以了。高度已更改，但 child 节点也已更改。
- 如果我们插入右边，我们就可以了。高度已更改，但 child 节点也已更改。
因此，不可能在改变高度的同时保持左右 child 高度相同。