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

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

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

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

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

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

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

1.可以是空樹。

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

三、平衡因子

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

四、節點結構

定義平衡二叉樹的節點結構：

typedef struct AVLNode *Tree;

typedef int ElementType;

struct AVLNode{

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

    Tree parent; //該結點的父節點

    ElementType val; //結點值

    Tree lchild;

    Tree rchild;

    AVLNode(int val=0) {

        parent = NULL;

        depth = 0;

        lchild = rchild = NULL;

        this->val=val;

    }

};

五、二叉平衡樹的應用

智能電網中，與傳統路由協議不同，突發性擁塞不再是數據采集的主要風險，風險的新來源是數據流過度集中在網絡的關鍵節點而導致的擁塞。為此,提出了一種能夠實現數據平衡的數據采集路由機制用以克服網絡擁塞。設計了基于平衡樹的路由算法(基于DBMM的路由算法,RA-DBMM)。有效地改善數據擁塞問題,提高系統可靠性和吞吐量。

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