AVL树插入操作与验证操作的简单实现

目录

AVL树的概念

AVL树的特征

 AVL树节点的定义

准备工作

AVL树的插入

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

调整节点的平衡因子(*****)

整体代码

---

AVL树的概念

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

就是说,这两个人在二叉树搜索树的基础上面做了一些优化,原来的二叉搜索树可能会退化为单只树,搜索时间复杂度为O(n),现在保证了这个树是基本平衡的,所以搜索的时间复杂度成为了O(logn)

AVL树的特征

一棵AVL树,要么是空树,要么具有这两个特征

它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

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

至于这个平衡因子是什么,简单,就是定义树节点的时候多加一个属于平衡因子的变量就行了

这里再贴一副图,大家感受一下

圆圈里面的数字表示节点的值,红色数字表示节点的平衡因子,平衡因子可以用右子树减去左子树,也可以用左子树减去右子树,这里采用的是右子树减去左子树,底下也是一样的

 AVL树节点的定义

template <class T>
class AVLTreeNode {
public:
	 AVLTreeNode<T>* _left;
	 AVLTreeNode<T>* _right;
	 AVLTreeNode<T>* _parent;
	 T _value;
	 int _bf;  //平衡因子,约定平衡因子为右边树的高度减去左边树的高度

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

这里的节点我们采用的是双亲表示发,因为后面要用到双亲,再求有点复杂

准备工作

template <class T>
class AVLTree {
	typedef AVLTreeNode<T> Node;
public:
	AVLTree() 
		:_root(nullptr)
	{}

	~AVLTree() {
		Distory(_root);
	}
private:
void Distory(Node*& root) {
		if (root) {
			Distory(root->_left);
			Distory(root->_right);
			delete root;
			root = nullptr;
		}
	}
	Node* _root;
};

注意Distory的参数是Node*的引用 

AVL树的插入

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

我们先按照二叉搜索树的插入方式给它插进去,不会二叉搜索树的插入也没关系,这里直接看就行

bool Insert(const T& value) {
		//判断要插入的位置
		//如果AVL树为空
		if (_root == nullptr) {
			_root = new Node(value);
			return true;
		}
		//如果AVL树不空
		//找节点,先插进去;
		Node* parent = _root;
		Node* child = parent;
		while (child) {
			parent = child;
			if (value > child->_value) {
				child = child->_right;
			}
			else if (value < child->_value) {
				child = child->_left;
			}
			else {
				return false;
			}
		}
        //节点找到了,插入,更新节点里面的指针
		child = new Node(value);
		child->_parent = parent;
		if (child->_value > parent->_value) {
			parent->_right = child;
		}
		else {
			parent->_left = child;
		}
		

注意,上面这个函数没完,只是因为太长了,所以放为两部分

调整节点的平衡因子(*****)

五星,重中之重

先来说一下调整平衡因子的四种方法,左单旋,右单旋,右左双旋,左右双旋

但其实我们只用看一种,其他的几种就很简单了

我们来看左单旋

看这幅图,现在是平衡的,但是如果我们再加一个70,它就不平衡了 

 这时,可以看到30这个节点的平衡因子是2,不符合AVL树的特性,所以我们应该对这一部分进行调整,对于这种场景(新节点加到较高右子树的右测节点),我们应该左单旋,所谓左单旋,我们给平衡因子不符合的节点命名为parent,给它的右孩子起名叫subR,然后把parent设置为subR的左孩子,subR原本的左孩子(如果有的话)设置成为parent新的右孩子,如果parent有双亲的话,让parent的双亲指向subR节点就好,调整以后的图片如图

平衡因字我们暂时没动,从图片可以看出,原本的parent节点和subR节点的平衡因子不对,应该改为0,所以后面再把这两个节点的平衡因子改为0即可

 右单旋(适用情况:在较高左子树的左侧插入节点)和左单旋差不对,就是把parent的左孩子节点上提而已,没什么好说的

接下来我们看第三种情况,右左双旋(适用情况:在较高右子树的左边插入节点)

听名字就知道怎么做了,先右单旋(右单旋parent的右孩子)再左单旋么,当然,你问我为什么我怎么就知道这么做?那是前人总结出来的,我试了一下发现是对的,仅此而已,你也可以试一下,要是错的你就赚大发了

两次旋转以后平衡因子可能会不对,那如何修改呢?也简单,你试一下,到最后就会发现,每次只有一个节点的平衡因子是不对的

这是人家发现的规律,当然可能不止这一个

        Node* subR = parent->_right;
		int bf = subR->_left->_bf;
		RotateRight(parent->_right);
		RotateLeft(parent);
		if (bf == 1) {
			parent->_bf = -1;
		}
		else if (bf == -1) {
			subR->_bf = 1;
		}

中间两个函数第一个是右单旋,第二个是左单旋,这个我觉得会画就行,或者记住也行,实在没有什么要着重说明的

然后是左右双旋(适用情况:在较高左子树的右侧插入节点)

就是先对parent的左孩子来一次左单旋,再对parent来一次右单旋就可以了

然后也是有一个节点的平衡因子不对,需要你取手动调整

        Node* subL = parent->_left;
		int bf = subL->_right->_bf;
		RotateLeft(parent->_left);
		RotateRight(parent);
		if (bf == 1) {
			subL->_bf = -1;
		}
		else if (bf == -1) {
			parent->_bf = 1;
		}

最后,看一下整体的代码,中间还有检测这棵树是否为AVL树以及前序遍历的代码

整体代码

template <class T>
class AVLTree {
	typedef AVLTreeNode<T> Node;
public:
	AVLTree() 
		:_root(nullptr)
	{}

	~AVLTree() {
		Distory(_root);
	}

	bool Insert(const T& value) {
		//判断要插入的位置
		//如果AVL树为空
		if (_root == nullptr) {
			_root = new Node(value);
			return true;
		}
		//如果AVL树不空
		//找节点,先插进去;
		Node* parent = _root;
		Node* child = parent;
		while (child) {
			parent = child;
			if (value > child->_value) {
				child = child->_right;
			}
			else if (value < child->_value) {
				child = child->_left;
			}
			else {
				return false;
			}
		}
		child = new Node(value);
		child->_parent = parent;
		if (child->_value > parent->_value) {
			parent->_right = child;
		}
		else {
			parent->_left = child;
		}
		
		//更新双亲的平衡因子
		while (parent) {
			//child插入会对平衡因子产生影响
			if (child == parent->_left) {
				parent->_bf--;
			}
			else {
				parent->_bf++;
			}

			//判断插入后是否满足AVL树的特性
			if (parent->_bf == 0) {
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1) {
				//parent变为1或者-1,肯定会对parent的双亲也产生影响
				child = parent;
				parent = parent->_parent;
			}
			else {
				//parent的_bf变为了2或者-2,这时候就需要调整了
				if (parent->_bf == 2) {
					if (child->_bf == 1) {
						RotateLeft(parent);
					}
					else {
						RotateRL(parent);
					}
				}
				else {
					if (child->_bf == -1) {
						RotateRight(parent);
					}
					else {
						RotateLR(parent);
					}
				}
				break;
			}
		}
		return true;
	}

	//中序遍历
	void InOrder() {
		_InOrder(_root);
	}

	//判断是否为AVL树
	bool IsAVLTree() {
		return _IsAVLTree(_root);
	}
private:
	//左单旋
	void RotateLeft(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		//处理subRL节点
		if (subRL) {
			subRL->_parent = parent;
		}
		//处理parent节点
		Node* pparent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		subR->_parent = pparent;
		//处理parent的双亲
		if (pparent) {
			if (parent == pparent->_left) {
				pparent->_left = subR;
			}
			else {
				pparent->_right = subR;
			}
		}
		else { //旋转之前,parent是根节点
			_root = subR;
		}
		//更新平衡因子
		parent->_bf = subR->_bf = 0;
	}

	//右单旋
	void RotateRight(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		//处理subLR
		if (subLR) {
			subLR->_parent = parent;			
		}

		//处理parent节点
		Node* pparent = parent->_parent;
		parent->_parent = subL;
		subL->_right = parent;
		subL->_parent = pparent;
		//处理pparent
		if (pparent) {
			if (parent == pparent->_left) {
				pparent->_left = subL;
			}
			else {
				pparent->_right = subL;
			}
		}
		else {
			//parent是root节点
			_root = subL;
		}
		//更新平衡因子
		parent->_bf = subL->_bf = 0;
	}

	//右左双旋
	void RotateRL(Node* parent) {
		Node* subR = parent->_right;
		int bf = subR->_left->_bf;
		RotateRight(parent->_right);
		RotateLeft(parent);
		if (bf == 1) {
			parent->_bf = -1;
		}
		else if (bf == -1) {
			subR->_bf = 1;
		}
	}

	//左右双旋
	void RotateLR(Node* parent) {
		Node* subL = parent->_left;
		int bf = subL->_right->_bf;
		RotateLeft(parent->_left);
		RotateRight(parent);
		if (bf == 1) {
			subL->_bf = -1;
		}
		else if (bf == -1) {
			parent->_bf = 1;
		}
	}

	//中序遍历
	void _InOrder(Node* root) {
		if (root == nullptr) {
			return;
		}
		_InOrder(root->_left);
		cout << root->_value << " ";
		_InOrder(root->_right);
	}

	//获取树的高度
	int GetHeight(Node* root) {
		if (root == nullptr) {
			return 0;
		}
		return GetHeight(root->_left) > GetHeight(root->_right) ? GetHeight(root->_left) + 1 : GetHeight(root->_right) + 1;
	}

	//判断是否为AVL树
	bool _IsAVLTree(Node* root) {
		if (root == nullptr) {
			return true;
		}
		int high = GetHeight(root->_right) - GetHeight(root->_left);
		if (high != root->_bf || abs(high) > 1) {
			return false;
		}
		return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
	}
	void Distory(Node*& root) {
		if (root) {
			Distory(root->_left);
			Distory(root->_right);
			delete root;
			root = nullptr;
		}
	}
	Node* _root;
};

要是有什么不懂的,欢迎在评论区留言,大家都是在路上的人,一起努力吧