二叉查找樹和AVL樹的基本操作（AVL樹就是一顆特殊的二叉查找樹。）

二叉查找樹的特點是：

1 對于每一棵子樹而言，其根節點大于所有左子樹的值，小于所有右子樹上的值(因為是用于查找，是以每個節點中包含的都是關鍵值，是以不應有重複的)。

2 其本身的特點決定了二叉排序樹生成的特點，生成代碼也是簡單的。

3 删除的時候分為隻有左子樹/右子樹，和既有左子樹又有右子樹兩種情況來進行解決。根據自身特點可以最終歸結為删除隻有左右子樹的節點。

4 由于自身特點，中序周遊一棵二叉排序樹得到的結果就是一個遞增序列。

AVL數的特點是：

對于二叉排序樹的1和4，AVL數也是具備的，但是由于AVL樹本身具備更強的限制條件，要求所有左子樹和右子樹高度內插補點的絕對值不能超過1，在插入和删除的時候不僅要保證其有序性，還要保證它的平衡性。是以它的插入删除有着更為複雜的操作。

1 一個很重要的結論就是，在每一次插入或者删除一個節點的時候，隻有在插入或者删除點（删除點是實際的要删除的節點，因為開始的時候會将删除有兩個子樹的節點轉換為删除至多有一個子樹的節點）到根的路徑上的節點才有可能發生平衡變化，因為隻有這些節點的子樹發生了變化。

2所謂最小不平衡子樹指離插入節點最近且以平衡因子的絕對值大于1的節點作為根的子樹。其中在插入節點時候關鍵的一點就是找到最小不平衡子樹的根節點。

3 AVL樹的插入可以分為四種情況：向最小不平衡子樹根節點的左孩子的左子樹上插入造成，定義為LL型；向根節點的左孩子的右子樹上插入造成，定義為LR型；向根節點的右孩子的右子樹上插入造成，定義為RR型；向根節點的右孩子的左子樹插入造成，定義為RL型。其中LL和RR是基本類型，LR類型可以用處理根節點左孩子的RR類型再處理根節點的LL類型來等價，RL類型可以用處理根節點右孩子的LL類型再處理根節點的RR類型來等價。其特點就是處理完這個最小不平衡子樹後不用再回溯，因為之上的肯定都已經是平衡樹了。

4 AVL樹的删除相對于插入就比較複雜了。設P為要删除節點的父節點，可以分為三種情況：P平衡因子原為0，删除使得P的某棵子樹邊矮，最容易處理；從P的較高的子樹上删除一個節點，使得較高的子樹變矮，這個時候不僅會影響P的平衡，很可能還會影響P的父節點的平衡，是以要回溯到根節點，直至遇到某個節點的平衡因子原來為0就停止回溯（當然這裡還會包含平衡的調整）；從P的較矮的子樹上删除一個節點，使得該子樹變得更矮，這個時候設這棵較高的子樹的根節點為Q，此時又分為Q的平衡因子為0，Q的平衡因子和原P的平衡因子同号和Q的平衡因子和原P的平衡因子異号三種情況進行處理。

說明：在這裡求取每個節點的平衡因子都是通過一個height函數，來計算特定節點的左右子樹的差距确定的，節點結構中沒有記錄平衡因子，記錄的是以這個節點為根的子樹的高度。在插入的時候是通過計算節點的左子樹和右子樹的內插補點來檢視是否不平衡需要調整；在删除的時候首先确定是在哪個子樹上删除，然後計算删除節點所在子樹的根節點的平衡因子，之後再細分進而實作節點删除之後造成的不平衡的調整。

其次，關于周遊、查找、删除就是樹或者二分查找樹的通用算法了。

高度為n的平衡二叉樹的最少節點數，設為F(n),則有F(n)=F(n-1)+F(n-2)+1；其中F(0)=0,F(1)=1。可以得到F(n)=F(n+2)-1。F為斐波那契額級數。其實這個也可以根據遞歸的想法總結得到，證明則使用數學歸納法。

屬于斐波那契數列的應用（後一項屬于前兩項之和，第零項為0，第一項為1）。

AVL的删除某個key值的另外一個思路：

從AVL樹中根開始，将和要删除key值不同的全部重新插入一遍，遇到key值則不插入，将key值所在節點的左子樹和右子樹的元素遞歸插入即可。這樣每次删除一個元素的過程轉換為了重新建構一棵AVL樹的過程，代價比較大！

同樣按照某個值分裂AVL樹的過程可以轉化為重新建構兩顆AVL樹的過程；及合并AVL樹都可以轉換為将一棵AVL樹中的元素插入到另外一棵AVL樹中的過程。

實作代碼：

#include <vector>
using namespace std;

template <class Type>
class AvlTree{
	struct AvlNode 
	{
		Type data;
		AvlNode *left;
		AvlNode *right;
		int height;
		AvlNode(const Type& element, AvlNode *lt, AvlNode *rt, int h=0)
			:data(element),left(lt),right(rt),height(h){}
	};

	AvlNode *root;

public:
	vector<Type> vType;						//存儲周遊結果
	typename vector<Type>::iterator iType;  //這裡需要使用typeneme說明一個嵌套類型
	vector<AvlNode *> vNode;
	typename vector<AvlNode*>::iterator iNode;

	AvlTree(AvlNode *t=NULL) {root = t;}
	~AvlTree(){makeEmpty(root);}
	bool find(const Type& x) const;
	void insert(const Type& x){insert(x,root);}
	void remove(const Type& x){remove(x,root);}
	void traverse() {						//遞歸中序周遊
		vType.clear();						//每次周遊之前清空上一次周遊結果！
		vNode.clear();
		traverse(root);
	}		


private:
	void insert(const Type&x, AvlNode *&t); //t的意義是表示一個int*指針類型的别名
	bool remove(const Type&x, AvlNode *&t);
	void traverse(AvlNode *&t);
	void makeEmpty(AvlNode *&t);
	int height(AvlNode *t) const{return t==NULL ? -1 : t->height;}
	void LL(AvlNode *&t);
	void LR(AvlNode *&t);
	void RL(AvlNode *&t);
	void RR(AvlNode *&t);
	int max(int a, int b){return (a>b)?a:b;}
};

template <class Type>
bool AvlTree<Type>::find(const Type &x) const
{
	AvlNode *t=root;
	while (t!=NULL && t->data!=x)
	{
		if(t->data>x)
			t=t->left;
		else
			t=t->right;
	}

	if(t==NULL)
		return false;
	else
		return true;
}

template <class Type>
void AvlTree<Type>::traverse(AvlNode *&t)
{
	if (t!=NULL)
	{
		traverse(t->left);
		vType.push_back(t->data);
		vNode.push_back(t);
		traverse(t->right);
	}
}

template <class Type>
void AvlTree<Type>::makeEmpty(AvlNode *&t)
{
	for (iNode=vNode.begin();iNode!=vNode.end();iNode++)
	{
		delete (*iNode);
	}
}

template <class Type>
void AvlTree<Type>::insert(const Type&x, AvlNode *&t)
{
	if(t==NULL)
		t=new AvlNode(x,NULL,NULL);
	else if (x<t->data)
	{
		insert(x,t->left);
		if (height(t->left)-height(t->right)==2)
		{
			if(x<t->left->data)
				LL(t);
			else
				LR(t);
		}
	}
	else if (t->data<x)
	{
		insert(x,t->right);
		if (height(t->right)-height(t->left)==2)
		{
			if(t->right->data<x)
				RR(t);
			else
				RL(t);
		}
	}
	t->height=max(height(t->left),height(t->right))+1;
}

template <class Type>
void AvlTree<Type>::LL(AvlNode *&t)
{
	AvlNode *t1=t->left;
	t->left=t1->right;
	t1->right=t;
	t->height=max(height(t->left),height(t->right))+1;
	t1->height=max(height(t1->left),height(t))+1;
	t=t1;
}

template <class Type>
void AvlTree<Type>::RR(AvlNode *&t)
{
	AvlNode *t1=t->right;
	t->right=t1->left;
	t1->left=t;
	t->height=max(height(t->left),height(t->right))+1;
	t1->height=max(height(t1->right),height(t));
	t=t1;
}

template<class Type>
void AvlTree<Type>::LR(AvlNode *&t)
{
	RR(t->left);
	LL(t);
}

template<class Type>
void AvlTree<Type>::RL(AvlNode *&t)
{
	LL(t->right);
	RR(t);
}

template<class Type>
bool AvlTree<Type>::remove(const Type&x, AvlNode *&t)
{
	bool stop=false;
	int subTree;    //1表示删除發生在左子樹，2表示删除發生在右子樹
	
	if(t==NULL)
		return true;
	if (x<t->data)
	{
		stop=remove(x,t->left);
		subTree=1;
	}
	else if (t->data<x)
	{
		stop=remove(x,t->right);
		subTree=2;
	}
	else if (t->left!=NULL && t->right!=NULL)
	{
		AvlNode *tmp=t->right;
		while (tmp->left!=NULL)
			tmp=tmp->left;
		t->data=tmp->data;
		stop=remove(t->data,t->right);
		subTree=2;
	}
	else
	{
		AvlNode *oldNode=t;
		t=(t->left!=NULL)?t->left:t->right;
		delete oldNode;
		return false;
	}
	if(stop) return true;
	int bf;       //删除前的平衡因子
	switch (subTree)
	{
	case 1:
		bf=height(t->left)-height(t->right)+1;
		if(bf==0) return true;
		if(bf==1) return false;
		if (bf==-1)
		{
			int bfr=height(t->right->left)-height(t->right->right);
			switch (bfr)
			{
			case 0: 
				RR(t);
				return true;
				break;
			case -1:
				RR(t);
				return false;
				break;
			default:
				RL(t);
				return false;
			}
		}
		break;
	case 2:
		bf=height(t->left)-height(t->right)-1;
		if(bf==0) return true;
		if(bf==-1) return false;
		if(bf==1)
		{
			int bfl=height(t->right->left)-height(t->right->right);
			switch (bfl)
			{
			case 0:
				LL(t);
				return true;
				break;
			case 1:
				LL(t);
				return false;
				break;
			default:
				LR(t);
				return false;
			}
		}
		break;
	}

}

測試代碼

#include <iostream>
#include <vector>
#include "main.h"
using namespace std;

int main()
{
	//建構一棵AVL樹
	int a[] = {10,8,6,21,87,56,4,0,11,3,22,7,5,34,1,2,9};
	AvlTree<int> tree;
	for(int i=0; i<17; i++)
		tree.insert(a[i]);
	cout << endl;

	//查找是否在AVL樹中
	int val1=22,val2=100;
	if(tree.find(val1))
		cout << "find val1 ok!" << endl;
	else
		cout << "NOT find val1" << endl;
	if(tree.find(val2))
		cout << "find val2 ok!" << endl;
	else
		cout << "NOT find val2" << endl;

	tree.traverse();
	cout << "NOW the Tree Size is:" << tree.vType.size() << endl;
	for(tree.iType=tree.vType.begin();tree.iType!=tree.vType.end();tree.iType++)
	{
		cout << " " << *(tree.iType);
	}
	cout << endl << "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" <<endl;

	//移除之後再查找
	tree.remove(val1);
	if(tree.find(val1))
		cout << "find val1 ok!" << endl;
	else
		cout << "NOT find val1" << endl;

	tree.traverse();
	cout << "NOW the Tree Size is:" << tree.vType.size() << endl;
	for(tree.iType=tree.vType.begin();tree.iType!=tree.vType.end();tree.iType++)
	{
		cout << " " << *(tree.iType);
	}
	cout << endl << "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" <<endl;

	return 0;
}

二叉查找樹和AVL樹的基本操作（AVL樹就是一顆特殊的二叉查找樹。）

繼續閱讀

studio📍位址：15RegentStreetWoolloongabba,Brisbane,Queensland410

probe()函數是什麼時候被調用，裝置和驅動是怎麼聯系起來的

（C# 程式設計指南）

數組的動态記憶體配置設定

二叉樹先序、中序、後序三種周遊的非遞歸算法

如何存取圖檔到資料庫(SQL Server)

DOS常用指令的使用

DOS指令(2) 磁盤操作類指令

程式設計高手：VC 6.0下利用消息實作内部程序通訊

設定某一行背景顔色的CListCtrl

轉換字元串成ＩＮＴ６４

c寫檔案

C#多線程——前台線程和背景線程

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

IE8 CSS設定DIV居中，添加“margin:0 auto”

Small tricks