AVLTree【c++实现】

标签：bf subR parent 实现 AVLTree c++ 单旋平衡节点

AVL树

AVLTree的代码实现连接：

AVLTree 代码链接

1.AVL树的概念

学习了二叉搜索树之后，我们知道二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此AVLTree就出现来解决这个问题了。

AVLTree如何解决的呢？——当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

AVLTree也可以叫做高度平衡二叉搜索树

AVLTree的特点：

所有子树的左右子树高度差的绝对值不超过1
所有子树都是AVLTree
AVLTree如果有n个节点，那么其高度保持在log_2_N，搜索的时间复杂度会保持在O(log_2_N)

注意：

上面-1代表对于3这个节点来说，其左子树高度比右子树大1.

1代表右子树高度比左子树高度大1

0代表左右子树高度平衡

2.AVLTree节点的定义

实现AVLTree有多种办法，这里我们选择引入平衡因子。用于判断该树是否平衡

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left; // 左孩子
	AVLTreeNode<K, V>* _right; // 右孩子
	AVLTreeNode<K, V>* _parent; // 节点的父亲

	int _bf; // 平衡因子

	pair<K, V> _kv; // 键值对
    	
	AVLTreeNode(pair<K, V>)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		_kv(pair)
	{}
};

3.AVLTree的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

按照二叉搜索树的规则进行插入
调整平衡因子
根据平衡因子来判断是否平衡，并进行相应处理。【不平衡要旋转】

下图对平衡因子的调整的三种情况进行了分析：

对第一种情况进行解析:

对第二种情况进行解析:

对第三种情况进行解析:

下面是更新平衡因子的代码实现：

		// 更新平衡因子
		while (parent) // 可能会更新到根节点
		{
			// 如果插入的节点是当前parent节点的右孩子
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}

			// 这个时候判断parent的平衡因子的情况是否还要向上调整
			if (parent->_bf == 0)
			{
				// 这个情况说明高度差不变，不需要变化了。
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 这种情况就还要向上调整
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 这种情况就代表着该parent子树已经不平衡了，要进行旋转处理

			}
		}

要完成AVLTree的插入，旋转的实现是必不可少的。

4.AVLTree的旋转

旋转就是保持树仍然是二叉搜索树的前提下，让它变成平衡二叉搜索树【旋的过程可不是乱旋的】

首先要知道什么情况需要旋转，上面也说了，这里在通过图片复习一下：

就是当树出现高度的不平衡的时候，就需要旋转。

旋转分多种情况的旋转：

4.1左单旋

当节点插入较高的左子树的左侧的时候——左单旋

因此根据上面两个进行左单旋的例子，我们可以总结出左单旋的两个重要规律

subR的左孩子变成parent的右孩子
parent会成为subR的左孩子

有了这个规律，我们就可以用一个抽象图来表示左单旋：

可以进行左单旋的情况是非常多的。上面我们的例子就是当h为0和1的情况。

注意：

在插入前，AVL树是平衡的，新节点插入到60的右子树(注意：此处不是右孩子)中，60右子树增加了一层，导致以30为根的二叉树不平衡，要让30这课树平衡，只能将30子树的高度减少一层，左子树增加一层

即将右子树往上提，这样30转下来，因为30比60大，只能将其放在60的左子树，而如果60有左子树，左子树根的值一定大于30，小于60，只能将其放在30的右子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

60节点的左孩子可能存在，也可能不存在

要注意左孩子不存在时，是否存在对空指针的解引用

如果左孩子存在，要处理其父亲指针的链接

30可能是根节点，也可能是子树

如果是根节点，旋转完成后，要更新根节点

如果是子树，可能是某个节点的左子树，也可能是右子树【要提前保存下parent的parent，这样才能在此时进行连接】

左单旋的代码实现如下：

	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		// 处理关系的时候还要注意到父亲指针的变化
		// 1.先让subR的左孩子变成parent的右孩子，再处理subR左孩子的父亲指针
		parent->_right = subRL;
		if(subRL) // 防止当h为0时，也就是subRL的左孩子是空的情况
			subRL->_parent - parent; // 处理父亲指针

		//2.再让parent成为subR的左孩子，并处理parent的父亲指针
		subR->_left = parent;
		Node* ppNode = parent->_parent; // 防止后面subR链接不到parent->_parent，这里要做个保存
		parent->_parent = subR; // 处理父亲指针
		
		//3.subR的父亲指针也需要变化
		// 这里会有两种情况
		// 1.左单旋之后，subR直接是根节点
		if (_root = parent)
		{
			// 原本parent是根节点，左单旋之后subR变成跟节点
			_root = subR;
			subR->_parent = nullptr;
		}
		else //2.parent不是根节点，左单旋完毕之后subR仍然是子树
		{
			// 这个情况说明原本parent是一个子树，左单旋后subR也是一个子树
			// 这个时候就要链接上原本parent的_parent，上面存储起来是ppNode

			// 但是这个时候还得判断左单旋之后的subR应该是ppNode的左子树还是右子树
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
				subR->_parent = ppNode;
			}
			else
			{
				// 原来的parent是ppNode的右子树,也就是subR要变成ppNode的右子树
				ppNode->_right = subR;
				subR->_parent = ppNode;
			}
		}

		// 左单旋之后，还得修改平衡因子，这样才算结束
		subR->_bf = parent->_bf = 0;
	}

4.2右单旋

当节点插入较高的右子树的右侧的时候——右单旋

因此根据上面两个进行右单旋的例子，我们可以总结出右单旋的两个重要规律

subR的右孩子变成parent的左孩子
parent会成为subR右孩子

有了这个规律，我们就可以用一个抽象图来表示右单旋：

上面举的两个例子就是该抽象图中，h为0或者1的情况。

注意：

在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层

即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

30节点的右孩子可能存在，也可能不存在

要注意右孩子不存在时，是否存在对空指针的解引用

如果右孩子存在，要处理其父亲指针的链接

60可能是根节点，也可能是子树

如果是根节点，旋转完成后，要更新根节点

如果是子树，可能是某个节点的左子树，也可能是右子树【要提前保存下parent的parent，这样才能在此时进行连接】

右单旋的代码实现：

// 右单旋
void RotateR(Node* parent)
{
	Node* subR = parent->_left;
	Node* subLR = subR->_right;

	// 处理节点关系的时候要注意处理其父亲指针的关系
	// 1.先让subR的右孩子变成parent的左孩子，再处理subR右孩子的父亲指针
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;// 处理subR右孩子的父亲指针

	// 2.再让parent成为subR的右孩子，再处理parent的父亲指针
	subR->_right = parent;
	Node* ppNode = parent->_parent; // 防止原来的parent是子树，不是根节点
	parent->_parent = subR;// 处理parent的父亲指针

	// 3.再处理更新后的subR的父亲指针
	// 这里又分两种情况
	// 1.一种是parent原先是根节点，subR代替之后，也会变成根节点
	if (_root == parent)
	{
		_root = subR; // subR代替之后，变成根节点
		subR->_parent = nullptr;
	}
	else //2.parent是原先的一个子树，左单旋完毕之后subR仍然是子树
	{
		//原来的parent是其父亲的左子树还是右子树
		if (parent == ppNode->_left)
		{
			// subR替代之后，是ppNode的左子树
			ppNode->_left = subR;
			subR->_parent = ppNode; //处理父亲指针
		}
		else
		{
			// sub替代之后，是ppNode的右子树
			ppNode->_right = subR;
			subR->_parent = ppNode; //处理父亲指针
		}
	}

	//4.处理完毕之后，还要更新平衡因子，这样右单旋才是结束了
	subR->_bf == parent->_bf = 0;
}

4.3左右双旋

左右双旋：其实就是先左单旋，在右单旋。

当给较高的左子树插入一个右节点，就要先左单旋，在右单旋

但是这里会有两种情况

这里虽然有两种情况，但是都是进行左右双旋，即先对30进行左单旋，在对90进行右单旋，规律如下：

左右双旋完毕后，两种情况下，60都为根。
并且60的b给了30的右子树。60的c给了90的左子树【因为b肯定比60小，30大】【c肯定比60大，比90小】
旋转的情况是相同的。两种情况的旋转情况都是一样的

因此左右双旋难得不是旋转，难得是平衡因子的调节。两种情况的平衡因子是不一样的。

并且除了上述两种情况下，还有一种情况也需要对平衡因子特殊处理：

也就是a b c d四个区域都是空的，60节点的插入本身

一共有三种情况，这三种情况的平衡因子都需要进行不同的处理。

因此判断是那种情况并做出相应的平衡因子调节成为了一个重点

代码实现如下：

这里对parent、subL、subLR的位置给个图片，方便代码理解

	// 左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf; // 先记载下来subLR节点的平衡因子，防止被后面的双旋进行干扰

		// 左右双旋 【双旋无关节点的插入情况，旋转都是一样的】
		RotateL(subL);
		Rotatel(parent);

		// 旋转之后需要对三种不同情况的平衡因子进行处理
		// 这里我们通过前面保存的subRL的平衡因子bf来区分节点是插入b还是c,还是abcd四个区域都为空。
		// 这里的a b c d要结合图片理解【博客或者笔记】

		if (bf == -1)
		{
			// 节点插入b区域
			// 此时subLR成为了根节点或者是整棵树的其中一颗子树
			// parent旋转后的bf == 1, subL的bf == 0
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			// 节点插入区域c
			// 此时subLR成为了根节点或者是整棵树的其中一颗子树
			// parent旋转后bf == 0， subL的bf == 1
			parent->_bf = 0;
			subL->_bf = 1;
			subLR->_bf = 0;
		}
		else // bf == 0
		{
			// 此时abcd四个区域都为空。
			// 旋转之后三个节点的bf都为0
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}

	}

4.4右左双旋

左右双旋：其实就是先左单旋，在右单旋。

当给较高的右子树插入一个左节点，就要先右单旋，在左单旋

这里虽然有两种情况，但是都是进行右左双旋，即先对90进行右单旋，在30进行左单旋，规律如下：

右左双旋完毕后，两种情况下，60都为根。
并且60的b给了30的右子树。60的c给了90的左子树【因为b肯定比60小，30大】【c肯定比60大，比90小】
旋转的情况是相同的。两种情况的旋转情况都是一样的

因此双旋难得不是旋转，难得是平衡因子的调节。两种情况的平衡因子是不一样的。

并且除了上述两种情况下，还有一种情况也需要对平衡因子特殊处理：

一共有三种情况，这三种情况的平衡因子都需要进行不同的处理。

因此判断是那种情况并做出相应的平衡因子调节成为了一个重点

代码实现如下：

这里对parent、subR、subRL的位置给个图片，方便代码理解

	// 右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf; // 防止后面的双旋对subRL的平衡因子进行干扰

		// 右左双选的两种情况都是，先右单旋，再左单旋
		RotateR(subR);
		RotateL(parent);

		// 重点是要控制三种情况的平衡因子
		// 这里我们通过前面保存的subRL的平衡因子bf来区分节点是插入b还是c,还是abcd四个区域都为空。
		// 这里的a b c d要结合图片理解【博客或者笔记】

		if (bf == 1)
		{
			// 节点插入c区域
			// 这种情况下，最后subRL成为了根节点或者是其中一个子树
			// 此时parent在旋转之后的平衡因子是-1，subR是0
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// 节点插入b区域
			// 这个情况下，最后subRL成为了根节点或者是其中一个子树
			// 此时subR的平衡因子是1，parent是0
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else // 此时bf == 0
		{
			//这种情况是a、b、c、d四个区域都为空。
			// 刚好插入的节点构成了引发双旋的条件
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
	}

5.AVLTree的验证

要验证AVLTree，需要验证两个方面：

首先是一个二叉搜索树【通过中序遍历，查看是否有序】
高度必须要平衡

验证是否为一个二叉搜索树——通过中序遍历即可：

	// 中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

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

	//cpp中一般实现递归都要通过子函数
	// 因为外边调用这个中序遍历接口的时候没办法直接传一个_root进来，_root是私有的
	void InOrder()
	{
		if (_root == nullptr)
		{
			cout << "该树为空" << endl;
			return;
		}

		_InOrder(_root);
		//_InOrder(this->_root); // 等价于上面的
		cout << endl;
	}

验证高度是否平衡：

这里两个方案：

树的左右子树的高度差的绝对值要<2，就意味着当前树平衡。然后每个左右子树的高度差都 < 2就意味是AVLTree。
计算当前根节点的平衡因子，将其与根节点存的平衡因子对比。如果相同，就意味着当前树平衡，如果每个子树的平衡因子都不出错，就意味着是AVLTree

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

		// 记载左右子树的高度
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		//对于当前层数的根节点来说，左右子树大的那个高度+1，才是这棵树的高度
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	bool _IsBanlance(Node* root)
	{
		if (root == nullptr)
			return true;

		// 计算出左右子树的高度
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		// 如果左右子树高度差的绝对值 < 2 并且 每个左右子树都是满足其左右子树高度差的绝对值<2的话，就是平衡的
		return abs(rightHeight - leftHeight) < 2 && _IsBanlance(root->_left) && _IsBanlance(root->_right);

		// 也可以通过判断平衡因子是否相同，rightHeight - leftHeight计算出当前根节点的平衡因子bf，将其与root->_bf对比。
		// 将每个子树的平衡因子都进行一个对比，如果都是对的，意味着这棵树平衡
		//int bf = rightHeight - leftHeight; // 自己计算的平衡因子
		//return bf == root->_bf && _IsBanlance(root->_left) && _IsBanlance(root->_right);
	}

	bool IsBanlance()
	{
		if (_root == nullptr)
		{
			cout << "该树为空\n";
			return false;
		}

		return _IsBanlance(_root);
	}

测试用例：

void test_AVLTree()
{
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int b[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int, int> avl1;
	AVLTree<int, int> avl2;

	for (auto e : a)
	{
		avl1.insert(pair<int, int>(e, e));
	}
	avl1.InOrder(); // 验证此树为二叉搜索树
	
	// 还得验证高度是否为AVLTree————是否平衡
	cout << avl1.IsBanlance() << endl; // 1
	cout << endl;

	for (auto e : b)
	{
		avl2.insert(pair<int, int>(e, e));
	}
	avl2.InOrder(); // 验证此树为二叉搜索树

    // 是否平衡
	cout << avl2.IsBanlance() << endl; // 1
}

6.AVLTree的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log_2 (N)。

但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

标签：bf,subR,parent,实现,AVLTree,c++,单旋,平衡,节点
From： https://blog.csdn.net/aaa114514aaaa/article/details/142621919

目录