背景：

二叉平衡樹，就是根據二叉搜尋樹進行優化，讓其速度更加的快，如果讀者沒有學過二叉搜尋樹，可以前往以下連結檢視資料：

http://t.csdn.cn/cCDQD

二叉平衡樹（C++）背景：二叉搜尋樹的缺陷：二叉平衡樹簡介：如何進行平衡操作：二叉平衡樹的初始化函數：二叉平衡樹的求左右子樹高度函數：二叉平衡樹的查找操作：二叉平衡樹的删除操作：main主函數代碼:全部代碼：樣例：輸入樣例:輸出樣例:總結：

http://t.csdn.cn/cCDQD

二叉搜尋樹的缺陷：

在以上連結中，我們講解了二叉搜尋樹：就是一個二叉樹，有着特殊的性質，搜尋時間很快！但是這有着一個緻命的缺陷，我們給出一個例子，假設我們輸入1,2,3,4,5,6,組成的二叉搜尋樹是這樣的：

1.1 和數組搜尋時間一樣的二叉搜尋樹

這樣的二叉搜尋樹，不就和普通的數組查找時間一樣嗎？連二分查找都不如，會浪費二叉樹的大把空間，我們再看一個例子，輸入6,5,4,3,2,1的二叉搜尋樹是這樣的：

1.2 以遞減序輸入造成的二叉搜尋樹

以上這個二叉搜尋樹是根據輸入的遞減序來進行建立的，而圖1.1則是通過遞增序輸入而造成的二叉搜尋樹，是以我們知道，如果我們的輸入是遞增、遞減序的話，那麼組成的二叉搜尋樹的搜尋時間就和數組一樣的。

是以我們要進行優化，怎麼優化呢？就是在二叉搜尋樹的基礎上優化出一個AVL數（二叉平衡樹）來。

二叉平衡樹簡介：

平衡二叉樹也叫做AVL樹,AVL樹的名字來源于它的發明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL樹是最先發明的自平衡二叉查找樹(Self-Balancing Binary Search Tree,簡稱平衡二叉樹。

我們怎麼知道這棵二叉搜尋樹平不平衡呢？我們知道，二叉搜尋樹的搜尋時間和高度是有直接關系的，但是我們按遞增、遞減序輸入之後，高度就和n一樣了，是以時間複雜度為O(log n).想要優化，就是改變這棵二叉搜尋樹的高度。

首先，我們就是要知道，怎麼樣才要改變二叉搜尋樹的高度，難道隻是遞增、遞減序的輸入嗎？不是的，隻要左子樹高度與右子樹高度沒有高度平衡的話，我們就需要進行一次改變二叉搜尋樹高度的操作。

什麼叫高度平衡呢？就是兩者高度相減的絕對值（abs函數可以求解）c，如果c不等于0（高度一樣），不等于1，不等于-1（等于1和-1都是兩者相差1），那麼說明次二叉搜尋樹不是高度平衡，反之，這棵二叉搜尋樹就是高度平衡。

假設呢？我們輸入1,2,3來組建二叉搜尋樹：

2.1 輸入1,2,3後組成的二叉搜尋樹

每一個節點上方都有兩個數字，左邊的代表其左子樹的高度，右邊的代表其右子樹的高度，從根節點開始，右子樹減左子樹的絕對值為2，不是-1,0,1，是以這不是一顆高度平衡的樹，那麼怎麼樣才是高度平衡的樹呢？

以下為輸入1,2,3後組成的一顆高度平衡的樹（平衡二叉樹）：

2.2 輸入1,2,3組成的高度平衡的二叉搜尋樹（二叉平衡樹）

以上就是一顆二叉平衡樹，這樣我們查找的最長時間為O(2),之前那棵不平衡的二叉搜尋樹卻需要O(3)的時間，别看差距隻有O(1)，如果資料大了之後，差距可是非常的大的。

初始結構代碼：

struct Node{
	int data;
	int r_high;
	int l_high;
	int high;
	Node* lchild;
	Node* rchild;
};

如何進行平衡操作：

思路1（調整輸入順序）：

看我們上面的圖，輸入1,2,3後組成了一顆不平衡的二叉搜尋樹，但是如果我們輸入2,1,3那麼就可以解決這個問題，可以建立出高度平衡的二叉搜尋樹。

這個方法行不行呢？肯定是不行的呀，兄弟們啊！我們講的是動态搜尋啊，什麼是動态啊，就是你在進行插入删除操作的之後，依舊可以進行查找，我們永遠不知道輸入來的下一個數是什麼？更不能提前挑好輸入順序了呀，這個方法是不符合實際的，是以不能采用。

思路2（盯好BF）：

我們這個思路就是要做好“盯好BF”，BF是什麼呢？大家不要誤解了啊，BF并不是男朋友的縮寫哈，在計算機程式設計之中，BF就是每一個結點的高度，就是要我們盯緊這個二叉搜尋樹是不是高度平衡，如果是，那麼不用管，如果不是，那麼需要進行平衡操作，使其依舊保持高度平衡（并且符合二叉搜尋樹的基本性質：左子節點小于根節點，右子節點大于根節點）。

我們怎麼求每一個節點的高度呢？我們可以編寫一個函數來解決，就是一個遞歸還是，不斷的前往其的左子節點、右子節點，如果不為空的話那麼進行計數器倒推++，這樣就可以求出左子樹的高度和右子樹的高度，對兩者相減的絕對值進行判斷，是不是高度平衡。

我們可以進行一次總結，看看二叉搜尋樹有哪些不平衡的的情形。

平衡二叉樹不平衡的情形：

把需要重新平衡的結點叫做q，由于任意兩個結點最多隻有兩個兒子，是以高度不平衡時，α結點的兩顆子樹的高度相差2.容易看出，這種不平衡可能出現在下面4中情況中：

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

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

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

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

情形1和情形4是關于q的鏡像對稱(也就是說在情形1在鏡子裡的樣子就是情形4），二情形2和情形3(也就是說在情形2在鏡子裡的樣子就是情形3）也是關于q的鏡像對稱，是以理論上看隻有兩種情況，但程式設計的角度看還是四種情形。

第一種情況是插入發生在“外邊”的情形（左左或右右），該情況可以通過一次單旋轉完成調整；第二種情況是插入發生在“内部”的情形（左右或右左），這種情況比較複雜，需要通過雙旋轉來調整。

調整措施：

一、單旋轉

左左情況的二叉搜尋樹

也就是從根節點k2開始，左子節點有兩個結點，并且沒有高度平衡，這樣我們可以進行一次單旋的操作。

進行一次單旋過後的二叉搜尋樹

上圖是左左的情況，k2結點不滿足平衡性，它的左子樹k1比右子樹z深兩層，k1子樹中更深的是k1的左子樹x，是以屬于左左情況。

為了恢複平衡，我們把x上移一層，并把z下移一層，但此時實際已經超出了AVL樹的性質要求。為此，重新安排結點以形成一顆等價的樹。為使樹恢複平衡，我們把k2變成這棵樹的根節點，因為k2大于k1，把k2置于k1的右子樹上，而原本在k1右子樹的Y大于k1，小于k2，就把Y置于k2的左子樹上，這樣既滿足了二叉查找樹的性質，又滿足了平衡二叉樹的性質。

這種情況稱為單旋轉。

二、雙旋轉

對于左右和右左兩種情況，單旋轉不能解決問題，要經過兩次旋轉。

我們以左右來作為例子：

左右情況的二叉搜尋樹

這種情況，進行一次單旋過後，依舊不是高度平衡，是以我們需要再次進行一次單旋操作，俗稱雙旋！

以下為第一次單旋過後的圖：

進行了一次單旋的二叉搜尋樹

第二次雙旋過後的圖：

雙旋結束過後的二叉搜尋樹

對于上圖情況，為使樹恢複平衡，我們需要進行兩步，第一步，把k1作為根，進行一次右右旋轉，旋轉之後就變成了左左情況，是以第二步再進行一次左左旋轉，最後得到了一棵以k2為根的平衡二叉樹。

代碼：

bool cz=false;
bool sx=false;
bool CZ=false;
void AVL_CZ(Node* &q,Node *c){
	if(CZ)
	  return ;
	if(q==NULL){
		q=c;
		CZ=true;
		return ;
	}
	bool f=cmp(c->data,q->data);
	if(f)
	  AVL_CZ(q->rchild,c);
	else
	  AVL_CZ(q->lchild,c);
}
void AVL_TC(Node* &q){
	if(cz)
	  return ;
	int c=abs(q->l_high-q->r_high);
	if(!(c!=1&&c!=0&&c!=-1)){
		cz=true;
		return ;
	}
	if(q->l_high>q->r_high){
		AVL_TC(q->lchild);
		if(cz==true&&sx==false){
			Node *p=q;
			q=q->lchild;
			p->lchild=NULL;
			sx=true;
			if(q->rchild==NULL)
			  q->rchild=p;
			else{
				Node *c;
				c=q->rchild;
				q->rchild=p;
				AVL_CZ(q,c);
			}
		}
	}
	else{
		AVL_TC(q->rchild);
		if(cz==true&&sx==false){
			Node *p=q;
			q=q->rchild;
			p->rchild=NULL;
			sx=true;
			if(q->lchild==NULL)
			  q->lchild=p;
			else{
				Node *c;
				c=q->lchild;
				q->lchild=p;
				AVL_CZ(q,c);
			}
		}
	}
}
void AVL(Node* &x){
	int c=abs(x->l_high-x->r_high);
	if(c!=1&&c!=0&&c!=-1){
		cz=sx=CZ=false;
		AVL_TC(x);
	}
}

二叉平衡樹的初始化函數：

void init(Node* &p){
	p=new Node; 
	p->l_high=p->r_high=p->high=0;
	p->data=-1;
	p->lchild=new Node;
	p->rchild=new Node;
	p->lchild=NULL;
	p->rchild=NULL;
}
//将高進行調整
void init2(Node *q){
	q->l_high--,q->r_high--,q->high=max(q->l_high,q->r_high);
	if(q->lchild==NULL&&q->rchild==NULL)
	  return ;
	if(q->lchild!=NULL)
	  init2(q->lchild);
	if(q->rchild!=NULL)
	  init2(q->rchild);
}

二叉平衡樹的求左右子樹高度函數：

之前我們講了，可以運用遞歸的形式，倒退加法！

求高度函數：

int high(Node* &q){
	q->l_high=q->r_high=q->high=1;
	if(q->lchild==NULL&&q->rchild==NULL)
	  return 1;
	if(q->lchild!=NULL)
	  q->l_high+=high(q->lchild);
	if(q->rchild!=NULL)
	  q->r_high+=high(q->rchild);
	q->high=max(q->l_high,q->r_high);
	return q->high;
}

二叉平衡樹的查找操作：

這個很簡單，就和二叉搜尋樹一樣，

我們可以應用遞歸的形式,如果q->lf為真，并且用cmp(q->data,s)進行比較之後，遞歸去q->lchild看看，如果q->rf為真，遞歸去q->rchild看看，每次到一個節點，都要比較這個結點和s是不是一樣（pd函數），如果一樣，傳回為真。

查找函數代碼：

bool S=false;
void search(Node *q,int s){
	if(S)
	  return ;
	if(q->data==s){
		S=true;
		return ;
	}
	if(q->lchild==NULL&&q->rchild==NULL)
	  return ;
	bool f=cmp(q->data,s);
	if(f)
	  search(q->lchild,s);
	else
	  search(q->rchild,s);
}

二叉平衡樹的删除操作：

我們以上已經将二叉搜尋樹優化成了二叉平衡樹，接下來我們需要進行二叉平衡樹的删除操作！

同插入操作一樣，删除結點時也有可能破壞平衡性，這就要求我們删除的時候要進行平衡性調整。

删除分為以下幾種情況：

首先在整個二叉樹中搜尋要删除的結點，如果沒搜尋到直接傳回不作處理，否則執行以下操作：

1.要删除的節點是目前根節點T。

如果左右子樹都非空。在高度較大的子樹中實施删除操作。

分兩種情況：

(1)、左子樹高度大于右子樹高度，将左子樹中最大的那個元素賦給目前根節點，然後删除左子樹中元素值最大的那個節點。

(1)、左子樹高度小于右子樹高度，将右子樹中最小的那個元素賦給目前根節點，然後删除右子樹中元素值最小的那個節點。

如果左右子樹中有一個為空，那麼直接用那個非空子樹或者是NULL替換目前根節點即可。

2、要删除的節點元素值小于目前根節點T值，在左子樹中進行删除。

遞歸調用，在左子樹中實施删除。

這個是需要判斷目前根節點是否仍然滿足平衡條件，

如果滿足平衡條件，隻需要更新目前根節點T的高度資訊。

否則，需要進行旋轉調整：

如果T的左子節點的左子樹的高度大于T的左子節點的右子樹的高度，進行相應的單旋轉。否則進行雙旋轉。

3、要删除的節點元素值大于目前根節點T值，在右子樹中進行删除。

删除函數代碼：

bool SC=false;
Node* TH=NULL;
void AVL_remove(Node* &q,int s){
	if(SC)
	  return ;
	if(q->data==s){
		Node *a=q;
		if(q->lchild==NULL&&q->rchild==NULL)
		  q=NULL;
		else if(a->l_high>=a->r_high&&q->lchild!=NULL&&((q->lchild->lchild==NULL||q->lchild->rchild==NULL)&&q->lchild->lchild!=q->lchild->rchild)){
			q=q->lchild;
			if(a->rchild!=NULL)
			  q->rchild=a->rchild;
		}
		else if(a->l_high<=a->r_high&&q->rchild!=NULL&&((q->rchild->lchild==NULL||q->rchild->rchild==NULL)&&q->rchild->lchild!=q->rchild->rchild)){
			q=q->rchild;
			if(a->lchild!=NULL)
			  q->lchild=a->lchild;
		}
		SC=true;
		return ;
	}
	bool f=cmp(q->data,s);
	if(f)
	  AVL_remove(q->lchild,s);
	else
	  AVL_remove(q->rchild,s);
}
bool remove(Node* &q,int s){
	search(q,s);
	if(S){
		AVL_remove(q,s);
		if(SC)
		  return true;
		else
		  return false;
	}
	else
	  return false;
}

main主函數代碼:

int main(){
	Node* p;
	init(p); 
	while(1){
		cout<<"1.插入\n2.查找\n3.删除\n";
		int c;
		cin>>c;
		if(c==1){
			int a;
			cout<<"輸入要插入的數:";
			cin>>a;
			bool f=insert(p,a);
			if(!f){
				cout<<"插入失敗！\n";
				return 0;
			}
			high(p);
			AVL(p); 
			high(p);
			init2(p);
			puts("樹:");
			print(p);
		}
		else if(c==2){
			int a;
			cout<<"輸入要查找的數:";
			cin>>a;
			S=false;
			search(p,a);
			if(S)
			  cout<<"在二叉伸展樹中有這個數!\n";
			else
			  cout<<"沒有查到此數!\n";
		}
		else if(c==3){
			int a;
			cout<<"請輸入你要删除的數:";
			cin>>a;
			S=SC=false;
			TH=NULL;
			bool f=remove(p,a);
			if(f){
				cout<<"删除成功!\n";
				high(p);
				AVL(p); 
				high(p);
				init2(p);
				puts("樹:");
				print(p);
			}
			else
			  cout<<"删除失敗,沒有這個數!\n";
		}
		else
		  cout<<"重新輸入!\n";
		puts(" ");
	}
	return 0;
}

全部代碼：

#include<bits/stdc++.h>
using namespace std;
int n;
struct Node{
	int data;
	int r_high;
	int l_high;
	int high;
	Node* lchild;
	Node* rchild;
};
void init(Node* &p){
	p=new Node; 
	p->l_high=p->r_high=p->high=0;
	p->data=-1;
	p->lchild=new Node;
	p->rchild=new Node;
	p->lchild=NULL;
	p->rchild=NULL;
}
bool cmp(int a,int b){
	return a>b;
}
bool insert(Node *q,int s){
	while(1){
		if(q->lchild==NULL&&q->rchild==NULL&&q->data==-1){
			q->data=s;
			return true;
		}
		bool f=cmp(q->data,s);
		if(f){
			if(q->lchild==NULL)
			  init(q->lchild);
			q=q->lchild;
		}
		else{
			if(q->rchild==NULL)
			  init(q->rchild);
			q=q->rchild;
		}
	}
	return false;
}
void print(Node* q,int a=-1,int b=-1){
	if(a==-1)
	  cout<<"根節點:";
	else{
		if(b==1)
		  cout<<a<<"的左子節點:";
		else
		  cout<<a<<"的右子節點:";
	}
	cout<<q->data<<endl<<"  左子樹高:"<<q->l_high<<endl<<"  右子樹高:"<<q->r_high<<endl;
	if(q->lchild==NULL&&q->rchild==NULL)
	  return ;
	if(q->lchild!=NULL)
	  print(q->lchild,q->data,1);
	if(q->rchild!=NULL)
	  print(q->rchild,q->data,2);
}
void init2(Node *q){
	q->l_high--,q->r_high--,q->high=max(q->l_high,q->r_high);
	if(q->lchild==NULL&&q->rchild==NULL)
	  return ;
	if(q->lchild!=NULL)
	  init2(q->lchild);
	if(q->rchild!=NULL)
	  init2(q->rchild);
}
int high(Node* &q){
	q->l_high=q->r_high=q->high=1;
	if(q->lchild==NULL&&q->rchild==NULL)
	  return 1;
	if(q->lchild!=NULL)
	  q->l_high+=high(q->lchild);
	if(q->rchild!=NULL)
	  q->r_high+=high(q->rchild);
	q->high=max(q->l_high,q->r_high);
	return q->high;
}
bool cz=false;
bool sx=false;
bool CZ=false;
void AVL_CZ(Node* &q,Node *c){
	if(CZ)
	  return ;
	if(q==NULL){
		q=c;
		CZ=true;
		return ;
	}
	bool f=cmp(c->data,q->data);
	if(f)
	  AVL_CZ(q->rchild,c);
	else
	  AVL_CZ(q->lchild,c);
}
void AVL_TC(Node* &q){
	if(cz)
	  return ;
	int c=abs(q->l_high-q->r_high);
	if(!(c!=1&&c!=0&&c!=-1)){
		cz=true;
		return ;
	}
	if(q->l_high>q->r_high){
		AVL_TC(q->lchild);
		if(cz==true&&sx==false){
			Node *p=q;
			q=q->lchild;
			p->lchild=NULL;
			sx=true;
			if(q->rchild==NULL)
			  q->rchild=p;
			else{
				Node *c;
				c=q->rchild;
				q->rchild=p;
				AVL_CZ(q,c);
			}
		}
	}
	else{
		AVL_TC(q->rchild);
		if(cz==true&&sx==false){
			Node *p=q;
			q=q->rchild;
			p->rchild=NULL;
			sx=true;
			if(q->lchild==NULL)
			  q->lchild=p;
			else{
				Node *c;
				c=q->lchild;
				q->lchild=p;
				AVL_CZ(q,c);
			}
		}
	}
}
void AVL(Node* &x){
	int c=abs(x->l_high-x->r_high);
	if(c!=1&&c!=0&&c!=-1){
		cz=sx=CZ=false;
		AVL_TC(x);
	}
}
bool S=false;
void search(Node *q,int s){
	if(S)
	  return ;
	if(q->data==s){
		S=true;
		return ;
	}
	if(q->lchild==NULL&&q->rchild==NULL)
	  return ;
	bool f=cmp(q->data,s);
	if(f)
	  search(q->lchild,s);
	else
	  search(q->rchild,s);
}
bool SC=false;
Node* TH=NULL;
void AVL_remove(Node* &q,int s){
	if(SC)
	  return ;
	if(q->data==s){
		Node *a=q;
		if(q->lchild==NULL&&q->rchild==NULL)
		  q=NULL;
		else if(a->l_high>=a->r_high&&q->lchild!=NULL&&((q->lchild->lchild==NULL||q->lchild->rchild==NULL)&&q->lchild->lchild!=q->lchild->rchild)){
			q=q->lchild;
			if(a->rchild!=NULL)
			  q->rchild=a->rchild;
		}
		else if(a->l_high<=a->r_high&&q->rchild!=NULL&&((q->rchild->lchild==NULL||q->rchild->rchild==NULL)&&q->rchild->lchild!=q->rchild->rchild)){
			q=q->rchild;
			if(a->lchild!=NULL)
			  q->lchild=a->lchild;
		}
		SC=true;
		return ;
	}
	bool f=cmp(q->data,s);
	if(f)
	  AVL_remove(q->lchild,s);
	else
	  AVL_remove(q->rchild,s);
}
bool remove(Node* &q,int s){
	search(q,s);
	if(S){
		AVL_remove(q,s);
		if(SC)
		  return true;
		else
		  return false;
	}
	else
	  return false;
}
int main(){
	Node* p;
	init(p); 
	while(1){
		cout<<"1.插入\n2.查找\n3.删除\n";
		int c;
		cin>>c;
		if(c==1){
			int a;
			cout<<"輸入要插入的數:";
			cin>>a;
			bool f=insert(p,a);
			if(!f){
				cout<<"插入失敗！\n";
				return 0;
			}
			high(p);
			AVL(p); 
			high(p);
			init2(p);
			puts("樹:");
			print(p);
		}
		else if(c==2){
			int a;
			cout<<"輸入要查找的數:";
			cin>>a;
			S=false;
			search(p,a);
			if(S)
			  cout<<"在二叉伸展樹中有這個數!\n";
			else
			  cout<<"沒有查到此數!\n";
		}
		else if(c==3){
			int a;
			cout<<"請輸入你要删除的數:";
			cin>>a;
			S=SC=false;
			TH=NULL;
			bool f=remove(p,a);
			if(f){
				cout<<"删除成功!\n";
				high(p);
				AVL(p); 
				high(p);
				init2(p);
				puts("樹:");
				print(p);
			}
			else
			  cout<<"删除失敗,沒有這個數!\n";
		}
		else
		  cout<<"重新輸入!\n";
		puts(" ");
	}
	return 0;
}

樣例：

輸入樣例:

輸出樣例:

1.插入
2.查找
3.删除
1
輸入要插入的數:1
樹:
根節點:1
  左子樹高:0
  右子樹高:0

1.插入
2.查找
3.删除
1
輸入要插入的數:2
樹:
根節點:1
  左子樹高:0
  右子樹高:1
1的右子節點:2
  左子樹高:0
  右子樹高:0

1.插入
2.查找
3.删除
1
輸入要插入的數:3
樹:
根節點:2
  左子樹高:1
  右子樹高:1
2的左子節點:1
  左子樹高:0
  右子樹高:0
2的右子節點:3
  左子樹高:0
  右子樹高:0

1.插入
2.查找
3.删除
2
輸入要查找的數:1
在二叉伸展樹中有這個數!

1.插入
2.查找
3.删除
3
請輸入你要删除的數:1
删除成功!
樹:
根節點:2
  左子樹高:0
  右子樹高:1
2的右子節點:3
  左子樹高:0
  右子樹高:0

總結：

對于二叉平衡樹來說，速度還是非常的快的，但是還有一項可以繼續的優化，這一點可以看我的下一個文章“二叉伸展樹”。

背景：

二叉搜尋樹的缺陷：

二叉平衡樹簡介：

初始結構代碼：

如何進行平衡操作：

思路1（調整輸入順序）：

思路2（盯好BF）：

代碼：

二叉平衡樹的初始化函數：

二叉平衡樹的求左右子樹高度函數：

求高度函數：

二叉平衡樹的查找操作：

查找函數代碼：

二叉平衡樹的删除操作：

删除函數代碼：

main主函數代碼:

全部代碼：

樣例：

輸入樣例:

輸出樣例:

總結：

繼續閱讀

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器

hdu7108哈希