關於AVL樹插入操作

Question

在AVL樹插入的標準過程中，插入一個新節點後，我們會從下到上進行調整，並且在這個過程中，子樹高度可能會增加一個（由於插入和旋轉操作），而子樹（高度增加一）時，仍然有左/右小孩的高度？如果是這樣，一個例子表示讚賞，如果沒有，如果有人能解釋爲什麼，這將是偉大的。謝謝。 :)

這裏是AVL樹的引用（https://en.wikipedia.org/wiki/AVL_tree）

問候， 林

Answer 1

插入後不可能讓子樹的左右子元素與高度變化保持一致。

讓我們考慮一個簡單的例子，在子樹中只有< 3個節點。平衡因子的possiblities是，

• +1 - 這是在子樹1左子根節點無權孩子
• -1 - 這是在子樹1右孩子沒有左孩子的根節點
• 0 - 子樹中的根節點在Right和Left中有1個節點。

對於平衡係數+1子樹

• 如果把它插入到正確的，我們都ok
• 如果我們插入到左邊，平衡因子變化爲2所以，我們需要以平衡樹，在這種情況下子樹的高度被改變。

對於平衡因子-1子樹

• 如果我們插入走後，我們都ok
• 如果我們插入正確，平衡因素的變化爲-2。所以我們需要平衡樹，在這種情況下，子樹的高度會發生變化。

對於平衡因子0子樹

• 如果我們插入到左邊，我們都ok。高度改變了，但子節點也改變了。
• 如果我們插入右邊，我們沒事。高度改變了，但子節點也改變了。

所以，不可能有高度變化，仍然有相同的左右兒童高度。

Answer 2

從Wikipedia Binary Tree page：

平衡二叉樹具有最小可能的最大高度（又名 深度），因爲對於任何給定數量的葉節點，葉節點被放置在儘可能最大的高度處。

一個常見的平衡樹結構是二叉樹結構，其中 每個節點的左和右子樹的高度相差不更 大於1

例如：

這是一個平衡的樹。

如果我們插入1它由1的高度增加然而，這又是一個平衡樹。由於左，右子樹的高度相差不超過1

BTW，AVL樹是一個平衡樹。所以插入後不可能失去平衡。因爲在每次插入之後，樹通過進行必要的旋轉來平衡自身。

我想你用錯了這個詞平衡了。您認爲平衡沒有高度差異，但最多隻有1高度差異的定義。

你的問題：

在AVL樹插入標準的過程中，是否有可能通過一個（因爲插入和旋轉操作的）子樹高度增加，而子樹（後高度增加一個），仍然有左/右兒童的高度？

如果我們將有哪些具有左，右分支相同的高度，如果我們將插入一個節點到左分支的葉節點，身高會增加，因爲樹的高度爲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)條件不可能是真的了。