AVL簡稱平衡二叉樹，縮寫為BBST，由蘇聯數學家 Adelse-Velskil 和 Landis 在 1962 年提出。

二叉樹是動態查找的典范，但在極限情況下，二叉樹的查找效果等同于鏈表，而平衡二叉樹可以完美的達到${\log }_{2}n$。

一直想深入的研究一下，并手寫平衡二叉樹的插入、刪除代碼。

可惜的是，國內數據結構的神級教材：閻蔚敏老師主編《數據結構》一書中并未看到關于AVL樹的代碼。

例子：

將17，9，2，12，14，26，33，15，40，23，25一次插入到一棵初始化為空的AVL樹中，畫出該二叉平衡樹。

解：過程和結果如下圖所示。

所謂平衡二叉樹，就是指二叉樹的左、右子樹的深度差不超過2。每當插入一個新的元素，導致左右子樹的深度超過2層時，需要對二叉樹的失衡節點進行平衡，保持左右子樹高度差在-1到1之間。

可以使用兩個整數來表示左右子樹的深度，前面一個表示左子樹的層數，右邊一個代表右子樹的層數。

調整時，首先需要找到要平衡的節點。找到調整節點后，處理的方法有4種：

上圖中圓標號1的是左-左結構，標號2的是左-右結構，標號3的是右-右，標號4的是右-左結構，這4種結構的處理方式各有不同。

1. 左-左結構，即(2，1)結構

中間節點當作父節點，最上面的節點當作右節點，最下邊節點當作左節點

2. 左-右結構，即(2，-1)結構

最下面節點當作父節點，父節點當作右節點，中間節點當作左節點

3. 右-右結構，即(-2，-1)結構

中間節點當作父節點，最上面的節點當作左節點，最下邊節點當作右節點

4. 右-左結構，即(-2，1)結構

最下面節點當作父節點，最上面節點當作左節點，中間節點當作右節點

編程中，計算左、右子樹深度的代碼如下：

int deep(BBST* b) {if (b == 0){return 0;}int ld =  deep(b->lchild);int rd = deep(b->rchild) ;return ld > rd ? ld + 1 : rd + 1;
}

有了上面的理論和編程基礎，我們可以慢慢的調試并手動寫出平衡二叉樹的插入代碼：

int BBSTree::insert(ELEMENT* e) {if (mTree == 0){mTree = newnode(e);mSize = 1;return 1;}BBST* t = mTree;BBST* tc = 0;Stack s;ELEMENT elem;while (1) {if (e->e == t->data.e) {return 0;}else if (e->e > t->data.e){if (t->rchild == 0){tc = newnode(e);tc->parent = t;t->rchild = tc;mSize++;break;}else {			elem.e = (unsigned long long)t;s.push((ELEMENT*)&elem);t = t->rchild;				}}else {if (t->lchild == 0){tc = newnode(e);tc->parent = t;t->lchild = tc;mSize++;break;}else {elem.e = (unsigned long long)t;s.push((ELEMENT*)&elem);t = t->lchild;		}}}while (s.isEmpty() == 0) {s.pop(&elem);BBST* b = (BBST*)elem.e;b->ld = deep(b->lchild);b->rd = deep(b->rchild);t->ld = deep(t->lchild);t->rd = deep(t->rchild);int high_diff = b->ld - b->rd;int low_diff = t->ld - t->rd;if(high_diff == 2 && low_diff == 1){BBST* f = (BBST*)b->parent;if (f&&f->lchild == b){f->lchild = t;}else if (f&&f->rchild == b){f->rchild = t;}t->parent = f;BBST* tr = t->rchild;t->rchild = b;b->parent = t;b->lchild = tr;if (tr){tr->parent = b;}if (b == mTree){mTree = t;}}else if (high_diff == 2 && low_diff == -1){BBST* f = (BBST*)b->parent;if (f->lchild == b){f->lchild = tc;}else if (f->rchild == b){f->rchild = tc;}tc->parent = f;t->parent = tc;if (tc->lchild){tc->lchild->parent = t;}t->rchild = tc->lchild;b->parent = tc;if (tc->rchild){tc->rchild->parent = b;}b->lchild = tc->rchild;tc->rchild = b;tc->lchild = t;		if (b == mTree){mTree = tc;}}else if (high_diff == -2 && low_diff == 1){BBST* f = (BBST*)b->parent;if (f&&f->lchild == b){f->lchild = tc;}else if (f&&f->rchild == b){f->rchild = tc;}tc->parent = f;b->parent = tc;b->rchild = tc->lchild;if (tc->lchild){tc->lchild->parent = b;}t->parent = tc;t->lchild = tc->rchild;if (tc->rchild){tc->rchild->parent = t;}tc->rchild = t;tc->lchild = b;if (b == mTree){mTree = tc;}}else if (high_diff == -2 && low_diff == -1){BBST* f = (BBST*)b->parent;if (f && f->lchild == b){f->lchild = t;}else if (f && f->rchild == b){f->rchild = t;}t->parent = f;BBST* tl = t->lchild;t->lchild = b;b->parent = t;b->rchild = tl;if (tl){tl->parent = b;}if (b == mTree){mTree = t;}}tc = t;t = b;}return 0;
}

完整代碼地址：
https://github.com/satadriver/dataStruct