平衡二叉樹一般指平衡樹（(Balance Tree）：它或者是一顆空樹，或者具有以下性質(zhì)的二叉樹：它的左子樹和右子樹的深度之差的絕對值不超過1，且它的左子樹和右子樹都是一顆平衡二叉樹。這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，刪除的時間復(fù)雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉(zhuǎn)會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩(wěn)定了很多。

常見的符合平衡二叉樹的有，B樹（多路平衡搜索樹）、AVL樹（二叉平衡搜索樹）等。平衡樹可以完成集合的一系列操作, 時間復(fù)雜度和空間復(fù)雜度相對于“2-3樹”要低，在完成集合的一系列操作中始終保持平衡，為大型數(shù)據(jù)庫的組織、索引提供了一條新的途徑。很顯然，平衡二叉樹是在二叉排序樹(BST)上引入的，就是為了解決二叉排序樹的不平衡性導(dǎo)致時間復(fù)雜度大大下降，那么AVL就保持住了(BST)的最好時間復(fù)雜度O(logn)，所以每次的插入和刪除都要確保二叉樹的平衡，那么怎么保持平衡呢？

一、B樹（多路平衡搜索樹）

多路平衡搜索樹一定程度上可以提高搜索效率，但是當(dāng)原序列有序時，例如序列 A = {1，2，3，4，5，6}，構(gòu)造二叉搜索樹。依據(jù)此序列構(gòu)造的二叉搜索樹為右斜樹，同時二叉樹退化成單鏈表，搜索效率降低為 O(n)。在此二叉搜索樹中查找元素 6 需要查找 6 次。

二叉搜索樹的查找效率取決于樹的高度，因此保持樹的高度最小，即可保證樹的查找效率。同樣的序列 A，將其改為圖 1.2 的方式存儲，查找元素 6 時只需比較 3 次，查找效率提升一倍?？梢钥闯霎?dāng)節(jié)點數(shù)目一定，保持樹的左右兩端保持平衡，樹的查找效率最高。

二、AVL樹（二叉平衡搜索樹）

AVL樹是高度平衡的二叉樹，具有如下幾個性質(zhì)：

1.可以是空樹。

2.假如不是空樹，任何一個結(jié)點的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對值不超過 1。

三、平衡因子

定義：某節(jié)點的左子樹與右子樹的高度(深度)差即為該節(jié)點的平衡因子（BF,Balance Factor），平衡二叉樹中不存在平衡因子大于 1 的節(jié)點。在一棵平衡二叉樹中，節(jié)點的平衡因子只能取 0 、1 或者 -1 ，分別對應(yīng)著左右子樹等高，左子樹比較高，右子樹比較高。

四、節(jié)點結(jié)構(gòu)

定義平衡二叉樹的節(jié)點結(jié)構(gòu)：

typedef struct AVLNode *Tree;

typedef int ElementType;

struct AVLNode{

    int depth; //深度，這里計算每個結(jié)點的深度，通過深度的比較可得出是否平衡

    Tree parent; //該結(jié)點的父節(jié)點

    ElementType val; //結(jié)點值

    Tree lchild;

    Tree rchild;

    AVLNode(int val=0) {

        parent = NULL;

        depth = 0;

        lchild = rchild = NULL;

        this->val=val;

    }

};

五、二叉平衡樹的應(yīng)用

智能電網(wǎng)中，與傳統(tǒng)路由協(xié)議不同，突發(fā)性擁塞不再是數(shù)據(jù)采集的主要風(fēng)險，風(fēng)險的新來源是數(shù)據(jù)流過度集中在網(wǎng)絡(luò)的關(guān)鍵節(jié)點而導(dǎo)致的擁塞。為此,提出了一種能夠?qū)崿F(xiàn)數(shù)據(jù)平衡的數(shù)據(jù)采集路由機(jī)制用以克服網(wǎng)絡(luò)擁塞。設(shè)計了基于平衡樹的路由算法(基于DBMM的路由算法,RA-DBMM)。有效地改善數(shù)據(jù)擁塞問題,提高系統(tǒng)可靠性和吞吐量。

平衡二叉樹大部分操作和二叉查找樹類似，這些樹形數(shù)據(jù)結(jié)構(gòu)之間其實都有想通之處，包括各種樹的算法也有異曲同工之妙。想學(xué)習(xí)更多的神奇的算法和數(shù)據(jù)結(jié)構(gòu)，本站的數(shù)據(jù)結(jié)構(gòu)和算法教程是你的不二選擇。