形態(tài)勻稱的二叉樹稱為平衡二叉樹 (Balanced binary tree) ，其嚴(yán)格定義是：
一棵空樹是平衡二叉樹；若 T 是一棵非空二叉樹，其左、右子樹為 TL 和 TR ，令 hl 和 hr 分別為左、右子樹的深度。當(dāng)且僅當(dāng)
①TL 、 TR 都是平衡二叉樹；
② ｜ hl － hr ｜≤ 1；
時(shí)，則 T 是平衡二叉樹。
【例】如圖 8.4 所示。
（a）平衡二叉樹 （b）非平衡二叉樹
圖8.3 平衡二叉樹與非平衡二叉樹
相應(yīng)地定義 hl － hr 為二叉平衡樹的平衡因子 (balance factor) 。因此，平衡二叉樹上所有結(jié)點(diǎn)的平衡因子可能是 -1 ， 0 ， 1 。換言之，若一棵二叉樹上任一結(jié)點(diǎn)的平衡因子的絕對(duì)值都不大于 1 ，則該樹是就平衡二叉樹。
動(dòng)態(tài)平衡技術(shù) 1.動(dòng)態(tài)平衡技術(shù)Adelson-Velskii 和 Landis 提出了一個(gè)動(dòng)態(tài)地保持二叉排序樹平衡的方法，其基本思想是：
在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹的平衡性，如果是因插入結(jié)點(diǎn)而破壞了樹的平衡性，則找出其中
最小不平衡子樹，在保持排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的連接關(guān)系，以達(dá)到新的平衡。通常將這樣得到的平衡二叉排序樹簡(jiǎn)稱為
AVL 樹。
2.最小不平衡子樹 以離插入結(jié)點(diǎn)最近、且平衡因子絕對(duì)值大于 1 的結(jié)點(diǎn)作根結(jié)點(diǎn)的子樹。為了簡(jiǎ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)可能還會(huì)有子樹。現(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ù)字為其平衡因子 )