AVL樹是帶有平衡條件的二叉查找樹。

這個平衡條件必須保持，并且它必須保證樹的深度是O（logN）。

一棵AVL樹是其每一個節(jié)點的左子樹和右子樹的高度最多差1的二叉查找樹。

（空樹的高度定義為-1）。

在插入以后。僅僅有那些從插入點到根節(jié)點的路徑上的節(jié)點的平衡可能被改變，由于僅僅有這些節(jié)點的子樹可能發(fā)生變化。當我們沿著這條路徑上行到根并更新平衡信息時。我們能夠找到一個節(jié)點，它的新平衡破壞了AVL條件。我們將指出怎樣在第一個這種節(jié)點(即最深的節(jié)點）又一次平衡這棵樹，并證明，這一又一次平衡保證整個樹滿足AVL特性。

讓我們把必須又一次平衡的這個節(jié)點叫做a。因為隨意節(jié)點最多有兩個兒子，因此高度不平衡時。a點的兩棵子樹的高度差2。easy看出，這樣的不平衡可能出如今以下四種情況中：

1.對a的左兒子的左子樹進行一次插入

2.對a的左兒子的右子樹進行一次插入

3.對a的右兒子的左子樹進行一次插入

4.對a的右兒子的右子樹進行一次插入

第一種情況是插入發(fā)生在“外邊"的情況（即左—左的情況或右—右的情況）。該情況通過對樹的一次單旋轉(zhuǎn)而完畢調(diào)整。另外一種情況是插入發(fā)生在”內(nèi)部“的情形(即左—右的情況或右—左的情況），該情況通過略微復(fù)雜些的雙旋轉(zhuǎn)來處理。

AVL樹本質(zhì)上還是一棵二叉搜索樹，它的特點是：

本身首先是一棵二叉搜索樹。

帶有平衡條件：每一個結(jié)點的左右子樹的高度之差的絕對值（平衡因子）最多為1

#include <iostream> using namespace std; const int LH = 1; const int EH = 0; const int RH = -1; bool TRUE = 1; bool FALSE = 0;typedef struct BSTNode {int key;int bf;BSTNode *lchild, *rchild; }BSTNode;//中序遍歷 void inordertree(BSTNode * &root) {if (root){inordertree(root->lchild);cout << root->key<<",";inordertree(root->rchild);} }//前序遍歷 void preordertree(BSTNode * &root) {if (root){cout << root->key<<",";preordertree(root->lchild);preordertree(root->rchild);} } //右旋 void R_Rotate(BSTNode * &p) {BSTNode *lc = p->lchild;p->lchild = lc->rchild;lc->rchild = p;p = lc; }//左旋 void L_Rotate(BSTNode *& p) {BSTNode *rc = p->rchild;p->rchild = rc->lchild;rc->lchild = p;p = rc; }void LeftBalance(BSTNode * &T) {BSTNode *lc = T->lchild;switch (lc->bf){case LH:T->bf = lc->bf = EH;R_Rotate(T);break;case RH:BSTNode *rd = lc->rchild;switch (rd->bf){case LH:T->bf = RH;lc->bf = EH;break;case EH:T->bf = lc->bf = EH;lc->bf = LH;break;}rd->bf = EH;L_Rotate(T->lchild);//先左旋R_Rotate(T);break;} }void RightBalance(BSTNode *& T) {BSTNode *rc = T->rchild;switch (rc->bf){case RH:T->bf = rc->bf = EH;L_Rotate(T);break;case LH:BSTNode *ld = rc->lchild;switch (ld->bf){case RH:T->bf = LH;rc->bf = EH;break;case EH:T->bf = rc->bf = EH;break;case LH:T->bf = EH;rc->bf = RH;break;}ld->bf = EH;R_Rotate(T->rchild);L_Rotate(T);break;} }int insertAVL(BSTNode *& t, int e, bool &taller) {if (!t){t = new BSTNode;t->key = e;t->lchild = t->rchild = NULL;t->bf = EH;taller = TRUE;}else{if (e == t->key){taller = FALSE;return 0;}if (e < t->key){if (!insertAVL(t->lchild, e,taller))return 0;if (taller){switch (t->bf){case LH:LeftBalance(t);taller = FALSE;break;case EH:t->bf = LH;taller = TRUE;break;case RH:t->bf = EH;taller = FALSE;break;}}}else{if (!insertAVL(t->rchild, e, taller))return 0;if (taller){switch (t->bf){case RH:RightBalance(t);taller = FALSE;break;case EH:t->bf = RH;taller = TRUE;break;case LH:t->bf = EH;taller = FALSE;break;}}}}return 1; }BSTNode *search(BSTNode *t, int key) {BSTNode *p = t;while (p){if (p->key == key)return p;else if (p->key < key)p = p->rchild;elsep = p->lchild;}return p; }int main() {BSTNode *root = NULL;BSTNode *r;bool taller = FALSE;int array[] = { 13, 24, 37, 90, 53 };for (int i = 0; i < 5; i++)insertAVL(root, array[i], taller);cout << "inorder traverse..." << endl;inordertree(root);cout << endl;cout << "preorder traverse..." << endl;preordertree(root);cout << endl;cout << "search key..." << endl;r = search(root, 37);if (r){cout << r->key << endl;}else{cout << "not find" << endl;}system("pause");return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/jhcelue/p/6880336.html

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法问题 AVL二叉平衡树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。