C++&&数据结构——AVL树

一，关于AVL树

根据前面对二叉搜索树的学习我们可以了解到二叉搜索树可以提高查找的效率，但是如果数据本身有序，搜索树将退化成单支树，查找时相当于顺序表查找，效率低下，如下图：

为了解决上面的问题，来自俄罗斯的两位天才数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种方法：当二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差绝对值不超过1，即可降低树的高度，减少平均搜索长度。这就是AVL树，也称平衡二叉搜索树

AVL树具有以下性质：

①它左右子树都是AVL树

②左右子树高度差绝对值不超过1 （这里高度差我们简称为平衡因子）

下面就是一个典型的AVL树：

二，AVL树节点和结构定义

2.1 节点定义

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;//祖先，三叉链，可以倒着遍历

	pair<K, V> _kv;
	int _bf;//balance factor  平衡因子,控制平衡时比较高度

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

2.2 结构定义

template<class K,class V>
struct AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:

private:
    Node* _root = nullptr;
}

三，AVL树插入*

3.1 树的插入与平衡因子的更新

AVL树的插入和前面的二叉搜索树大体相同，只是需要多维护parent指针，更新判断平衡因子以及旋转

bool Insert(const pair<K, V>& kv)//插入和搜索树的结构差不多
{
	//先按搜索树的结构把值插入
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first)//插入的值比根大
		{
			parent = cur;
			cur = cur->_right;//往右走
		}
		else if (cur->_kv.first > kv.first)//插入的值比根小
		{
			parent = cur;
			cur = cur->_left;//往左走
		}
		else//插入的值相等
		{
			return false;
		}
	}
    //已经走到要插入的位置了
	cur = new Node(kv);
	if (parent->_kv.first < kv.first)//要插入的值比父节点大，链接在右边
	{
		parent->_right = cur;
	}
	else //要插入的值比父节点小，链接在左边
	{
		parent->_left = cur;
	}
	//插入后要维护parent，反向链接
	cur->_parent = parent;

	//插入完成，接下来控制平衡//
	//更新平衡因子，如果更新过后，平衡因子没有出现问题，说明插入对树结构没有影响，不需要处理 bf的绝对值<=1
	//①新增在右，parebt->bf++; 新增在左，parent->bf--
	//②更新后parent->bf == 1 or -1,说明parent插入前的平衡因子是0，说明左右子树高度相等，插入后有一边高，parent的高度变了，需要继续往上更新
	//③更新后parent->bf ==0,说明parent插入前的平衡因子是1 or -1,左右子树一边高一边低，插入后一样高了，不需要往上更新
	//④更新后parent->bf == 2 or -2,说明之前是1或-1，已经是平衡的临界值，已打破平衡，parent所在的子树需要旋转处理。
	while (parent)//往上更新平衡因子，并判断是否需要旋转
	{
		//规则①
		if (cur == parent->_right)
		{
			parent->_bf++;
		}
		else
		{
			parent->_bf--;
		}
		//规则②
		if (parent->_bf == 0)
		{
			break;//不需要更新，跳出循环
		}
		//规则③
		else if (abs(parent->_bf) == 1)
		{
			parent = parent->_parent;//往上跳，利用循环持续更新平衡因子
			cur = cur->_parent;
		}
        //规则④
		else if (abs(parent->_bf) == 2)//已出现问题，需要旋转处理，目的是让这棵树平衡，其次使树的高度恢复正常
		{
			//这部分是旋转的具体实现部分
            //具体看下面的旋转部分
		}
		else
		{
			assert(false);//错误，直接报错
		}
	}
	return true;
}

3.2 树的旋转

3.2.1 右单旋

我们在a子树插入一个节点，那么a的子树高度从h变为h+1，导致父节点平衡因子减一变成-1，祖父节点平衡因子也减一变成-2，绝对值大于1了，引发右旋转，如上图，需要改变的指针已用不同颜色标出，具体实现如下代码：

if (parent->_bf == -2 && cur->_bf == -1)
{
	RotateR(parent);
}

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	//subLR可能是空
	if (subLR)
	{
		subLR->_parent = parent;
	}
	//记录一下要旋转的parent节点的_parent，用于当parent是子树根时的调整
	Node* ppNode = parent->_parent;

	subL->_right = parent;
	parent->_parent = subL;

	//parent是整颗树的根
	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}
		subL->_parent = ppNode;
	}
	//调整sub和parent的平衡因子
	subL->_bf = parent->_bf = 0;
}

3.2.2 左单旋

如图所示，我们在c子树插入一个节点，和右单选情况一样，导致祖父节点平衡因子绝对值大于1了，需要旋转处理，需要处理的指针已用不同颜色标出，具体代码实现如下：

else if (parent->_bf == 2 && cur->_bf == 1)
{
	RotateL(parent);
}

void RotateL(Node* parent)
{
	Node* subR = parent->_right; //结合图来看
	Node* subRL = subR->_left;

	parent->_right = subRL; 
	//subRL可能是空
	if (subRL) //维护subRL的parent
	{
		subRL->_parent = parent;
	}
	//记录一下要旋转的parent节点的_parent，用于当parent是子树根时的调整
	Node* ppNode = parent->_parent;

	subR->_left = parent;
	parent->_parent = subR; //维护原来parent的parent
	//parent是整棵树的根
	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else//parent是子树的根
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subR;
		}
		else
		{
			ppNode->_right = subR;
		}
		subR->_parent = ppNode;
	}
	//调整sunR和parent的平衡因子
	subR->_bf = parent->_bf = 0;
}

3.2.3 左右双旋

?如上图所示，左右双旋其实就是先左单旋转再右单旋，先在b子树插入一个值，导致祖父节点平衡因子大于1，（这种情况比较复杂，建议多把流程图看几遍）我们先以30为子树根节点进行左旋，使树的“中间高”变为“一边高”，然后再以90为根进行右单旋转达到平衡，具体代码实现如下：

else if (parent->_bf == -2 && cur->_bf == 1)
{
	RotateLR(parent);
}

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RotateL(parent->_left);//复用
	RotateR(parent);

	//平衡因子的更新
	if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
	}
	else if(bf ==0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

3.3.4 右左双旋

右左双旋和前面的差不多，直接看图理解即可，具体代码实现如下：

else if (parent->_bf == 2 && cur->_bf == -1)
{
	RotateRL(parent);
}

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处插入
	{
		subR->_bf = 0;
		parent->_bf = -1;
		subRL->_bf = 0;
	}
	else if(bf == -1)
	{
		subR->_bf = 1;
		parent->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

四，AVL树其他接口实现

4.1 打印函数

public:
    void InOrder()
    {
	    _InOrder(_root);
	    cout << endl;
    }

private:
    void _InOrder(Node* root)
    {
	    if (root == nullptr)
	    {
		    return;
	    }

	    _InOrder(root->_left);
	    cout << root->_kv.first << ":" << root->_kv.second << endl;
	    _InOrder(root->_right);
    }

4.2 判断平衡因子函数

private:
    int Height(Node* root)
    {
	    if (root == nullptr)
		    return 0;

	    return max(Height(root->_left),Height(root->_right)) + 1;
    }
    //判断平衡因子函数
    bool _IsBalance(Node* root) //不能直接检查平衡因子，因为是我们自己更新的，无法保证全部更新正确，所以需要老老实实去求高度
    {
	    if (root == nullptr) //空树也可以认为是平衡树
		    return true;

	    int leftHt = Height(root->_left);
	    int rightHt = Height(root->_right);
	    int diff = rightHt - leftHt;

	    if (diff != root->_bf) //在判断是否是AVL树的同时，检查平衡因子是否有问题，防止蝴蝶效应
	    {
		    cout << root->_kv.first << "平衡因子错误" << endl;
		    return false;
	    }

	    return abs(diff) < 2
		    && _IsBalance(root->_left)
		    && _IsBalance(root->_right);//还需要递归去看子树
    }

五，AVL树源代码与测试代码

?头文件

#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
#include<time.h>
using namespace std;

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;//祖先，三叉链，可以倒着遍历

	pair<K, V> _kv;
	int _bf;//balance factor  平衡因子,控制平衡时比较高度

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

template<class K,class V>
struct AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)//插入和搜索树的结构差不多
	{
		//先按搜索树的结构把值插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)//插入的值比根大
			{
				parent = cur;
				cur = cur->_right;//往又走
			}
			else if(cur->_kv.first > kv.first)//插入的值比根小
			{
				parent = cur;
				cur = cur->_left;//往左走
			}
			else//插入的值相等
			{
				return false;
			}
		}//已经走到要插入的位置了
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)//要插入的值大，链接在右边
		{
			parent->_right = cur;
		}
		else //比我小，插在左边
		{
			parent->_left = cur;
		}
		//插入后要维护parent，反向链接
		cur->_parent = parent;

		//插入完成，接下来控制平衡//
		//1，更新平衡因子，如果更新过后，平衡因子没有出现问题，说明插入对树结构没有影响，不需要处理 bf的绝对这<=1
		//①新增在右，parebt->bf++;新增在左，parent->bf--
		//②更新后parent->bf == 1 or -1,说明parent插入前的平衡因子是0，说明左右子树高度相等，插入后有一边高，parent的高度变了，需要继续往上更新
		//③更新后parent->bf ==0,说明parent插入前的平衡因子是1 or -1,左右子树一边高一边低，插入后一样高了，不需要往上更新
        //④更新后parent->bf == 2 or -2,说明之前是1或-1，已经是平衡的临界值，已打破平衡，parent所在的子树需要旋转处理。
		while (parent)//往上更新平衡因子，并判断是否需要旋转
		{
			//规则①
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}
			//在矮的那边插入了一个
			if (parent->_bf == 0)
			{
				break;//不需要更新，跳出循环
			}
			//parent所在的子树高度变了，需要继续更新
			else if (abs(parent->_bf) == 1)
			{
				parent = parent->_parent;//往上跳
				cur = cur->_parent;
			}
			else if (abs(parent->_bf) == 2)//已出现问题，需要旋转处理///目的是让这棵树平衡，其次使树的高度恢复正常
			{
				//旋转原则：保持它继续是平衡树
				//旋转目的：左右均衡，降低整棵树的高度
				//左单旋
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				//右单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				//左右双旋转
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				//右左双旋转
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);//错误，直接报错
			}
		}
		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
private:
	//打印子函数
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
	//求高度函数
	int Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		return max(Height(root->_left),Height(root->_right)) + 1;
	}
	//判断平衡因子函数
	bool _IsBalance(Node* root) //不能直接检查平衡因子，因为是我们自己更新的，无法保证全部更新正确，所以需要老老实实去求高度
	{
		if (root == nullptr) //空树也可以认为是平衡树
			return true;

		int leftHt = Height(root->_left);
		int rightHt = Height(root->_right);
		int diff = rightHt - leftHt;

		if (diff != root->_bf) //在判断是否是AVL树的同时，检查平衡因子是否有问题，防止蝴蝶效应
		{
			cout << root->_kv.first << "平衡因子错误" << endl;
			return false;
		}

		return abs(diff) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);//还需要递归去看子树
	}
private:
	//旋转的价值和意义
	// ①使子树保持平衡
	// ②使高度恢复到插入之前的样子
	
	//左旋转函数
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right; //结合图来看
		Node* subRL = subR->_left;

		parent->_right = subRL; 
		//subRL可能是空
		if (subRL) //维护subRL的parent
		{
			subRL->_parent = parent;
		}
		//记录一下要旋转的parent节点的_parent，用于当parent是子树根时的调整
		Node* ppNode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR; //维护原来parent的parent
		//parent是整棵树的根
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else//parent是子树的根
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
		//调整sunR和parent的平衡因子
		subR->_bf = parent->_bf = 0;
	}

	//右旋转函数
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		//subLR可能是空
		if (subLR)
		{
			subLR->_parent = parent;
		}
		//记录一下要旋转的parent节点的_parent，用于当parent是子树根时的调整
		Node* ppNode = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		//parent是整颗树的根
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
		//调整sub和parent的平衡因子
		subL->_bf = parent->_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)//板书里的c处插入
		{
			parent->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)//从b处插入
		{
			/*parent->_bf = 0;
			subL->_bf = 1;*/

			parent->_bf = 1;
			subL->_bf = 0;
		}
		else if(bf ==0)//板书的第三种情况
		{
			parent->_bf = 0;
			subL->_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处插入
		{
			subR->_bf = 0;
			parent->_bf = -1;
			subRL->_bf = 0;
		}
		else if(bf == -1)
		{
			subR->_bf = 1;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
private:
	Node* _root = nullptr;
};

测试代码

#include"AVLTree.h"
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;

void TestAVLTree1()
{
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };//专门用来测试双旋平衡因子的测试用例
	//int a[] = { 16,3,7,11,9,26,8,14,15 };
	AVLTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
	}
	t1.InOrder();
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

void TestAVLTree2()//上随机值来当测试用例
{
	size_t N = 10000;
	srand(time(0));
	AVLTree<int, int> t1;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand();//产生随机值
		t1.Insert(make_pair(x, i));
		//关掉srand创造闭线条件，每次插入值都调用IsBalabce，找到哪个值插入时导致问题
		/*bool ret = t1.IsBalance();
		if (ret == false)
		{
			int u = 1;
		}
		else
		{
			cout << "Insert:" << x << "IsBalance:" << ret << endl;
		}*/
	}
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

//高度平衡二叉搜索树
int main()
{
	TestAVLTree2();
	return 0;
}