資料結構 - 二叉平衡樹 AVL Tree

1. 平衡條件
2. 失衡情景
3. 兩種旋轉
- 3.1 單旋轉
- 3.2 雙旋轉
4. 插入、删除
- 4.1 插入
- 4.2 删除
5. 完整程式
6. 更多思考

二叉平衡樹是基于二叉查找樹的基礎之上，增加了平衡條件，避免二叉查找樹在一定次數的插入/删除操作之後，左右失衡。如果對二叉查找樹不了解，可以點選這裡。

一、平衡條件

除了二叉查找樹的性質，平衡二叉樹的每個結點，其左子樹和右子樹的高度差不超過1。

平衡條件就要求樹結點需要額外的變量存儲高度，是以樹的結構如下。

struct AVLNode{
	int value;
	AVLNode *left, *right;
	int height;
	AVLNode(int val):value(val), left(NULL), right(NULL), height(0){}
};

class AVLTree{
public:
	AVLTree(): root(NULL){}
	AVLTree(vector<int> &arr);
	void Insert(int val);
	void Delete(int val);
	void PostOrder();
	AVLNode* getMin(AVLNode* T);
	void Clear();
private:
	AVLNode* SingleLeftRotation(AVLNode* K2);
	AVLNode* SingleRightRotation(AVLNode* K2);
	AVLNode* DoubleLeftRotation(AVLNode* K3);
	AVLNode* DoubleRightRotation(AVLNode* K3);
	AVLNode* RecursiveInsert(int val, AVLNode* T);
	AVLNode* RecursiveDelete(int val, AVLNode* T);
	AVLNode* RecursiveClear(AVLNode* T);
	void RecursivePostOrder(AVLNode* T);
	int Height(AVLNode* T);
	AVLNode* root;
};

二、失衡情景

有了這個限制，每當我們進行insert操作時，就需要檢測插入的結點是否違背了平衡條件。

如果出現違背，可以假設該結點為α，它的兩顆子樹的高度相差2。這種不平衡可能出現在下面4中情況中：

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

b. 對α的左兒子的右子樹進行一次插入

c. 對α的右兒子的左子樹進行一次插入

d. 對α的右兒子的右子樹進行一次插入

資料結構 - 二叉平衡樹 AVL Tree

可以看出，a和d互相鏡像，b和c互相鏡像，分别對應單旋轉和雙旋轉。

三、兩種旋轉

3.1 單旋轉

資料結構 - 二叉平衡樹 AVL Tree

上圖是a中左-左的情況，k2結點不滿足平衡性，需要如圖示旋轉，d相似。

//a: 左-左
AVLNode* AVLTree::SingleLeftRotation(AVLNode* K2){
	AVLNode* K1 = K2->left;
	K2->left = K1->right;
	K1->right = K2;
	K2->height = max(Height(K2->left), Height(K2->right)) + 1;
	K1->height = max(Height(K1->left), Height(K1->right)) + 1;
	return K1;
}
//d: 右-右
AVLNode* AVLTree::SingleRightRotation(AVLNode* K2){
	AVLNode* K1 = K2->right;
	K2->right = K1->left;
	K1->left = K2;
	K2->height = max(Height(K2->left), Height(K2->right)) + 1;
	K1->height = max(Height(K1->left), Height(K1->right)) + 1;
	return K1;
}

3.2 雙旋轉

資料結構 - 二叉平衡樹 AVL Tree

上圖是b中左-右的情況，k3結點不滿足平衡性，需要進行兩次單旋轉，得到圖示效果，c相似。

//b： 左-右
AVLNode* AVLTree::DoubleLeftRotation(AVLNode* K3){
	K3->left = SingleRightRotation(K3->left);
	return SingleLeftRotation(K3);
}

//c：右-左
AVLNode* AVLTree::DoubleRightRotation(AVLNode* K3){
	K3->right = SingleLeftRotation(K3->right);
	return SingleRightRotation(K3);
}

四、插入、删除

無論是插入還是删除操作，過程中都需要判斷結點的失衡問題，是以首先要定義一個傳回高度的函數。

int AVLTree::Height(AVLNode* T){
	if(!T) return -1;
	else return T->height;
}

4.1 插入

采用遞歸的方式，每次遞歸結束進行平衡判斷。

void AVLTree::Insert(int val){
	root = RecursiveInsert(val, root);
}

AVLNode* AVLTree::RecursiveInsert(int val, AVLNode* T){
	if(!T) T = new AVLNode(val);
	else if(val > T->value){
		T->right = RecursiveInsert(val, T->right);
		if(Height(T->right) - Height(T->left) == 2){
			if(val > T->right->value)
				T = SingleRightRotation(T);
			else T = DoubleRightRotation(T);
		}
	}
	else if(val < T->value){
		T->left = RecursiveInsert(val, T->left);
		if(Height(T->left) - Height(T->right) == 2){
			if(val > T->left->value)
				T = DoubleLeftRotation(T);
			else T = SingleLeftRotation(T);
		}
	}
		
	T->height = max(Height(T->left), Height(T->right)) + 1; //高度更新
	return T;
}

4.2 删除

二叉平衡樹的删除要比插入要複雜，如果删除次數不多，可以考慮lazy deletion。

不過，這裡我主要展示普通删除：采用遞歸方式，每次删除遞歸結束，要對平衡進行判斷，删除是對結點類型進行讨論。

void AVLTree::Delete(int val){
	root = RecursiveDelete(val, root);
}

AVLNode* AVLTree::RecursiveDelete(int val, AVLNode* T){
	if(!T) return NULL;
	if(val > T->value){
		T->right = RecursiveDelete(val, T->right);
		
		if(Height(T->left) - Height(T->right) == 2){
			if(Height(T->left->left) >= Height(T->left->right)){
				T = SingleLeftRotation(T);
			}
			else{
				T = DoubleLeftRotation(T);
			}
		}
	}
	else if(val < T->value){
		T->left = RecursiveDelete(val, T->left);
		if(Height(T->right) - Height(T->left) == 2){
			if(Height(T->right->right) >= Height(T->right->left)){
				T = SingleRightRotation(T);
			}
			else {
				T = DoubleRightRotation(T);
			}
		}
	}
	else{ 
		if(T->left && T->right){ //删除存在左右子樹的結點
			T->value = getMin(T->right)->value;
			T->right = RecursiveDelete(T->value, T->right);
		}
		else{//删除隻有一個子樹或者沒有子樹的結點
			AVLNode* tmp = T;
			if(!T->left) T = T->right;
			else if(!T->right) T = T->left;
			delete tmp; tmp = NULL;
		}
	}

	if(T) T->height = max(Height(T->left), Height(T->right)) + 1;
	return T;
}

五、完整程式

AVLTree.h

#pragma once
#include <vector>
using namespace std;

/* 平衡二叉樹 AVL Tree
 * 性質：平衡二叉樹的每個結點，其左子樹和右子樹的高度差不超過1.
 * 存儲height->根據height判斷imbalance->single rotation or double rotation
*/

struct AVLNode{
	int value;
	AVLNode *left, *right;
	int height;
	AVLNode(int val):value(val), left(NULL), right(NULL), height(0){}
};

class AVLTree{
public:
	AVLTree(): root(NULL){}
	AVLTree(vector<int> &arr);
	void Insert(int val);
	void Delete(int val);
	void PostOrder();
	AVLNode* getMin(AVLNode* T);
	void Clear();
private:
	AVLNode* SingleLeftRotation(AVLNode* K2);
	AVLNode* SingleRightRotation(AVLNode* K2);
	AVLNode* DoubleLeftRotation(AVLNode* K3);
	AVLNode* DoubleRightRotation(AVLNode* K3);
	AVLNode* RecursiveInsert(int val, AVLNode* T);
	AVLNode* RecursiveDelete(int val, AVLNode* T);
	AVLNode* RecursiveClear(AVLNode* T);
	void RecursivePostOrder(AVLNode* T);
	int Height(AVLNode* T);
	AVLNode* root;
};

AVLTree.cpp

#include "AVLTree.h"
#include <algorithm>
#include <iostream>
using namespace std;

AVLTree::AVLTree(vector<int> &arr){
	for(auto &i: arr)
		Insert(i);
}

int AVLTree::Height(AVLNode* T){
	if(!T) return -1;
	else return T->height;
}

void AVLTree::Insert(int val){
	root = RecursiveInsert(val, root);
}

AVLNode* AVLTree::RecursiveInsert(int val, AVLNode* T){
	if(!T) T = new AVLNode(val);
	else if(val > T->value){
		T->right = RecursiveInsert(val, T->right);
		if(Height(T->right) - Height(T->left) == 2){
			if(val > T->right->value)
				T = SingleRightRotation(T);
			else T = DoubleRightRotation(T);
		}
	}
	else if(val < T->value){
		T->left = RecursiveInsert(val, T->left);
		if(Height(T->left) - Height(T->right) == 2){
			if(val > T->left->value)
				T = DoubleLeftRotation(T);
			else T = SingleLeftRotation(T);
		}
	}
		
	T->height = max(Height(T->left), Height(T->right)) + 1;
	return T;
}

AVLNode* AVLTree::getMin(AVLNode* T){
	if(!T) return NULL;
	if(!T->left) return T;
	else return getMin(T->left);
}

void AVLTree::Delete(int val){
	root = RecursiveDelete(val, root);
}

AVLNode* AVLTree::RecursiveDelete(int val, AVLNode* T){
	if(!T) return NULL;
	if(val > T->value){
		T->right = RecursiveDelete(val, T->right);
		
		if(Height(T->left) - Height(T->right) == 2){
			if(Height(T->left->left) >= Height(T->left->right)){
				T = SingleLeftRotation(T);
				//cout << "Delete: single left rotation." << endl;
			}
			else{ 
				//cout << "Delete: double left rotation." << endl;
				T = DoubleLeftRotation(T);
			}
		}
	}
	else if(val < T->value){
		T->left = RecursiveDelete(val, T->left);
		if(Height(T->right) - Height(T->left) == 2){
			if(Height(T->right->right) >= Height(T->right->left)){
				T = SingleRightRotation(T);
				//cout << "Delete: single right rotation." << endl;
			}
			else {
				//cout << "Delete: ouble right rotation." << endl;
				T = DoubleRightRotation(T);
			}
		}
	}
	else{
		if(T->left && T->right){
			T->value = getMin(T->right)->value;
			T->right = RecursiveDelete(T->value, T->right);
		}
		else{
			AVLNode* tmp = T;
			if(!T->left) T = T->right;
			else if(!T->right) T = T->left;
			delete tmp; tmp = NULL;
		}
	}

	if(T) T->height = max(Height(T->left), Height(T->right)) + 1;
	return T;
}

void AVLTree::Clear(){
	root = RecursiveClear(root);
}

AVLNode* AVLTree::RecursiveClear(AVLNode* T){
	if(!T) return NULL;
	T->left = RecursiveClear(T->left);
	T->right = RecursiveClear(T->right);
	delete T; T = NULL;
	return T;
}


AVLNode* AVLTree::SingleLeftRotation(AVLNode* K2){
	AVLNode* K1 = K2->left;
	K2->left = K1->right;
	K1->right = K2;
	K2->height = max(Height(K2->left), Height(K2->right)) + 1;
	K1->height = max(Height(K1->left), Height(K1->right)) + 1;
	return K1;
}

AVLNode* AVLTree::SingleRightRotation(AVLNode* K2){
	AVLNode* K1 = K2->right;
	K2->right = K1->left;
	K1->left = K2;
	K2->height = max(Height(K2->left), Height(K2->right)) + 1;
	K1->height = max(Height(K1->left), Height(K1->right)) + 1;
	return K1;
}

AVLNode* AVLTree::DoubleLeftRotation(AVLNode* K3){
	K3->left = SingleRightRotation(K3->left);
	return SingleLeftRotation(K3);
}

AVLNode* AVLTree::DoubleRightRotation(AVLNode* K3){
	K3->right = SingleLeftRotation(K3->right);
	return SingleRightRotation(K3);
}

void AVLTree::PostOrder(){
	RecursivePostOrder(root);
}

void AVLTree::RecursivePostOrder(AVLNode* T){
	if(!T) return;
	RecursivePostOrder(T->left);
	RecursivePostOrder(T->right);
	cout << T->value << "(" << T->height << ")  ";
}

main.cpp

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

int main(){
	//vector<int> arr = {3, 2, 1, 4, 5, 6, 7}; //only single rotaion
	vector<int> arr = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
	AVLTree test(arr);
	cout << "Before deleting 12: ";
	test.PostOrder();
	cout << endl;

	test.Delete(12); //single rotation
	//test.Delete(8); //double rotaion
	cout << "After deleting 12: ";
	test.PostOrder();
	cout << endl;

	test.Clear();
	cout << "After clearing: ";
	test.PostOrder();
	cout << endl;
}

Output

Before deleting 12: 1(0)  3(0)  2(1)  5(0)  6(1)  4(2)  8(0)  10(0)  9(1)  12(0)  11(2)  14(0)  16(0)  15(1)  13(3)  7(4)
After deleting 12: 1(0)  3(0)  2(1)  5(0)  6(1)  4(2)  8(0)  10(0)  11(1)  9(2)  14(0)  16(0)  15(1)  13(3)  7(4)
After clearing:

六、更多思考

雖然二叉平衡術相較于二叉查找樹而言，解決了樹的不平衡問題，但針對對于資料通路卻有缺陷。如果有一個結點在樹的底層，我們百分之八十的時間都想要通路它，那效率不免有些低下。因而，我們需要求助于另外一個樹的結構–伸展樹。

資料結構 - 二叉平衡樹 AVL Tree

一、平衡條件

二、失衡情景

三、兩種旋轉

3.1 單旋轉

3.2 雙旋轉

四、插入、删除

4.1 插入

4.2 删除

五、完整程式

AVLTree.h

AVLTree.cpp

main.cpp

Output

六、更多思考

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

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

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

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

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

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