已知一個長度為11的線性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，試回答下面問題
（1）將線性表元素依次插入一個空的平衡二叉樹，畫出所得平衡二叉樹，如果假設每個元素查找概率相同，則平均查找長度為多少？

?

(1)?插入12,?這是第一個結點,是根結點.

?

(2)?插入24,?比12大,作為12的右分支.

?

????12

?????\

??????24

?

(3)?插入36,?結點12的平衡因子BF變成-2(右子樹過高),要左旋(逆時針旋轉),

????此時,結點24成為根結點.

????平衡因子BF(Balance?Factor)就是:

????將二叉樹上結點的?左子樹深度?減去?右子樹深度的值.

?

????12??

?????\

??????24?????????24

???????\????????/??\

????????36?????12???36?

????????????????左旋后

?

(4)?插入90,?結點24的BF是-1,二叉樹仍然保持平衡.

?

??????24

?????/??\

????12???36?

??????????\

???????????90

?

(5)?插入52,?結點36的BF是-2,結點90的BF是+1,兩個符號不一致,結點90和52先右旋,

????此時,結點52的BF是-1,結點36的BF是-2,再對結點36,52,90進行左旋.

?

?

??????24?????????????24????????????????24

?????/??\???????????/??\??????????????/??\

????12???36????????12???36???????????12???52

??????????\??????????????\????????????????/?\

???????????90????????????52??????????????36??90

??????????/????????????????\

?????????52????????????????90

????????????????????右旋后?????????????左旋后

?

(6)?插入30,?結點52的BF是+1,結點24的BF是-2,兩個符號不一致,

????結點30,36和52先右旋,此時,結點36的BF是-1,結點24的BF是-2,

????結點12,24和36進行左旋.

?

???????24???????????????24???????????????????36

??????/??\?????????????/??\?????????????????/??\

?????12???52??????????12???36??????????????24???52

??????????/?\??????????????/?\????????????/?\????\

?????????36??90???????????30??52?????????12??30???90

????????/??????????????????????\

???????30??????????????????????90

???????????????????????右旋后???????????????左旋后

?

(7)?插入41,?二叉樹仍然保持平衡.

?

??????????36

????????/????\

???????24????52

??????/?\????/?\

????12??30??41??90

?

(8)?插入8,?二叉樹仍然保持平衡.

?

???????????36

?????????/????\

????????24????52

???????/?\????/?\

?????12??30??41??90

?????/

????8

?

(9)?插入10,?結點8的BF是-1,結點12的BF是+2,結點24的BF是+2,

????結點8和10先左旋,此時,結點10的BF是+1,結點12的BF是+2,

????對結點10,8,12進行右旋.

?

???????????36????????????????????36??????????????????36

?????????/????\????????????????/????\??????????????/?????\

????????24????52??????????????24????52????????????24?????52

???????/?\????/?\????????????/?\????/?\??????????/?\?????/?\

?????12??30??41??90????????12??30??41??90???????10??30??41??90

?????/?????????????????????/???????????????????/?\

????8?????????????????????10??????????????????8??12

?????\???????????????????/

??????10????????????????8

???????????????????????????????左旋后??????????????右旋后

?

(10)?插入38,?二叉樹仍然保持平衡.

?

??????????????36

??????????/????????\

?????????24????????52

????????/?\???????/??\

??????10???30????41??90

??????/?\???????/

?????8??12?????38

?

(11)?插入61,?二叉樹仍然保持平衡.

?

??????????????36

??????????/????????\

?????????24????????52

????????/?\???????/??\

??????10???30????41??90

??????/?\???????/????/

?????8??12?????38???61

?

????這就是最后得到的平衡二叉樹

?

???

二叉樹的總結點數?N=11

?

如果假設每個元素查找概率相同,平均查找長度是?log2(N)=log2(11),

表示以2為底,取11的對數.

總結

以上是生活随笔為你收集整理的简单的平衡二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。