AVL樹---最簡單的實作

一、定義：

我們知道二叉查找樹，有很強的排序、查找、删除、插入的能力，但是，随着插入和删除的次數變多，二叉查找樹的工作的效率有可能的變得沒那麼好了，因為二叉查找樹的工作效率依賴于樹的高度，樹越高效率越差(同樣多的結點的情況下),是以，就需要盡可能地降低樹的高度。引入AVL樹的目的就是為了提高二叉查找樹的效率，在每次向二叉樹插入或删除結點的時候，盡可能地使二叉查找樹保持平衡，平衡狀态下樹的高度是最低的。

維基百科:

AVL樹---最簡單的實作

上圖給出了，AVL樹的概念和平衡因子的概念(左子樹的高度-右子樹的高度)

二、分析：

首先空樹是AVL樹,當我們先AVL樹插入或删除結點的AVL樹可能會失去平衡，AVL樹失去平衡的情況有以下四種:

AVL樹---最簡單的實作

1、左左（

LL

）不平衡情況：

在根結點的較高的左子樹的左子樹上插入了結點，使得根的平衡因子大于

而失去平衡，或者是在删除一個結點後，使得原本就更高的左子樹的左邊更高，這種情況要作右單旋(右邊矮做右單旋)操作

以下假設

T1、T2、T3

是高度相同的滿二叉樹：

y    			     y                               x
	    / \   			    / \     Right Rotation          /  \
	   x   T3 	-------->  x   T3   - - - - - - - >        T1   y 
	  / \     	insert O  / \                             /    / \
	 T1  T2   			 T1  T2                          O    T2  T3
			    		/
			  	       O

Node *x = y->left;
	y->left = x->right;
	x->right = y;

2、右右（

RR

)不平衡情況：

這個和

LL

對稱，它是原較高的右子樹的右子樹更高了,這種情況要進行左單旋(左邊矮做左單旋)操作

以下假設

T1、T2、T3

是高度相同的滿二叉樹：

y                     		  x                           x                 
    / \                    		 / \             	         / \                        
   x   T3                  		T1   y     <-------        T1   y                       
  / \    \   < - - - - - - -        / \     insert O           / \                             
 T1  T2   o  Left Rotation        T2  T3                     T2  T3                                 
									    \
										 O

Node* y = x->right;
	x->right = y->left;
	y->left = x;

3、左右(

LR

)不平衡情況:

原本較高的左子樹(斷句)的右子樹高度更高了,這種情況要進行先左單,後右單的雙旋操作

以下假設

T1、T4

高度為

、

T2、T3

的高度

h-1

：

z    			       z                               z                           x
    / \   			      / \                            /   \                        /  \ 
   y   T4 	------->     y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \    	insert O    / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x    			  T1   x                          y    T3                    T1  T2 T3  T4
    / \   			      / \                        / \						     /
  T2   T3 			    T2   T3                    T1   T2  						O
	  					/                              /
					   O						      O

上面圖

假設在以

為根較高的左子樹

的右子樹

上插入一個結點

(

的左右子女上都可以)，首先

結點的平衡因子為

-2

,失去平衡,這裡先做個左單旋，做完後(不管做不做)

的平衡因子為

,要做個右單旋。

代碼類似于：

leftRotation(y);
	rightRotation(z);

因為y是z的左子女,是以可以寫成：

z->left = leftRotation(z->left);
	return rightRotation(z);

leftRotation

和

rightRotation

傳回調整後的根結點。

4、

RL

不平衡情況：和

LR

不平衡對稱

在原本較高的右子樹(斷句)的左子樹高度更高了導緻的不平衡,要先右單旋後左單旋。

以下假設

T1、T4

高度為

、

T2、T3

的高度

h-1

：

z     					   z                            z                            x
  / \    					  / \                          / \                          /  \ 
T1   y   	----------> 	T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
    / \  	insert O		    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4					   x   T4                      T2   y                  T1  T2  T3  T4
  / \    					  / \                         /    /  \                    /
T2   T3  					T2   T3                      O    T3   T4                 O
							/
						   O

代碼類似于：

z->left = rightRotation(z->left);
	return leftRotation(z);

在插入或删除某個結點後，隻有出現了這四種情況會導緻AVL樹暫時失去平衡,而相應的解決辦法也給出了。是以，在代碼實作的時候，每次插入删除的時候，都要從插入删除位置沿雙親位置向上回溯，檢查以每個雙親為根時AVL樹有沒有失去平衡，失去了是哪種情況就對的就用那種方法調整。是以插入删除的時候可以用遞歸的方法來實作，插入和删除一個結點後就回溯到上一層，檢查，然後繼續回溯，直到沒問題的時候。

小總結:

假設定義以自底向上第一個平衡因子為

2或者-2

為根的樹為最小不平衡AVL樹。那麼它不平衡的原因就四種:

設根為

root

，這四種情況是：

不平衡情況	說明	平衡因子特點	解決辦法
LL	root的左子樹比右子樹高2，并且左子樹的左子樹比右子樹高1或相等(插入時不會，删除時可能會)	此時root的平衡因子為2，左子樹的平衡因子為1或0	右單旋
LR	root的左子樹比右子樹高2，并且左子樹的右子樹比左子樹高1(其實相等也可以，但我把相等的情況放上面去了）	此時root的平衡因子為2，左子樹的平衡因子為-1	先左單旋後右單旋
RR	root的右子樹比左子樹高2，并且右子樹的右子樹比左子樹高1或相等(與LL同理）	此時，root的平衡因子為-2，右子樹的平衡因子為-1或0	左單旋
RL	root的右子樹比左子樹高2，并且右子樹的左子樹比右子樹高1	此時，root的平衡因子為-2，root的右子樹平衡因子為1	先右單旋後左單旋

這個表很重要，插入和删除時就是根據這個來調整不平衡的。

左邊低左單旋，右邊低右單旋。這個自己了解了解圖就好。

三、代碼實作：

1、結點結構：

class Node
{
	public:
		int key;
		int height;
		Node *left,*right;
		Node(int _key)
		{
			key = _key;
			height = 1;
			left = right = NULL;
		}
};

2、樹的高度：

int height(Node *N)
{
	if(N == NULL)
	{
		return 0;
	}
	return N->height;
}

3、max函數：傳回大的值

int max(int x,int y)
{
	return x > y ? x : y;
}

4、計算以某結點為根的平衡因子：左子樹的高度-右子樹的高度

int getBalance(Node *root)    //獲得以root為根的子樹的平衡因子 
{
	if(root == NULL)
	{
		return 0;
	} 
	return height(root->left) - height(root->right);
}

5、左單旋：

Node* leftRotation(Node *x)
{//左單旋(左邊矮),又稱RR旋轉(在較高的右子樹的右子樹插入結點導緻失去平衡 ) 
	Node* y = x->right;
	x->right = y->left;
	y->left = x;
	
	y->height = max(height(y->left), height(y->right)) + 1;
	x->height = max(height(x->left), height(x->right)) + 1;
	
	return y;	//傳回調整後的根結點 
}

6、右單旋：

Node* rightRotation(Node *y)
{ //右單旋(右邊矮),又稱LL旋轉(在較高的左子樹的左子樹插入結點導緻失去平衡) 
	Node *x = y->left;
	y->left = x->right;
	x->right = y;
	
	y->height = max(height(y->left), height(y->right)) + 1;
	x->height = max(height(x->left), height(x->right)) + 1;
	
	return x; 	//傳回調整後的根結點 
}

7、插入：

插入完後執行以下步驟：

1）目前節點如果是插入結點的祖先之一，那麼要更新目前結點的高度。

2）擷取目前結點的平衡因子（左子樹的高度–右子樹的高度）。

3）如果平衡因子大于1，則目前結點不平衡，我們處于“左左”情況或“左右”情況。要檢查是左左情況還是左右情況，請擷取左子樹的平衡因子。如果左子樹的平衡因子大于或等于0，則為

LL

情況

[因為大于等于0說明左子樹的左子樹的高度大于或等于左子樹的右子樹的高度,大于0時是

情況沒問題，等于0時，為方面當作LL情況來處理(LL一次左單旋就夠了，LR得先左旋後右旋)]

，否則為

LR

情況。下同

4）如果平衡因子小于-1，則目前節點不平衡，我們處于“右右”情況或“右左”情況。要檢查是右右情況還是右左情況，請擷取右子樹的平衡因子。如果右子樹的平衡因子小于或等于0，則為

RR

情況，否則為

RL

情況。

Node* insert(Node *root,int key)
{
	if(root == NULL)
	{
		return new Node(key);
	} 
	
	if(key < root->key)
	{
		root->left = insert(root->left, key); 
	}
	else if(key > root->key)
	{
		root->right = insert(root->right, key);
	}
	else 	//key == root->key不插入 
	{
		return root;
	}
	
	root->height = 1 + max(height(root->left),height(root->right));
	
	int balance = getBalance(root);		//檢查平衡因子
	
	//LL情況 -->右單旋 
	if(balance > 1 && getBalance(root->left) >= 0)
	{//LL ---> 右單旋 
		return rightRotation(root); 
	} 
	
	if(balance > 1 && getBalance(root->left) < 0)
	{//LR ----->先左單旋後右單旋
		root->left = leftRotation(root->left);
		return rightRotation(root); 
	} 
	
	if(balance < -1 && getBalance(root->right) <= 0)
	{//RR---->左單旋
		return leftRotation(root);		
	}
	
	if(balance < -1 && getBalance(root->right) > 0)
	{//RL---->先右單旋後左單旋 
		root->right = rightRotation(root->right);
		return leftRotation(root);
	}
	
	return root;	//沒有失去平衡 
}

8、删除：這個和二叉查找樹一樣，當有待删結點有兩個子女時，要把它轉換成删一個子女的情況(找右子樹下值關鍵碼最小的結點來代替被删(中序後繼),或者左子樹下關鍵碼最大的(中序前繼))。

删完後還有以下步驟：

1）目前節點如果是已删除結點的祖先之一，那麼要更新目前結點的高度。

2）擷取目前結點的平衡因子（左子樹的高度–右子樹的高度）。

LL

情況

[因為大于等于0說明左子樹的左子樹的高度大于或等于左子樹的右子樹的高度,大于0時是

情況沒問題，等于0時，為方面當作LL情況來處理(LL一次左單旋就夠了，LR得先左旋後右旋)]

，否則為

LR

情況。下同

RR

情況，否則為

RL

情況。

Node *minValueNode(Node *node)
{//中序右子樹下第一個結點(右子樹下key值最小) 
	Node *current = node;
	
	while(current->left != NULL)
	{
		current = current->left;
	}
	return current;
}

Node* deleteNode(Node* root,int key)
{
	if(root == NULL)
	{
		return root;
	} 

	if(key < root->key)
	{
		root->left = deleteNode(root->left, key);
	}
	else if(key > root->key)
	{
		root->right = deleteNode(root->right, key); 
	}
	else
	{
		if((root->left == NULL) || (root->right == NULL))
		{
			Node* temp = root->left?
						 root->left:
						 root->right; 
			if(temp == NULL)  //如果沒有子女 
			{
				temp = root;	//temp 儲存要删除結點 
				root = NULL;    // root 置空 
			}
			else		//有一個子女 
			{
				*root = *temp;		//把temp的值拷給root,temp代替被删 
			}
			delete temp; 
		}
		else    //如果有兩個子女-->找個隻有一個子女或者沒有子女的子孫, 
		{		//把它的值存到目前結點,然後把這個子孫删了 
			Node *temp = minValueNode(root->right);
			
			root->key = temp->key;
			
			root->right = deleteNode(root->right,
									 temp->key);
		} 
	}
	
	//删完後root == NULL就不用檢查以root為根的子樹平不平衡了
	if(root == NULL)
	{
		return root;
	} 
	
	root->height = 1 + max(height(root->left),
						   height(root->right));
	
	int balance = getBalance(root);
	
	if(balance > 1 && getBalance(root->left) >= 0)
	{//LL ---> 右單旋 
		return rightRotation(root); 
	} 
	
	if(balance > 1 && getBalance(root->left) < 0)
	{//LR ----->先左單旋後右單旋
		root->left = leftRotation(root->left);
		return rightRotation(root); 
	} 
	
	if(balance < -1 && getBalance(root->right) <= 0)
	{//RR---->左單旋
		return leftRotation(root);		
	}
	
	if(balance < -1 && getBalance(root->right) > 0)
	{//RL---->先右單旋後左單旋 
		root->right = rightRotation(root->right);
		return leftRotation(root);
	}
	return root;		//傳回删完後調整後的根
}

9、測試代碼：

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Node
{
	public:
		int key;
		int height;
		Node *left,*right;
		Node(int _key)
		{
			key = _key;
			height = 1;
			left = right = NULL;
		}
};
int height(Node *N)
{
	if(N == NULL)
	{
		return 0;
	}
	return N->height;
}
int max(int x,int y)
{
	return (x > y )? x : y;
} 
int getBalance(Node *root)    //獲得以root為根的子樹的平衡因子 
{
	if(root == NULL)
	{
		return 0;
	} 
	return height(root->left) - height(root->right);
}
/*
     y                               x
    / \     Right Rotation          /  \
   x   T3   - - - - - - - >        T1   y 
  / \       < - - - - - - -            / \
 T1  T2     Left Rotation            T2  T3
*/
Node* leftRotation(Node *x)
{//左單旋(左邊矮),又稱RR旋轉(在較高的右子樹的右子樹插入結點導緻失去平衡 ) 
	Node* y = x->right;
	x->right = y->left;
	y->left = x;
	
	//更新x,y的高度，必須先x,後y,因為x是y的子樹 
	x->height = max(height(x->left), height(x->right)) + 1;
	y->height = max(height(y->left), height(y->right)) + 1;
	
	return y;	//傳回調整後的根結點 
} 
Node* rightRotation(Node *y)
{ //右單旋(右邊矮),又稱LL旋轉(在較高的左子樹的左子樹插入結點導緻失去平衡) 
	Node *x = y->left;
	y->left = x->right;
	x->right = y;
	
	//更新x,y的高度，必須先y,後x,因為y是x的子樹 
	y->height = max(height(y->left), height(y->right)) + 1;
	x->height = max(height(x->left), height(x->right)) + 1;
	
	return x; 	//傳回調整後的根結點 
} 
Node* insert(Node *root,int key)
{
	if(root == NULL)
	{
		return new Node(key);
	} 
	
	if(key < root->key)
	{
		root->left = insert(root->left, key); 
	}
	else if(key > root->key)
	{
		root->right = insert(root->right, key);
	}
	else 	//key == root->key不插入 
	{
		return root;
	}
	
	root->height = 1 + max(height(root->left),height(root->right));
	
	int balance = getBalance(root);		//檢查平衡因子
	
	//LL情況 -->右單旋 
	if(balance > 1 && getBalance(root->left) >= 0)
	{//LL ---> 右單旋 
		return rightRotation(root); 
	} 
	
	if(balance > 1 && getBalance(root->left) < 0)
	{//LR ----->先左單旋後右單旋
		root->left = leftRotation(root->left);
		return rightRotation(root); 
	} 
	
	if(balance < -1 && getBalance(root->right) <= 0)
	{//RR---->左單旋
		return leftRotation(root);		
	}
	
	if(balance < -1 && getBalance(root->right) > 0)
	{//RL---->先右單旋後左單旋 
		root->right = rightRotation(root->right);
		return leftRotation(root);
	}
	
	return root;	//沒有失去平衡 
}
Node *minValueNode(Node *node)
{//中序右子樹下第一個結點(右子樹下key值最小) 
	Node *current = node;
	
	while(current->left != NULL)
	{
		current = current->left;
	}
	return current;
}

Node* deleteNode(Node* root,int key)
{
	if(root == NULL)
	{
		return root;
	} 
	
	if(key < root->key)
	{
		root->left = deleteNode(root->left, key);
	}
	else if(key > root->key)
	{
		root->right = deleteNode(root->right, key); 
	}
	else
	{
		if((root->left == NULL) || (root->right == NULL))
		{
			Node* temp = root->left?
						 root->left:
						 root->right; 
			if(temp == NULL)  //如果沒有子女 
			{
				temp = root;	//temp 儲存要删除結點 
				root = NULL;    // root 置空 
			}
			else		//有一個子女 
			{
				*root = *temp;		//把temp的值拷給root,temp代替被删 
			}
			delete temp; 
		}
		else    //如果有兩個子女-->找個隻有一個子女或者沒有子女的子孫, 
		{		//把它的值存到目前結點,然後把這個子孫删了 
			Node *temp = minValueNode(root->right);
			
			root->key = temp->key;
			
			root->right = deleteNode(root->right,
									 temp->key);
		} 
		
	}
	
	//删完後root == NULL就不用檢查以root為根的子樹平不平衡了
	if(root == NULL)
	{
		return root;
	} 
	
	root->height = 1 + max(height(root->left),
						   height(root->right));
	
	int balance = getBalance(root);
	
	if(balance > 1 && getBalance(root->left) >= 0)
	{//LL ---> 右單旋 
		return rightRotation(root); 
	} 
	
	if(balance > 1 && getBalance(root->left) < 0)
	{//LR ----->先左單旋後右單旋
		root->left = leftRotation(root->left);
		return rightRotation(root); 
	} 
	
	if(balance < -1 && getBalance(root->right) <= 0)
	{//RR---->左單旋
		return leftRotation(root);		
	}
	
	if(balance < -1 && getBalance(root->right) > 0)
	{//RL---->先右單旋後左單旋 
		root->right = rightRotation(root->right);
		return leftRotation(root);
	}
	
	return root;
	
}
void printBST(Node *root, int k)
{
	if(root != NULL)
	{
		printBST(root->right,k+5);
		for(int i = 0; i < k; i++)
		{
			cout<<" ";
		}
		cout<<root->key<<endl;
		printBST(root->left,k+5);
	}
}
int main()
{
	Node *root = NULL;
	root = insert(root,10); 
	root = insert(root,5); 
	root = insert(root,11); 
	root = insert(root,3); 
	root = insert(root,6);
	root = insert(root,12); 
	root = insert(root,2); 
	root = insert(root,9);  	  
	printBST(root,0);
	cout<<"------LL---------"<<endl;
	root = deleteNode(root,12);
	printBST(root,0);	
	return 0;
}

結果圖：

AVL樹---最簡單的實作

特意找個删除後是root的左子樹的平衡結點是0(左子樹的左右子樹高度相等)，當

LL

處理沒問題。

寫完了，剛了3個下午應該算搞懂了。如果哪裡錯了，還請各位指出哦！

AVL樹---最簡單的實作

一、定義：

二、分析：

小總結:

三、代碼實作：

繼續閱讀

UVa 122 - Trees on the level

資料結構先序序列建立二叉樹任務描述相關知識程式設計要求測試說明C/C++代碼

1123. Is It a Complete AVL Tree (30)[AVL樹+層序周遊]

AVL樹詳解1. 簡介2. 插入3. 删除4 java代碼例子

二叉平衡樹（AVL）-C語言

『資料結構』AVL樹什麼是AVL樹？AVL樹結點的定義AVL樹的插入AVL樹的旋轉AVL樹的驗證

資料結構-AVL樹

AVL平衡樹的旋轉

[ 資料結構 - C++] AVL樹原理及實作

樹、二叉樹、二叉查找樹、AVL樹、伸展樹、B-樹

Java基礎-樹和二叉樹

2021/3/16 求二叉樹中值為x的結點的層号

#考編上岸#資訊技術樹和二叉樹#資料結構上岸你準備好了嘛！

順序表實作一顆avl樹

認真學習資料結構之AVL樹

AVL樹插入小結