平衡二叉樹和二叉排序樹并沒有直接的關系，但是二叉排序樹的查找效率與二叉樹的形態(tài)有關，所有當我們希望二叉排序樹的形態(tài)是均勻的時候，這樣的二叉樹就被稱為平衡二叉樹。

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設,雷山企業(yè)網(wǎng)站建設,雷山品牌網(wǎng)站建設,網(wǎng)站定制,雷山網(wǎng)站建設報價,網(wǎng)絡營銷,網(wǎng)絡優(yōu)化,雷山網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。

1. 二叉排序樹

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。

二叉排序樹定義：

二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：

若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；若右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；左、右子樹也分別為二叉排序樹。

如圖下圖所示就是一棵二叉排序樹：

對二叉排序樹進行中序遍歷，便可得到一個按關鍵字排序的序列，如對上圖進行一次中序遍歷可得到一個有序序列：10，42，45，55，58，63，67，70，83，90，98

二叉排序樹的查找分析

就查找的平均時間性能而言，二叉排序樹上的查找與折半查找類似，但就維護表的有序性而言，二叉排序樹更高效，因為它無需移動節(jié)點，只需修改指針即可完成二叉排序樹的插入和刪除操作。

二叉排序樹查找在在最壞的情況下，需要的查找時間取決于樹的深度：

當二叉排序樹接近于滿二叉樹時，其深度為$lo{g}_{2}n$log2n ,因此最壞情況下的查找時間為O($lo{g}_{2}n$log2n)，與折半查找是同數(shù)量級的。當二叉樹如下圖所示形成單枝樹時，其深度為n，最壞情況下查找時間為O(n)，與順序查找屬于同一數(shù)量級。

所以為了保證二叉排序樹查找有較高的查找速度，希望該二叉樹接近于滿二叉樹，或者二叉樹的每一個節(jié)點的左、右子樹深度盡量相等2. 平衡二叉樹

通過上面的分析可知，二叉排序樹的查找效率與二叉樹的形態(tài)有關，我們希望二叉排序樹的形態(tài)是均勻的，這樣的二叉樹稱為平衡二叉樹。

平衡二叉樹定義
平衡二叉樹（Balanced Binary Tree），它是一棵空樹，或者是具有以下性質：它的左右兩個子樹的深度差的絕對值不超過1；它的左右兩個子樹也分別是平衡二叉樹。

將二叉樹節(jié)點的左子樹的深度減去它的右子樹的深度稱為平衡因子BF，則平衡二叉樹上所有節(jié)點的平衡因子只可能是-1、0和1，如下圖左邊的為平衡二叉樹，右邊的為非平衡二叉樹。

因為平衡二叉樹上任何節(jié)點的左、右子樹的深度之差都不會超過1，可以證明它的深度和n個節(jié)點的完全二叉樹的深度$?lo{g}_{2}n?$?log2n?+1是同數(shù)量級的。因此，它的平均查找次數(shù)也是和$?lo{g}_{2}n?$?log2n?+1同數(shù)量級的。

要構造一棵平衡二叉樹，Georgii M. Adelson-Velskii 和 Evgenii M. Landis 提出了一種動態(tài)保持二叉平衡樹的方法，其基本思想是：在構造二叉排序樹的時候，每當插入一個節(jié)點時，先檢查是否因插入節(jié)點而破壞了樹的平衡性，如果是，則找出其中最小不平衡子樹，在保持排序樹的前提下，調整最小不平衡子樹中各節(jié)點之間的連接關系，以達到新的平衡，所以這樣的平衡二叉樹簡稱AVL樹。其中最小平衡子樹是指：離插入節(jié)點最近，且平衡因子絕對值大于1的節(jié)點作為根節(jié)點的子樹。

調整最小不平衡子樹一般有四種情況：單向右旋(LL型)： 插入位置為左子樹的左子樹，以左子樹為軸心，進行單次向右旋轉，如下圖所示。節(jié)點旁邊的數(shù)字為該節(jié)點的平衡因子，I節(jié)點為當前插入節(jié)點(如果I節(jié)點處于正中，則表示I節(jié)點既可以是左孩子也可以是右孩子。

注意LL型，以中間節(jié)點為軸心進行旋轉。為什么這里I為BL左孩子不能將B-BL-I作為LL型，是因為A節(jié)點才是離I節(jié)點最近的平衡因子絕對值>1的子樹，其余節(jié)點的平衡因子絕對值都沒有超過1；同理當I為BL右孩子，也不能將B-BL-I作為LR型。

2. 單向左旋(RR型)： 插入位置為右子樹的右子樹，右子樹為軸心，進行單次向左旋轉

注意RR型，以中間節(jié)點為軸心進行旋轉。這里I為左右子樹并不影響其實RR型，原理同上。

3. 雙向旋轉先左后右(LR型)：插入位置為左子樹的右子樹，要進行兩次旋轉，先向左旋轉，再向右旋轉。

插入節(jié)點為左孩子：注意為什么不能B-C-I作為子樹將其定為RL型，原理同RR型中的解釋，對于LR型，，是以R端或者L靠近插入節(jié)點端作為旋轉軸心（如下圖相當于先旋轉以B為根的子樹后，成為了LL型，再旋轉以A為根的子樹）。

插入節(jié)點為右孩子：

4. 雙向旋轉先右后左(RL型)：插入位置為右子樹的左子樹，進行兩次調整，先右旋轉再左旋轉；處理情況與LR類似。

插入節(jié)點為左孩子：

插入節(jié)點為右孩子：

經(jīng)過上面的我們可以發(fā)現(xiàn)，平衡因子與類型有很大的關系，需要以離插入節(jié)點最近且平衡因子絕對值>1的節(jié)點作為根節(jié)點的子樹進行判定是哪種類型。

練習

如下圖所示，先插入節(jié)點2后，成為LL型，然后整體右旋處理后平衡。

再依次插入8和6之后，節(jié)點5的平衡因子絕對值>1，成為RL型，所以先以5為根節(jié)點，將其子樹8-6右旋（成為RR型），然后將5為根節(jié)點的整棵樹再左旋。

繼續(xù)插入節(jié)點9后，節(jié)點4的平衡因子>1，成為RR型，所以以4為根節(jié)點，將整體左旋。

分享文章：平衡二叉樹和二叉排序樹的關系
文章路徑：http://weahome.cn/article/cjideo.html