数据结构 - 二叉平衡树 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设备模型（中）之上层容器