• <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++博客 :: 首頁 :: 聯(lián)系 :: 聚合  :: 管理
              21 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(15)

            我參與的團(tuán)隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

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

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

            Feedback

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

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

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

            www.久久热.com| 国产精品无码久久久久久| 精品熟女少妇av免费久久| 国产人久久人人人人爽| 99久久99这里只有免费的精品| 九九精品99久久久香蕉| 久久97精品久久久久久久不卡| 国产L精品国产亚洲区久久| 精品熟女少妇aⅴ免费久久| 久久亚洲精品国产精品婷婷| 亚洲精品乱码久久久久久中文字幕| 国产精品久久久久久搜索| 一本久久a久久精品综合香蕉| 国产精品久久久久久一区二区三区| 久久精品国产一区二区电影| 久久精品国产亚洲av麻豆色欲| 中文字幕无码久久精品青草| 国产精品久久久99| 久久免费精品一区二区| 久久精品国产清高在天天线| 日韩人妻无码一区二区三区久久99 | 久久精品99久久香蕉国产色戒| 国产欧美久久久精品影院| 精品熟女少妇aⅴ免费久久| 国产精品99久久久久久人| 激情久久久久久久久久| 91精品国产综合久久香蕉| 国内精品久久人妻互换| 国产美女久久久| 欧美麻豆久久久久久中文| 国产精品久久久久蜜芽| 久久久久亚洲av无码专区| 欧美久久精品一级c片片| 一本伊大人香蕉久久网手机| 久久久久久噜噜精品免费直播| 欧美精品九九99久久在观看| 99久久精品日本一区二区免费| 久久不射电影网| 人妻精品久久久久中文字幕69| 97精品久久天干天天天按摩| 久久婷婷五月综合色奶水99啪|