• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            專注于c++

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              21 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(15)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            形態勻稱的二叉樹稱為平衡二叉樹 (Balanced binary tree) ,其嚴格定義是:
              一棵空樹是平衡二叉樹;若 T 是一棵非空二叉樹,其左、右子樹為 TL 和 TR ,令 hl 和 hr 分別為左、右子樹的深度。當且僅當
               ①TL 、 TR 都是平衡二叉樹;
               ② | hl - hr |≤ 1;
            時,則 T 是平衡二叉樹。
            【例】如圖 8.4 所示。
                     
                         (a)平衡二叉樹           (b)非平衡二叉樹
                                  圖8.3 平衡二叉樹與非平衡二叉樹
            相應地定義 hl - hr 為二叉平衡樹的平衡因子 (balance factor) 。因此,平衡二叉樹上所有結點的平衡因子可能是 -1 , 0 , 1 。換言之,若一棵二叉樹上任一結點的平衡因子的絕對值都不大于 1 ,則該樹是就平衡二叉樹。
            動態平衡技術
            1.動態平衡技術
            Adelson-Velskii 和 Landis 提出了一個動態地保持二叉排序樹平衡的方法,其基本思想是:
              在構造二叉排序樹的過程中,每當插入一個結點時,首先檢查是否因插入而破壞了樹的平衡性,如果是因插入結點而破壞了樹的平衡性,則找出其中最小不平衡子樹,在保持排序樹特性的前提下,調整最小不平衡子樹中各結點之間的連接關系,以達到新的平衡。通常將這樣得到的平衡二叉排序樹簡稱為 AVL 樹
            2.最小不平衡子樹
              以離插入結點最近、且平衡因子絕對值大于 1 的結點作根結點的子樹。為了簡化討論,不妨假設二叉排序樹的最小不平衡子樹的根結點為 A ,則調整該子樹的規律可歸納為下列四種情況:
            (1) LL 型:
              新結點 X 插在 A 的左孩子的左子樹里。調整方法見圖 8.5(a) 。圖中以 B 為軸心,將 A 結點從 B 的右上方轉到 B 的右下側,使 A 成為 B 的右孩子。
                  
                      圖8.5 平衡調整的4種基本類型(結點旁的數字是平衡因子)
            (2)RR 型:
              新結點 X 插在 A 的右孩子的右子樹里。調整方法見圖 8.5(b) 。圖中以 B 為軸心,將 A 結點從 B 的左上方轉到 B 的左下側,使 A 成為 B 的左孩子。
            (3)LR 型:
              新結點 X 插在 A 的左孩子的右子樹里。調整方法見圖 8.5(c) 。分為兩步進行:第一步以 X 為軸心,將 B 從 X 的左上方轉到 X 的左下側,使 B 成為 X 的左孩子, X 成為 A 的左孩子。第二步跟 LL 型一樣處理 ( 應以 X 為軸心 ) 。
            (4)RL 型:
              新結點 X 插在 A 的右孩子的左子樹里。調整方法見圖 8.5(d) 。分為兩步進行:第一步以 X 為軸心,將 B 從 X 的右上方轉到 X 的右下側,使 B 成為 X 的右孩子, X 成為 A 的右孩子。第二步跟 RR 型一樣處理 ( 應以 X 為軸心 ) 。
            【例】
            實際的插入情況,可能比圖 8.5 要復雜。因為 A 、 B 結點可能還會有子樹。現舉一例說明,設一組記錄的關鍵字按以下次序進行插入: 4 、 5 、 7 , 2 、 1 、 3 、 6 ,其生成及調整成二叉平衡樹的過程示于圖 8.6 。
              在圖 8.6 中,當插入關鍵字為 3 的結點后,由于離結點 3 最近的平衡因子為 2 的祖先是根結點 5 。所以,第一次旋轉應以結點 4 為軸心,把結點 2 從結點 4 的左上方轉到左下側,從而結點 5 的左孩子是結點 4 ,結點 4 的左孩子是結點 2 ,原結點 4 的左孩子變成了結點 2 的右孩子。第二步再以結點 4 為軸心,按 LL 類型進行轉換。這種插入與調整平衡的方法可以編成算法和程序,這里就不再討論了。

                     圖 8.6 二叉平衡樹插入結點 ( 結點旁的數字為其平衡因子 )
            posted on 2009-10-12 18:50 bellgrade 閱讀(7249) 評論(3)  編輯 收藏 引用 所屬分類: 數據結構算法

            Feedback

            # re: 平衡二叉樹 2011-06-15 16:43 vlisa
            謝謝  回復  更多評論
              

            # re: 平衡二叉樹 2011-08-08 16:38 maimai
            @vlisa
            第三圖貌似錯了  回復  更多評論
              

            # re: 平衡二叉樹[未登錄] 2011-10-19 14:35 1
            @maimai
            寫錯了個數  回復  更多評論
              

            99久久国产综合精品五月天喷水| 久久本道久久综合伊人| 97久久婷婷五月综合色d啪蜜芽| 久久99精品久久久大学生| 狠狠色噜噜色狠狠狠综合久久| 久久精品人人做人人爽97| 国内精品久久国产大陆| 91精品免费久久久久久久久| 办公室久久精品| 99久久国产宗和精品1上映| 麻豆精品久久精品色综合| 久久精品成人免费观看97| 久久久久亚洲精品日久生情| 国产成人香蕉久久久久| 亚洲日韩中文无码久久| 久久99热这里只有精品国产| 亚洲va久久久噜噜噜久久天堂| 久久精品国产99久久久香蕉 | 亚洲成色www久久网站夜月| 久久亚洲高清观看| 精品无码久久久久国产动漫3d| 国产精品欧美久久久久天天影视| 波多野结衣久久精品| 精品国产综合区久久久久久| 日产精品久久久久久久| 久久影院亚洲一区| 国产亚洲精午夜久久久久久| 国产精品美女久久久久久2018| 亚洲а∨天堂久久精品9966| 99久久无码一区人妻| 久久99精品国产99久久| 亚洲精品乱码久久久久66| 狠狠色综合网站久久久久久久高清| 性高朝久久久久久久久久| 久久国产视屏| 狠狠色综合久久久久尤物| 91久久精品电影| 国产精品成人无码久久久久久| 久久99热国产这有精品| 精品久久久久久中文字幕| 精品国产91久久久久久久|