模拟实现AVLTree超详解（C++）

 大家好，我是bug！今天来跟大伙谈谈AVLTree：
（代码可能会有一点问题，请各位老铁指正   ）

文章目录

• 一、AVLTree的概念
• 二、AVLTree的插入
• •   （1）“直线形状”
  • • 一、（右单旋）
    • 二、（左单旋）
  •  （2）”折线形状“
  • • 一、（右左双旋）
    •  二、（左右双旋）
• 三、AVLTree的迭代器
• 四、AVLTree的模拟实现

一、AVLTree的概念

 AVLTree：也叫做高度平衡二叉搜索树。通过对高度的控制来保证效率，而对于高度我们采用了旋转的方式来进行约束。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。相较于二叉搜索树，平衡二叉搜索树很好地避免了极端情况（插入的数据接近于有序），查找的时间复杂度为O（logN）。

K模型和KV模型 ：
K模型中只有key作为关键字，只存储key一个值。
而KV模型中存储了KV的键对值，即每个key值都有一个value与之对应。与K模型不一样的是多了个value与之绑定，其他部分没什么区别。

 同时相较于普通的二叉搜索树，我们在AVLTree中采用了三叉链和平衡因子，三叉链可以在某些方面带来便利，平衡因子用来控制树的平衡。 （当然，AVLTree的实现也可以不借助三叉链和平衡因子，有兴趣的小伙伴们可以去研究研究。）

 三叉链结构：每个结点有三个指针域，除了指向左孩子和右孩子还会指向父亲，如果是根结点，则父亲结点为nullptr。

平衡因子：即右子树的高度减去左子树的高度所得结果。(abs(平衡因子) <= 1)

二、AVLTree的插入

☀️ ☀️在开始插入操作前，我们先讲讲AVLTree的旋转操作。
AVLTree中的旋转操作包括左单旋，右单旋，左右双旋和右左双旋，共四种。 （下面我们直接在分类中按图说话，嘿嘿）

AVL树的插入过程比较复杂，一共有四种情况，要严格遵守其规则（下面例子为最简单的具象图）：

  （1）“直线形状” 一、（右单旋）

  当我们插入结点后出现下图情况时 :

（插入前p的平衡因子为0，g的平衡因子为-1；插入后p的平衡因子为-1，g的平衡因子为-2）   ：

 此时，g的平衡因子变成了-2，违反了规则，所以我们要进行旋转操作。以g为旋转点，进行右单旋。

 此时cur，p和g的平衡因子都变成了0，调整完成。

---

二、（左单旋）

  和上面的情况刚好相反。当我们插入结点后出现下图情况时:

（插入前p的平衡因子为0，g的平衡因子为1；插入后p的平衡因子为1，g的平衡因子为2 ）   ：

 这时，我们要以g为旋转点进行左单旋，同时更新平衡因子。

 三个结点的平衡因子都变成了0，调整完毕。

---

下面我们从中抽出AVLTree的抽象图模型：
  1、右单旋：

 此时以80为旋转点，进行右单旋，同时把80的右子树与_root进行链接。

---

  2、左单旋

 和右单旋情况类似，此时以80作为旋转点进行左单旋，同时把80的左子树和_root进行链接。

---

 （2）”折线形状“ 一、（右左双旋）

  当我们插入结点后变成下面这种情况   ：

 我们就要进行右左双旋了，要先以p为旋转点进行右单旋。（变成左单旋的情况）

 再以cur为旋转点进行左单旋。

---

 二、（左右双旋）

  和上面的情况相反   ：

 先以p为旋转点，进行左单旋。（旋转后和右单旋的情况一致）

 再以cur为旋转点，进行右单旋 。

---

下面我们来抽出它的抽象图：
  1、右左双旋

 先以80为旋转点，进行右单旋，同时更新80和70的平衡因子。

 再以50为旋转点，进行左单旋，同时更新50和70的平衡因子。

---

  2、左右双旋

 先以80为旋转点，进行左单旋，同时更新80和90的平衡因子。

 再以90为旋转点，进行右单旋，同时更新100和90的平衡因子。

---

插入部分的内容比较复杂，希望大家能够多看看。  

---

三、AVLTree的迭代器

  简介：对于AVLTree（包括红黑树），我们引入了三叉链进行实现，这样有助于我们实现迭代器。
AVLTree的迭代器与list的迭代器类似，其都不是原生指针，而是进行封装之后的复杂结构。
这里我们会实现AVLTree的正向迭代器和反向迭代器。其中反向迭代器的内部封装了正向迭代器。

  那我们是怎么实现AVLTree的正向迭代器呢？
（难点：自增自减的重载）

对于自增自减，我们按照中序完成。（以自增为例，自减和自增类似）
 与_pnode中的数据最接近的一定是右子树的最左结点（按照中序）。

 当_pnode的右子树存在，那么我们去找它右子树的最左结点。

  当_pnode的右子树不存在，那我们只能向上去找，找到当前结点是父亲的左孩子的结点，这个时候的父亲结点就是我们的下个结点。（按照中序）

  对于反向迭代器，其内部封装了正向迭代器，正向迭代器内要实现自减的重载，自减重载是反向迭代器的关键。

---

四、AVLTree的模拟实现

 这里模拟实现AVLTree树⬇️ ⬇️：

#pragma once

#include
#include
#include

using std::cin;
using std::cout;
using std::endl;
using std::pair;

namespace lz
{
	template
	struct PairKeyOfValue
	{
		const K& operator()(const pair& kv){ return kv.first; }
	};

	template
	struct KKeyOfValue
	{
		const K& operator()(const K& key)const { return key; }
	};

	template
	struct AVLTreeNode
	{
	public:
		AVLTreeNode* _left;
		AVLTreeNode* _right;
		AVLTreeNode* _parent;

		//平衡因子
		//平衡因子等于右子树的高度减去左子树的高度
		int _bf;

		T _data;

		//构造函数
		AVLTreeNode(const T& data = T())
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _bf(0)
			, _data(data)
		{}
	};

	template
	struct iterator
	{
		typedef AVLTreeNode* pNode;
		typedef Ref reference;
		typedef Ptr pointer;
		typedef const Ref const_reference;
		typedef const Ptr const_pointer;
		typedef iterator self;

	public:
		iterator(pNode pnode = nullptr)
			:_pnode(pnode)
		{}

		reference operator*() { return _pnode->_data; }
		const_reference operator*()const { return _pnode->_data; }
		pointer operator->() { return &operator*(); }
		const_pointer operator->()const { return &operator*(); }

		void increasement()
		{
			if (_pnode == nullptr)
				return ;

			//去找右子树的最左结点
			if (_pnode->_right != nullptr)
			{
				pNode left = _pnode->_right;
				while (left->_left)
					left = left->_left;

				_pnode = left;
				return ;
			}

			//右子树为空，我们向上找
			pNode parent = _pnode->_parent;
			pNode cur = _pnode;
			while (parent)
			{
				if (parent->_right == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				else
					break;
			}

			_pnode = parent;
		}
		self& operator++() { increasement(); return *this; }
		self operator++(int) { pNode tmp = _pnode; increasement(); return self(tmp); }

		void decreasement()
		{
			if (_pnode == nullptr)
				return ;

			//左子树不为空时
			if (_pnode->_left != nullptr)
			{
				pNode right = _pnode->_left;
				while (right->_right)
					right = right->_right;

				_pnode = right;
				return;
			}

			//左子树为空
			pNode parent = _pnode->_parent;
			pNode cur = _pnode;
			while (parent)
			{
				if (parent->_left == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				else
					break;
			}

			_pnode = parent;
		}

		self& operator--(){decreasement();return *this;}
		self operator--(int) { pNode tmp = _pnode; decreasement(); return self(tmp); }
		bool operator==(const self& it)const { return _pnode == it._pnode; }
		bool operator!=(const self& it)const { return _pnode != it._pnode; }
	public:
		pNode _pnode;
	};

	template
	struct reverse_iterator
	{
		typedef reverse_iterator self;
		typedef typename iterator::reference reference;
		typedef const reference const_reference;
		typedef typename iterator::pointer pointer;
		typedef const pointer const_pointer;
	public:
		reverse_iterator(iterator it)
			:_it(it)
		{}

		reference operator*() { return *_it; }
		const_reference operator*()const { return *_it; }
		pointer operator->() { return &operator*(); }
		const_pointer operator->()const { return &operator*(); }

		self& operator++() { --_it; return *this; }
		self operator++(int) { iterator tmp = _it; --_it; return self(tmp); }
		self& operator--() { ++_it; return *this; }
		self operator--(int) { iterator tmp = _it; return self(tmp); }

		bool operator!=(const self& it) const{ return _it != it._it; }
		bool operator==(const self& it) const{ return _it == it._it; }
	private:
		iterator _it;
	};

	template
	struct AVLTree
	{
		typedef AVLTreeNode* pNode;
		typedef iterator tree_iterator;
		typedef iterator tree_const_iterator;
		typedef reverse_iterator tree_reverse_iterator;
		typedef reverse_iterator tree_const_reverse_iterator;
		typedef AVLTree self;

	private:
		//根节点
		pNode _root;

	public:
		//构造函数
		AVLTree()
			:_root(nullptr)
		{}

		~AVLTree()
		{
			clear(_root);
			_root = nullptr;
		}

		void clear(pNode root)
		{
			if (root == nullptr)
				return;

			clear(root->_left);
			clear(root->_right);
			delete root;
		}

		void _CopyTree(const pNode& root)
		{
			if (root == nullptr)
				return;

			_CopyTree(root->_left);
			_CopyTree(root->_right);
			insert(root->_data);
		}

		AVLTree(const self& t)
		{
			_root = nullptr;
			_CopyTree(t._root);
		}

		//非const
		tree_iterator begin()
		{
			pNode left = _root;
			//判断根结点是否是nullptr
			if (_root != nullptr)
			{
				if (_root->_left != nullptr)
					while (left->_left)
					{
						left = left->_left;
					}
			}
			return tree_iterator(left);
		}
		tree_iterator end() { return tree_iterator(nullptr); }

		//const
		tree_const_iterator cbegin()const
		{
			pNode left = _root;
			//判断根结点是否是nullptr
			if (_root != nullptr)
			{
				if (_root->_left != nullptr)
					while (left->_left)
					{
						left = left->_left;
					}
			}
			return tree_const_iterator(left);
		}
		tree_const_iterator cend()const { return tree_const_iterator(nullptr); }

		tree_reverse_iterator rbegin()
		{
			pNode right = _root;
			if (right != nullptr)
			{
				while (right->_right)
				{
					right = right->_right;
				}
			}
			return tree_reverse_iterator(tree_iterator(right));
		}
		tree_reverse_iterator rend() { return tree_reverse_iterator(tree_iterator(nullptr)); }

		tree_const_reverse_iterator crbegin()
		{
			pNode right = _root;
			if (right != nullptr)
			{
				while (right->_right)
				{
					right = right->_right;
				}
			}
			return tree_const_reverse_iterator(tree_const_iterator(right));
		}
		tree_const_reverse_iterator crend() 
		{ return tree_const_reverse_iterator(tree_const_iterator(nullptr)); }

		self& operator=(const self& t)
		{
			self tmp(t);
			std::swap(tmp._root, this->_root);
			return *this;
		}

		V& operator[](const K& key)
		{
			
			return insert(make_pair(key, V())).first._pnode->_data.second;
		}

		//插入
		pair insert(const T& data)
		{
			KeyOfValue kov;

			if (_root == nullptr)
			{
				_root = new AVLTreeNode(data);
				//_root->_data = data;
				return std::make_pair(tree_iterator(_root), true);
			}

			//找到插入结点的位置
			pNode parent = _root;
			pNode cur = _root;
			while (cur)
			{
				if (kov(cur->_data) > kov(data))
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (kov(cur->_data) < kov(data))
				{
					parent = cur;
					cur = parent->_right;
				}
				else
					return pair(tree_iterator(cur), false);
			}

			cur = new AVLTreeNode(data);
			//保存cur的指针，作为返回值
			pNode ret = cur;
			//判断cur是在parent左边还是右边，再创建结点，进行插入
			if (kov(parent->_data) > kov(data))
			{
				cur->_parent = parent;
				parent->_left = cur;
			}
			else//kov(parent->_data) < kov(data)
			{
				cur->_parent = parent;
				parent->_right = cur;
			}

			//调节平衡因子
			while (parent)
			{
				//如果在parent的右边插入，则平衡因子++
				if (parent->_right == cur)
					parent->_bf++;
				//如果在parent的左边插入，平衡因子--
				else if (parent->_left == cur)
					parent->_bf--;

				//通过平衡因子进行调整
				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)
				{
					if (parent->_bf == -2)
					{
						//左左--》右单旋
						if (cur->_bf == -1)
						{
							RotateR(parent);
							break;
						}
						//左右--》左右双旋
						else if (cur->_bf == 1)
						{
							RotateLR(parent);
							break;
						}
					}
					else//parent->_bf == 2
					{
						//右右--》左单旋
						if (cur->_bf == 1)
						{
							RotateL(parent);
							break;
						}
						//右左--》右左双旋
						else if (cur->_bf == -1)
						{
							RotateRL(parent);
							break;
						}
					}
				}
				else
					assert(false);
			}
			return std::make_pair(tree_iterator(ret), true);
		}

		//重点：平衡因子的更新
		//左右双旋
		void RotateLR(pNode& parent)
		{
			//平衡因子的更新
			pNode subL = parent->_left;
			pNode subLR = subL->_right;
			//保存subRL的平衡因子
			int bf = subLR->_bf;

			RotateL(parent->_left);
			RotateR(parent);

			if (bf == 1)
			{
				subLR->_bf = 0;
				parent->_bf = -1;
				subL->_bf = 0;
			}
			else if (bf == -1)
			{
				subLR->_bf = 0;
				parent->_bf = 0;
				subL->_bf = 1;
			}
			else if (bf == 0)
			{
				subLR->_bf = 0;
				parent->_bf = 0;
				subL->_bf = 0;
			}
			else
				assert(false);
		}
		//右左双旋
		void RotateRL(pNode& parent)
		{
			//平衡因子的更新
			pNode subR = parent->_right;
			pNode subRL = subR->_left;
			//保存subRL的平衡因子
			int bf = subRL->_bf;

			RotateR(parent->_right);
			RotateL(parent);

			//平衡因子的更新
			if (bf == 1)
			{
				subRL->_bf = 0;
				parent->_bf = -1;
				subR->_bf = 0;
			}
			else if (bf == -1)
			{
				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);
		}

		//重点：旋转的实现
		void RotateR(pNode& parent)
		{
			pNode grandFather = parent->_parent;
			pNode subL = parent->_left;
			pNode subLR = subL->_right;

			//判断subLR结点是否为空
			if (subLR)
				subLR->_parent = parent;

			parent->_left = subLR;
			subL->_right = parent;
			subL->_parent = grandFather;
			parent->_parent = subL;


			//右单旋操作
			//如果parent是根节点
			if (parent == _root)
				_root = subL;
			else//parent不是根节点
			{
				//判断parent是grandparent的左孩子还是右孩子
				//再将subL连接上去
				if (grandFather->_left == parent)
					grandFather->_left = subL;
				else//grandFather->_right = parent
					grandFather->_right = subL;
			}
			//平衡因子的调节操作
			parent->_bf = subL->_bf = 0;
		}

		void RotateL(pNode& parent)
		{
			pNode grandFather = parent->_parent;
			pNode subR = parent->_right;
			pNode subRL = subR->_left;

			//判断subRL是否为空
			if (subRL)
				subRL->_parent = parent;

			parent->_right = subRL;
			subR->_left = parent;
			parent->_parent = subR;

			//左单旋操作
			//判断parent是不是根节点
			if (parent == _root)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				//判断parent是grandFather的左孩子还是右孩子
				if (grandFather->_left == parent)
					grandFather->_left = subR;
				else//grandFather->_right == parent
					grandFather->_right = subR;
				//不是根节点时，进行连接
				subR->_parent = grandFather;
			}
			//平衡因子的调节
			parent->_bf = subR->_bf = 0;
		}

		void KV_inOrder()
		{
			_KV_inOrder(_root);
		}

		void K_inOrder()
		{
			_K_inOrder(_root);
		}

		tree_iterator find(const T& data)
		{
			KeyOfValue kov;
			pNode cur = _root;
			while (cur)
			{
				if (kov(cur->_data) > kov(data))
					cur = cur->_left;
				else if (kov(cur->_data) < kov(data))
					cur = cur->_right;
				else
					return tree_iterator(cur);
			}

			return tree_iterator(nullptr);
		}

		size_t Height()
		{
			return _Height(_root);
		}

		bool IsAVLTree()
		{
			return _IsBalance(_root);
		}

		private:
			bool _IsBalance(const pNode& root)
			{
				//空树也是AVLTree树
				if (root == nullptr)
					return true;

				int leftHeight = _Height(root->_left);
				int rightHeight = _Height(root->_right);
				int diff = rightHeight - leftHeight;

				return abs(diff) < 2
					&& _IsBalance(root->_left)
					&& _IsBalance(root->_right);
			}

			//树的高度
			int _Height(const pNode& root)
			{
				if (root == nullptr)
					return 0;

				int ret1 = _Height(root->_left);
				int ret2 = _Height(root->_right);

				return ret2 > ret1 ? ret2 + 1 : ret1 + 1;
			}

			//用于K模型
			void _K_inOrder(const pNode& cur)
			{
				KeyOfValue kov;
				if (cur == nullptr)
					return;

				_K_inOrder(cur->_left);
				cout << cur->_data << "  ";
				_K_inOrder(cur->_right);
			}

			//用于KV模型
			void _KV_inOrder(const pNode& cur)
			{
				KeyOfValue kov;
				if (cur == nullptr)
					return;

				_KV_inOrder(cur->_left);
				cout << cur->_data.first << " : " << cur->_data.second << endl;
				_KV_inOrder(cur->_right);
			}
	};
}



void Test1()//测试左右旋
{
	lz::AVLTree, lz::PairKeyOfValue> t;
	

	//测试左右双旋
	

	//测试右左双旋
	//t.insert(pair(5, 6));
	//t.insert(pair(6, 6));
	//t.insert(pair(4, 6));
	//t.insert(pair(8, 6));
	//t.insert(pair(7, 6));
	//t.insert(pair(1, 1));
	//t.insert(pair(2, 1));
	//t.insert(pair(3, 1));
	cout << t.IsAVLTree() << "  " << endl;
}

void Test2()//测试正向迭代器
{
	lz::AVLTree, lz::PairKeyOfValue> t1;
	t1.insert(pair(1, 2));
	t1.insert(pair(2, 2));
	t1.insert(pair(3, 2));
	t1.insert(pair(4, 2));

	//const类型正向迭代器，key和value都不能修改
	lz::AVLTree,lz::PairKeyOfValue>
		::tree_const_iterator cit = t1.cbegin();
	while (cit != t1.cend())
	{
		//cit->first = 1;
		//cit->second = 1;
		cout << cit->first << ":" << cit->second << endl;
		++cit;
	}
	cout << endl;

	//非const类型正向迭代器，key不能修改，value可修改
	lz::AVLTree, lz::PairKeyOfValue>
		::tree_iterator it = t1.begin();
	while (it != t1.end())
	{
		//it->first = 1;
		it->second = 1;
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
}

void Test3()//测试反向迭代器
{
	lz::AVLTree, lz::PairKeyOfValue> t1;
	t1.insert(pair(1, 2));
	t1.insert(pair(2, 2));
	t1.insert(pair(3, 2));
	t1.insert(pair(4, 2));

	//const类型反向迭代器，key和value都不能修改
	lz::AVLTree, lz::PairKeyOfValue>
		::tree_const_reverse_iterator crit = t1.crbegin();
	while (crit != t1.crend())
	{
		//crit->first = 1;
		//crit->second = 1;
		cout << crit->first << ":" << crit->second << endl;
		crit++;
	}
	cout << endl;

	//非const类型反向迭代器，key不能修改，value可以修改
	lz::AVLTree, lz::PairKeyOfValue>
		::tree_reverse_iterator rit = t1.rbegin();
	while (rit != t1.rend())
	{
		//rit->first = 1;
		rit->second = 1;
		cout << rit->first << ":" << rit->second << endl;
		rit++;
	}
	cout << endl;
}

void Test4()//测试KV功能(字典)
{
	lz::AVLTree, lz::PairKeyOfValue> dict;
	//插入
	dict.insert(std::make_pair("apple", "苹果"));
	dict["left"] = "左边";
	dict["right"] = "右边";
	dict["up"] = "向上";
	dict["down"] = "向下";
	dict["down"] = "下滑";

	lz::AVLTree, lz::PairKeyOfValue>::tree_iterator it = dict.begin();

	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;

}

void Test5()//测试K功能
{
	lz::AVLTree> t1;
	t1.insert(1);
	t1.insert(2);
	t1.insert(3);
	t1.insert(4);
	t1.K_inOrder();
	cout << endl << endl;

	//非const正向迭代器
	lz::AVLTree>::tree_iterator it = t1.begin();
	while (it != t1.end())
	{
		//可修改
		//*it = 2;
		cout << *it << endl;
		++it;
	}
	cout << endl;

	//const正向迭代器
	lz::AVLTree>::tree_const_iterator cit = t1.cbegin();
	while (cit != t1.cend())
	{
		//不可修改
		//*cit = 1;
		cout << *cit << endl;
		++cit;
	}
	cout << endl;
	
	//非const反向迭代器
	lz::AVLTree>::tree_reverse_iterator rit = t1.rbegin();
	while (rit != t1.rend())
	{
		//可修改
		//*rit = 5;
		cout << *rit << endl;
		++rit;
	}
	cout << endl;

	//const反向迭代器
	lz::AVLTree>::
		tree_const_reverse_iterator crit = t1.crbegin();
	while (crit != t1.crend())
	{
		//不可修改
		//*crit = 5;
		cout << *crit << endl;
		++crit;
	}
	cout << endl;
}

void Test6()//测试插入功能+等号重载
{
	lz::AVLTree> t1;
	t1.insert(1);
	t1.insert(2);
	t1.insert(3);
	t1.insert(4);
	t1.insert(5);
	lz::AVLTree> t2(t1);
	lz::AVLTree> t3;
	t3 = t2;
	t3.K_inOrder();

}

int main()
{
	Test6();

 	return 0;
}

  今天的内容到这里就结束了，希望小伙伴们能够有所收获，我们下期再见！