數據結構與算法問題 AVL二叉平衡樹

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

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

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

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

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

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

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

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

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

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

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

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

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

2. 帶有平衡條件：每一個結點的左右子樹的高度之差的絕對值（平衡因子）最多為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;
}