AVL tree insert問題

我知道AVL的定義

但是今天拿到一個題目是這樣的

       MAR

      /   \ 

   AUG    MAY

   / \      \    

APR  JAN    NOV

    /   \

   DEC July

請問 insert FEB 的結果為何?

因為是初學者,可能我觀念還不通

所以請解釋一下步驟,謝謝!

2 Answers

Rating
  • 1 decade ago
    Favorite Answer

    (0) initial AVL tree

           MAR

          /   \ 

       AUG    MAY

       / \      \    

    APR  JAN    NOV

        /   \

       DEC July

    (1) insert FEB

           MAR

          /   \ 

       AUG    MAY

       / \      \    

    APR  JAN    NOV

        /   \

       DEC July

        \

        FEB

    (2) becaue AUG subtree is not AVL and it is in R-L case, right rotate the right subtree (JAN subtree) then a left rotate of AUG subtree

           MAR

          /   \ 

       AUG    MAY

       / \      \    

    APR  DEC    NOV

         / \

       (empty ) JAN

         / \

        FEB July

           MAR

          /   \ 

       DEC    MAY

       / \      \    

    AUG   JAN    NOV

    /  \   /  \

    APR(empty )FEB  July

  • Anonymous
    1 decade ago

    MAR

          /   \ 

       DEC    MAY

       / \      \    

    APR  JAN    NOV

      \  /   \

     AUG FEB  July

    1.這是要看字母的順序的-->這個不了解的話~就很難再講下去~SO可能要先搞懂這個步驟

    2.AVL TREE每一個節點的bf值不的超過2-->這個貴校老師上課應該有講~

    3.bf值超過2後~則要調整到每一個節點的bf值都不會超過2為止

    -------------------------------------------------------------------------

    上面那個圖不敢說太有把握~~錯了的話~~真的很抱歉~還請其他的大大指教~順便也可以給小弟偷學一下~~~

    說明的部份~應該沒有太大的錯誤~

    最後~~也是最重要的:

    希望這不是作業~我不希望幫你完成的是作業~><這樣我會覺得很冏

    2009-12-14 19:15:28 補充:

    MAR 自己會歪掉~不知道為什麼~~~

    2009-12-14 19:21:54 補充:

    再補充一下

    順序依次為~左小孩較小-父母次之-右小孩較大(小弟的老師是都這樣稱呼他們~~煩請各位專

    家大大們見諒這個不是很正式的稱呼法~也許有更好的稱呼~但小弟已經習慣成自然囉!)

    Source(s): 我自己+課本
Still have questions? Get your answers by asking now.