• <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ù)  更多評論
              

            久久er热视频在这里精品| 久久久久久久97| 99久久精品国产综合一区| 久久免费小视频| 综合人妻久久一区二区精品| 亚洲国产精品成人久久| 亚洲一区中文字幕久久| 久久av高潮av无码av喷吹| 亚洲国产精品无码久久| 久久精品免费观看| 偷窥少妇久久久久久久久| 精品久久久久久国产| 狠狠色伊人久久精品综合网| 久久久噜噜噜久久中文字幕色伊伊| 久久国产精品久久| 亚洲&#228;v永久无码精品天堂久久| 一97日本道伊人久久综合影院| 国产精品久久亚洲不卡动漫| 97久久婷婷五月综合色d啪蜜芽| 精品久久无码中文字幕| 国产成人久久精品一区二区三区| 国产精品久久久久久福利漫画| 人人狠狠综合久久亚洲| 99re久久精品国产首页2020| 久久精品国产久精国产一老狼| 97久久精品人人做人人爽| 无码AV波多野结衣久久| 99久久香蕉国产线看观香| 精品人妻伦九区久久AAA片69| 久久人人爽人人爽人人片AV不 | 久久久精品一区二区三区| 久久久久国产精品人妻| 久久综合九色综合久99| 色天使久久综合网天天| 久久久久久久综合综合狠狠| 日本久久中文字幕| 精品国产一区二区三区久久蜜臀| www亚洲欲色成人久久精品| 国产成人AV综合久久| 青青热久久综合网伊人| 久久这里只有精品久久|