程序员修炼手册--AVLTree实现

1.AVLtree概念

2.AVLTree的实现

2.1.AVLtree的节点定义

2.2.AVLTree的插入

2.3，AVL树的验证

2.4，AVL树的查找

3.实现代码

1.AVLtree概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下，因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在olog（n），搜索时间复杂度olog（n）。

2.AVLTree的实现

2.1.AVLtree的节点定义

在构建节点时，我们采用三叉链实现，这样方便我们去插入数据。

//构建成员节点
template
struct AVltreeNode
{
	AVltreeNode* _left;//左孩子
	AVltreeNode* _right;//右孩子
	AVltreeNode* _parent;//父亲节点
	int  _bf;//平衡因子
	pair _kv; //存储的数据
	AVltreeNode(const pair& kv)//构造函数
		:_left(nullptr)
		,_right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _kv(kv)
	{}
};

2.2.AVLTree的插入

2.2.1AVL树就是在搜索二叉树的基础上加入了平衡因子，因此插入可以分为两步

1.按照搜索二叉树的方式插入新节点（左边比插入值小，右边比插入值大）

2.更新平衡因子

2.2.2，插入新节点

1.首先找到插入位置，把数据先连接起来

pair insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			_root = new node(kv);
			return make_pair(_root,true);
		}
		//找到存储位置，把数据插入进去
		node*parent = _root;
		node*cur = _root;
		//找位置,cur当前的位置为空，为将要插入的数据
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, true);
			}
		}
		//插入数据
		cur = new node(kv);
		node*newnode = cur;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
}

2.2.3.更新此时连接在新节点上的这根枝上的平衡因子

a.新节点连在父节点的左边，父节点平衡因子-1，连接在父节点右边，父节点平衡因子-1

其遵循的规则是右树高度（h1）-左树高度（h2）

2.2.4，平衡因子等于2或者-2，旋转树，使得树平衡，满足AVL树的规则

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

a. 新节点插入较高左子树的左侧---左左：右单旋

代码如下：

	//右旋转
void RotateR(node*parent)
{
		node* subL = parent->_left; 
		node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)//如果sublr不为空，sublr连接到右树的左边
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;//连接
		node*parentparent = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)//判断parent是否等于根
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else  //不是根处理
		{
			if (parentparent->_left == parent)
			{
			 parentparent->_left=subL;
			}
			else
			{
				parentparent->_right = subL;
			}
			subL->_parent = parentparent;
		}
		subL->_bf = parent->_bf = 0;
}

b. 新节点插入较高右子树右边---左旋转

代码如下：

void RotateL(node*parent)//左旋
{
	node*subR = parent->_right;
	node*subRL = subR->_left;
	parent->_right = subRL;
	//先将右树的数据挪过来
	//再去处理父子关系和根
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	node*parentparent = parent->_parent;
	parent->_parent = subR;
	if (_root == parent)
	{
		_root=subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (parentparent->_left == parent)
		{
			parentparent->_left = subR;
		}
		else
		{
			parentparent->_right = subR;
		}
		subR->_parent = parentparent;
	}
	parent->_bf = subR->_bf = 0;  //更新平衡因子
}

c. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

此时这种情况下就需要调节平衡因子，需要单独更新parent，subL，subLr的平衡因子

代码段：

void RotateLR(node*parent)
{
	node*subL = parent->_left;
	node*subLR = subL->_right;
	int bf = subLR->_bf;
	RotateL(parent->_left);
	RotateR(parent);
	//更新平衡因子
	if (bf == -1) //新增节点在b树左边
	{
		parent->_bf = 1;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else if (bf == 1)//新增节点在b树右边
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == 0)  //旋转完以后只有三个数据
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

d，新节点插入较高右子树的左侧---右左：先右单旋再左单旋

与c相同，均需更新平衡因子

oid RotateRL(node*parent)
{
	node*subR = parent->_right;
	node*subRL = subR->_left;
	int bf = subRL->_bf; 
	
	RotateR(parent->_right);
	RotateL(parent);
	if (bf == 1)//在c树右边
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == -1)//在c树左边
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf==0)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

2.3，AVL树的验证

方法按照之前的搜索二叉树一样，递归查看左右子树的高度，再去比较右减左的平衡因子，与高度差是否一致

int _height(node*root)//检查树的高度
{
	if (root == nullptr)
	{
		return 0;
	}
	int leftheight = _height(root->_left);
	int rightheight = _height(root->_right);
	return rightheight > leftheight ? rightheight + 1 : leftheight + 1;
}
bool _isbanlanceTree(node*root)
{
	if (root == nullptr)
	{
		return true;
	}
	int leftHeight = _height(root->_left);
	int rightHeight = _height(root->_right);
	//检查平衡因子是否正确
	if (rightHeight - leftHeight != root->_bf)
	{
		cout << "平衡因子异常:" << root->_kv.first << endl;
	}
	return abs(rightHeight - leftHeight) < 2
		&& _isbanlanceTree(root->_left)
		&& _isbanlanceTree(root->_right);
}
bool isAVltree()
{
	return _isbanlanceTree(_root);
}

2.4，AVL树的查找

使用kv的第一个元素向下查找，与二叉搜索树的查找方法一致。

node*find(const K& key)
{
	node*cur = _root;
	while (cur)
	{
		if (cur->_kv.first < key)
		{
			cur = cur->_right;
		}
		else if (cur->_kv.first > key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

3.实现代码

AVLtree.h

#pragma once
#include
#include
#include
using namespace std;

//构建成员节点
template
struct AVltreeNode
{
	AVltreeNode* _left;//左孩子
	AVltreeNode* _right;//右孩子
	AVltreeNode* _parent;//父亲节点
	int  _bf;//平衡因子
	pair _kv; //存储的数据
	AVltreeNode(const pair& kv)//构造函数
		:_left(nullptr)
		,_right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _kv(kv)
	{}
};
template
class AVLTree
{
	typedef AVltreeNode  node;
public:
	AVLTree()
		:_root(nullptr)
	{}
	void _destory(node*root)
	{
		if (root == nullptr)
		{
			return;
		}
		_destory(root->_left);
		_destory(root->_right);
		delete root;
	}
	~AVLTree()//析构
	{
		_destory(_root);
		_root = nullptr;
	}
	//方括号引用
	V& operator[](const K& key)
	{
		pair ret = insert(make_pair(key, V()));
		return ret.first->_kv.second;
	}
	pair insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			_root = new node(kv);
			return make_pair(_root,true);
		}
		//找到存储位置，把数据插入进去
		node*parent = _root;
		node*cur = _root;
		//找位置,cur当前的位置为空，为将要插入的数据
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, true);
			}
		}
		//插入数据
		cur = new node(kv);
		node*newnode = cur;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		//控制平衡因子
		//更新平衡因子
		//不平衡，旋转使其平衡
		while (cur != _root)
		{
			if (parent->_left == cur)//更新枝的平衡因子
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}


			if (parent->_bf == 0)//停止更新，跳出循环
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//parent所在的子树高度变了，会影响parent-》parent
				//需要向上更新
				cur = parent;
				parent = parent->_parent;
			}

			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//此时树已经不平衡了，需要旋转处理
				if (parent->_bf == -2)
				{
					if (cur->_bf == -1)
					{
						//右旋转
						RotateR(parent);
					}
					else //cur->_bf=1
					{
						//左右双旋
						RotateLR(parent);
					}
				}
				else  //parent->_bf=2
				{
					if (cur->_bf = 1)
					{
						//左单旋
						RotateL(parent);
					}
					else   //cur->_bf=-1
					{
						//右左双旋
						RotateRL(parent);
					}
				}
				break;
			}

			else
			{
				assert(false);
			}
		}
		return make_pair(newnode, true);
	}
	//右旋转
void RotateR(node*parent)
{
		node* subL = parent->_left; 
		node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)//如果sublr不为空，sublr连接到右树的左边
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;//连接
		node*parentparent = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)//判断parent是否等于根
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else  //不是根处理
		{
			if (parentparent->_left == parent)
			{
			 parentparent->_left=subL;
			}
			else
			{
				parentparent->_right = subL;
			}
			subL->_parent = parentparent;
		}
		subL->_bf = parent->_bf = 0;
}

void RotateL(node*parent)//左旋
{
	node*subR = parent->_right;
	node*subRL = subR->_left;
	parent->_right = subRL;
	//先将右树的数据挪过来
	//再去处理父子关系和根
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	node*parentparent = parent->_parent;
	parent->_parent = subR;
	if (_root == parent)
	{
		_root=subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (parentparent->_left == parent)
		{
			parentparent->_left = subR;
		}
		else
		{
			parentparent->_right = subR;
		}
		subR->_parent = parentparent;
	}
	parent->_bf = subR->_bf = 0;


}


void RotateLR(node*parent)
{
	node*subL = parent->_left;
	node*subLR = subL->_right;
	int bf = subLR->_bf;
	RotateL(parent->_left);
	RotateR(parent);
	//更新平衡因子
	if (bf == -1) //新增节点在b树左边
	{
		parent->_bf = 1;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else if (bf == 1)//新增节点在b树右边
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == 0)  //旋转完以后只有三个数据
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

void RotateRL(node*parent)
{
	node*subR = parent->_right;
	node*subRL = subR->_left;
	int bf = subRL->_bf; 
	
	RotateR(parent->_right);
	RotateL(parent);
	if (bf == 1)//在c树右边
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == -1)//在c树左边
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf==0)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}
node*find(const K& key)
{
	node*cur = _root;
	while (cur)
	{
		if (cur->_kv.first < key)
		{
			cur = cur->_right;
		}
		else if (cur->_kv.first > key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}
void _inorder(node*root)
{
	if (root == nullptr)
	{
		return;
	}
	_inorder(root->_left);
	cout << root->_kv.first << ":" << root->_kv.second << endl;
	_inorder(root->_right);
}
void inorder()
{
	_inorder(_root);
}
int _height(node*root)//检查树的高度
{
	if (root == nullptr)
	{
		return 0;
	}
	int leftheight = _height(root->_left);
	int rightheight = _height(root->_right);
	return rightheight > leftheight ? rightheight + 1 : leftheight + 1;
}
bool _isbanlanceTree(node*root)
{
	if (root == nullptr)
	{
		return true;
	}
	int leftHeight = _height(root->_left);
	int rightHeight = _height(root->_right);
	//检查平衡因子是否正确
	if (rightHeight - leftHeight != root->_bf)
	{
		cout << "平衡因子异常:" << root->_kv.first << endl;
	}
	return abs(rightHeight - leftHeight) < 2
		&& _isbanlanceTree(root->_left)
		&& _isbanlanceTree(root->_right);
}
bool isAVltree()
{
	return _isbanlanceTree(_root);
}
private:
	node* _root;

};

测试代码：

#include"AVLtree.h"
//void TestAVLTree()
//{
//	int a[] = { 1, 3, 5, 7, 6};
//	AVLTree t;
//	for (auto e : a)
//	{
//		t.insert(make_pair(e, e));
//	}
//
//
//	t.inorder();
//}
void TestAVLTree()
{
	
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree t;
	for (auto e : a)
	{
		t.insert(make_pair(e, e));
		cout << "插入" << e << "->" << t.isAVltree() << endl;
	}

	t.inorder();
	cout << t.isAVltree() << endl;
	t.inorder();
	t[3] *= 10;
	t[4] *= 10;
	t[5] *= 10;
	t.inorder();

	AVLTree dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("left", "左边"));
	dict.inorder();

	dict["left"] = "左边+剩余";
	dict["string"] = "字符串";
	dict.inorder();
}

int main()
{
	TestAVLTree();
	return 0;
}

程序员修炼手册--AVLTree实现

2.AVLTree的实现

C/C++/C#相关栏目本月热门文章