AVL树的模拟实现(c++)

目录

        搜索二叉树对于搜索查询来说是非常快的，但是它有着致命的缺陷，如果插入的数据是有序的，那么它的结构就会退化成单链表，这对于搜索查询来说是非常不利的，因此为了解决搜索树的缺陷，弥补它的不足，后来就有人引入了AVL树，它是由两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明的一种解决上述问题的方法 ，即：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树的高度差的绝对值不超过1（需要对树中的节点进行调整），即可降低树的高度，从而减少平均搜索长度。

目录

1.AVL树的性质

2.AVL树节点的定义

        2.1AVL节点的定义 

       2.2 AVL树的定义

3.AVL树的插入

4.AVL树的旋转

5.AVL树的删除

6.AVL树的性能

7.其它代码

---

1.AVL树的性质

        1.它的左右子树都是AVL树

        2.左右子树的高度之差（简称平衡因子）的绝对值不超过1

        如何实现AVL树呐，首先我们需要定义一个变量来记录每个节点的平衡因子，新插入的节点的平衡因子永远是 0，平衡因子等于当前节点右子树的高度减去左子树的高度。每次插入平衡因子后都需要对有关这个节点祖先的平衡因子进行更新，那么，什么时候更新结束呐，等节点的祖先的平衡因子等于零的时候更新结束，平衡因子等于0说明之前这颗子树的平衡因子是1或者-1，插入新的节点后树的高度没有变大（之前这颗树有一边高一边矮现在它们变的一样高了），而是变得平衡了，此时就不需要更新平衡因子了，那么更新平衡因子的意义在哪里呢，如果更新，新插入节点的平衡因子时，它的平衡因子变成-2或者2说明这棵子树不平衡了，需要调整了，此时不必再继续更新平衡因子了，需要及时对这颗子树进行旋转。如图：

2.AVL树节点的定义

        2.1AVL节点的定义 

         需要注意的是这里使用了三叉链，目的是方便平衡因子的更新。

    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(const pair<K,V> & kv)
			:_left(nullptr)
			,_right(nullptr)
			,_bf(0)
			,_parent(nullptr)
			,_kv(kv)
		{ }
	};

       2.2 AVL树的定义

	template<class K,class V>
	class AVLTree
	{
	public:
		typedef AVLTreeNode<K, V> Node;
		
	private:
		Node* _root;
	};

3.AVL树的插入

        AVL树的插入与二叉搜索树的插入一样，因此AVL树的插入分为两步：

        1.按照二叉搜索树的方式插入新节点

        2.调整节点的平衡因子 

      bool insert(const pair<K,V> &kv)
		{
			if (_root == nullptr)//第一次插入，没有节点首先给_root申请新的节点
			{
				_root = new Node(kv);
				return true;
			}
			
			Node* cur = _root;
			Node* parent = nullptr;
			//查找插入的位置
			while (cur)//从根节点开始
			{
				if (cur->_kv < kv)
				{
					parent = cur;//保存父节点
					cur = cur->_right;//走左边
				}
				else if(cur -> _kv > kv)
				{
					parent = cur;
					cur = cur->_left;//走右边
				}
				else
				{
					return false;//已经存在key值无法插入
				}
			}
			cur = new Node(kv);
			if (parent->_kv > kv)//对插入的位置进行判断
			{
				//插入到左边
				parent->_left = cur;
				cur->_parent = parent;
			}
			else
			{
				//插入到右边
				parent->_right = cur;
				cur->_parent = parent;
			}
			//更新平衡因子
			while (parent)
			{
				if (cur->_kv > parent->_kv)
				{
					//在右边平衡因子++
					parent->_bf++;
				}
				else if (cur->_kv < parent->_kv)
				{
					//在左边平衡因子--
					parent->_bf--;
				}
 
				if (parent->_bf == 0)
				{
					break;//平衡因子更新结束，无需调整
				}
 
				if (parent->_bf == -1 || parent->_bf == 1)
				{
					//继续更新平衡因子
					cur = parent;
					parent = parent->_parent;
				}
				else if (parent->_bf == -2 || parent->_bf == 2)
				{
					//此时parent所在子树已经不平衡了
					// 需要进行旋转处理
					//旋转parent所在的子树
					if (parent->_bf == 2)
					{
						if (cur->_bf == 1)
						{
							//左单旋
							rotateL(parent);
						}
						else if(cur->_bf == -1)
						{
							//右左双旋
							rotateRL(parent);
						}
					}
					else if(parent->_bf == -2)
					{
						if (cur->_bf == -1)
						{
							//右单旋
							rotateR(parent);
						}
						else if (cur->_bf == 1)
						{
							//左右双旋
							rotateLR(parent);
						}
					}
					
					
				}
				//旋转结束之后这棵树肯定是平衡的
				//直接结束就行
				break;
			}
 
		}

4.AVL树的旋转

        对于AVLtree的旋转首先要分成几种情况分开讨论，它的旋转还是有些复杂的。

       

        第一种：新节点插入较高左子树的左侧：右单旋 

        如图：

        图中这两种都是属于右旋的情况，这样的右旋情况的子树还有很多种，但是他们都有想同的特点此时parent的平衡因子是等于-2的。parent所在左子树的高度永远比右子树高2，所以我们可以对这种情况进行抽象，如下图： 

进行右单旋需要：将30的右子树b连接到60（parent） 的左孩子，将30的左子树连接到60（parent）处。需要注意的是这里使用的是三叉链，所以对于节点的parent指针也要进行更新。

        void rotateR(Node* parent)//右单旋
		{
			//保存需要改变的节点的关系
			Node* subL = parent->_left;
			Node*pParent = parent->_parent;
			Node* subLR = subL->_right;
			//更新节点的关系
			parent->_left = subLR;
			subL->_right = parent;
			//确保subLR存在
			if (subLR)
			{
				subLR->_parent = parent;
			}
			
			parent->_parent = subL;
			//判断parent的父节点是否是root节点，如果是root节点就要对_root节点进行更新
			if ( pParent == nullptr)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else//对subL的父节点进行更新，更新之前需要确定parent与pParent的链接关系
			{
				if (pParent->_left == parent)
				{
					pParent->_left = subL;
				}
				else
				{
					pParent->_right = subL;
				}
				subL->_parent = pParent;
 
			}
			//旋转之后parent所在子树的高度会变低，所以subL和parent的平衡因子都会变为0
 
			subL->_bf = parent->_bf = 0;
		}

        第二种：新节点插入较高右子树的右侧：左单旋 

        如图： 

        具体情况和第一种类似，可以参考第一种。

	    void rotateL(Node* parent)//左单旋
		{
			//保存需要改变的节点的关系
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			Node* pParent = parent->_parent;
			parent->_right = subRL;
			subR->_left = parent;
			//确保subRL不为空
			if (subRL)
			{
				subRL->_parent = parent;
			}
			parent->_parent = subR;
			//判断parent的父节点是否为空，如果parent的父节点为空说明parent是_root节点，此时需要更新root节点
			if (pParent == nullptr)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			//对subR的父节点进行更新，更新之前需要确定parent与pParent的链接关系
			else
			{
				if (pParent->_left == parent)
				{
					pParent->_left = subR;
				}
				else
				{
					pParent->_right = subR;
				}
			}
			//旋转之后parent所在子树的高度会变低，所以subR和parent的平衡因子都会变为0
 
			subR->_bf = parent->_bf = 0;
		}

         第三种：新节点插入较高左子树的右侧：先左单旋再右单旋

        如图： 

        需要注意的是涉及平衡因子的更新较为麻烦，需要根据具体情况进行更新。 

	    //左右双旋
		void rotateLR(Node* parent)
		{
			//记录需要进行左单旋和右单旋的子树节点
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			//对subLR的平衡因子进行记录，用来判断更新后的平衡因子
			int bf = subLR->_bf;
			rotateL(subL);//左单旋
			rotateR(parent);//右单旋
			//根据subLR的平衡因子对其他的平衡因子进行调节
			if (bf == -1)
			{
				subL->_bf = 0;
				subLR->_bf = 0;
				parent->_bf = -1;
			}
			else if (bf == 1)
			{
				subL->_bf = -1;
				parent->_bf = 0;
				subLR->_bf = 0;
			}
			else if (bf == 0)
			{
				subL->_bf = 0;
				subLR->_bf = 0;
				parent->_bf = 0;
			}
		} 

        第四种：新节点插入较高右子树的左侧：先右单旋再左单旋

        如图： 

	    //右左双旋
		void rotateRL(Node* parent)
		{
			//记录需要进行左单旋和右单旋的子树节点
 
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			//对subRL的平衡因子进行记录，用来判断更新后的平衡因子
			int bf = subRL->_bf;
			rotateR(subR);
			rotateL(parent);
			//根据subRL的平衡因子对其他的平衡因子进行调节
			if (bf == -1)
			{
				parent->_bf = 0;
				subR->_bf = 1;
				subRL->_bf = 0;
			}
			else if (bf == 1)
			{
				parent->_bf = -1;
				subR->_bf = 0;
				subRL->_bf = 0;
			}
			else if (bf == 0)
			{
				parent->_bf = 0;
				subR->_bf = 0;
				subRL->_bf = 0;
			}
		}

        这里不再进行细节的讲解因为和第三种类似，具体参考第三种。 

5.AVL树的删除

         因为AVL也是二叉搜索树，可以按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与插入不同的是删除节点后的平衡因子更新，最差的情况一直要调整到根节点。

        怎么进行对AVL树节点的删除，这里分为两步：

        1.按照平衡树的方式进行删除

        2.更新平衡因子 

        其实删除就分为三种情况：删除的这个节点左子树为空，删除的这个节点右子树为空和删除的这个节点左，右子树都不为空。 具体可以参考： 搜索树的删除

        更新平衡因子这里和插入刚好是相反的，插入如果平衡因子变为零说明之前平衡因子是1或者-1，高度是，没有变化的此时就不需要更新了。而删除恰恰相反，如果平衡因子变为0说明之前是1或者-1，现在变为0了，这个子树的高度变低了要继续进行更新平衡因子。

        插入后 平衡因子变为0就可以结束平衡因子的更新，而删除后平衡因子等于1或者-1就可结束平衡因子的更新。

        相同的是如果平衡因子等于-2或者2的时候不管是删除还是插入都说明这棵子树不平衡了，需要进行旋转处理。

       

6.AVL树的性能

        AVL树是一颗绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差都不大于1，这样可以保证查询时效率很高，时间复杂度很低（$log_2 (N)$）,但是如果对AVL树坐做一些结构修改的操作，性能就会非常低下，比如：插入时要维护绝对的平衡，旋转次数就会比较多，更差的是在删除时，有可能一直让旋转持续根的位置。到因此如果需要一种查询高效的且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树，但是一个结构经常修改，就不太适合。

7.其它代码

         

        typedef AVLTreeNode<K, V> Node;
		AVLTree(const K& key = K(), const V& val = V())
		{
			//构造函数初始化根节点为空
			_root = nullptr;
		}
		~AVLTree()
		{
			//调用Destory()对节点进行释放
			Destory();
			_root = nullptr;
		}
		void _Destory(Node* root)
		{
			//对树进行后续遍历，并释放节点
			if (root == nullptr)
			{
				return;
			}
			_Destory(root->_left);
			_Destory(root->_right);
			delete root;
		}
		void Destory()
		{
			if (_root)
			{
				_Destory(_root);
			}
		}
        //查找key是否存在
		Node* Find(const K& key)
		{
			//根节点为空不需要查找
			if (_root == nullptr)
			{
				return nullptr;
			}
			else
			{
				//按照搜索树的方式进行查找
				Node* cur = _root;
				while (cur)
				{
					if (cur->_key == key)
					{
						//找到了返回节点的指针
						return cur;
					}
					else if (key > cur->_key)
					{
						cur = cur->_right;
					}
					else
					{
						cur = cur->_left;
					}
				}
				//走到这里说明cur为空，key不存在
				return cur;
			}
		}
        void _Inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Inorder(root->_left);
			cout << root->_key << ":" << root->_val << endl;
			_Inorder(root->_right);
		}
		//对树按照递归的方式进行中序遍历
		void Inorder()
		{
			_Inorder(_root);
		}
		int _Hight(Node* root)
		{
			if (root == nullptr)
			{
				return 0;
			}
			int leftHight = _Hight(root->_left);
			int rightHight = _Hight(root->_right);
 
			return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
		}
		//求树的高度
		int Hight()
		{
			return _Hight(_root);
		}
		bool _Balance(Node* root)
		{
			if (root == nullptr)
			{
				return true;
			}
			
			int leftHight = _Hight(root->_left);
			int rightHight = _Hight(root->_right);
 
			if (abs(leftHight - rightHight) > 1)
				return false;
			return (abs(leftHight - rightHight) > 1)
				&& _Balance(root->_left)
				&&_Balance(root->_right);
		}
		//判断树是否平衡
		bool Balance()
		{
			return _Balance(_root);
		}
		//判断是否是AVL树
		bool isAVLTree()
		{
			return _Balance(_root);
		}

        为什么这里对树进行中序遍历和其他操作的时候要写一个子函数呢，是因为_root是私有的成员，如果不使用子函数，在类的外面就不能调用了。 

        好咯，今天的烧脑就到这里啦，明天依旧光芒万丈呢！写的不好的地方还请指正批评，在下洗耳恭听。