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

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

一、B樹(shù)（多路平衡搜索樹(shù)）

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

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

二、AVL樹(shù)（二叉平衡搜索樹(shù)）

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

1.可以是空樹(shù)。

2.假如不是空樹(shù)，任何一個(gè)結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)都是平衡二叉樹(shù)，并且高度之差的絕對(duì)值不超過(guò) 1。

三、平衡因子

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

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

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

typedef struct AVLNode *Tree;

typedef int ElementType;

struct AVLNode{

    int depth; //深度，這里計(jì)算每個(gè)結(jié)點(diǎn)的深度，通過(guò)深度的比較可得出是否平衡

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

    ElementType val; //結(jié)點(diǎn)值

    Tree lchild;

    Tree rchild;

    AVLNode(int val=0) {

        parent = NULL;

        depth = 0;

        lchild = rchild = NULL;

        this->val=val;

    }

};

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

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

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