AVL樹插入問題

我正在觀看IIT關於數據結構的講座（Dr.naveen garg）關於AVL樹。AVL樹插入問題

Screen shot

我的問題：爲什麼T2的高度不能（H-1）？

2011-03-07 3m masr

你確定在演講中他沒有提到目前的情況是插入淺層子樹嗎？他有沒有說圖中四個標記樹的高度是多少？另外，幻燈片還說「x保持平衡」;如果是這種情況，ht（T_2）不能是h-1，因爲插入後的ht（T_1）是h + 1，因此不平衡。 – 2011-03-07 01:22:02

X保持平衡是我正確的問題。爲什麼X必須保持平衡？ – 2011-03-07 01:26:10

我不知道。他在演講中有沒有提到這件事？這可能是因爲他假定'x'下的插入是一個遞歸的AVL插入，所以在原始插入之後，如果需要的話，它將被重新平衡。 – 2011-03-07 01:37:11

假定樹插入後沒有旋轉而平衡。
如果旋轉發生 - 這是一個不同的情況，你用ROTATION處理它，我從"Since X remains balanced.."中計算出這是假設，並且我們在這裏顯示只有在這種情況下樹才保持平衡。

2011-03-20 22:03:34 amit

如果ht（T2）像你說的那樣是（h-1），那麼在插入之後樹會不平衡。這不是問題中假設的一部分。

因爲x的平衡係數現在是2.因此輪換將不得不發生。

2017-07-10 05:52:25 muahcheeee

回答