C++简单实现AVL树

目录

一、AVL树的概念

二、AVL树的性质

三、AVL树节点的定义

四、AVL树的插入

4.1 parent的平衡因子为0

4.2 parent的平衡因子为1或-1

4.3 parent的平衡因子为2或-2

4.3.1 左单旋

4.3.2 右单旋

4.3.3 先左单旋再右单旋

4.3.4 先右单旋再左单旋

4.4 插入节点完整代码：

五、AVL树判断是否平衡

六、AVL树的验证

---

一、AVL树的概念

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

二、AVL树的性质

1、空树也是一颗AVL树

2、它的左右子树都是AVL树

3、左右子树高度差（平衡因子）的绝对值不超过1

4、如果一颗二叉搜索树是高度平衡的，它就是AVL树。如果它由N个节点，其高度可保持在O(log2N)，搜索时间复杂度为O(log2N)。

三、AVL树节点的定义

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair& kv)
		:_kv(kv)
		,_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_bf(0)//平衡因子初始为0
	{}
 
	pair _kv;
	AVLTreeNode* _parent;
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	int _bf;//平衡因子 —— balance factor
};

四、AVL树的插入

AVL树的插入分为两大步：

1、新建节点，插入到正确的位置（使之符合二叉搜索树的性质）

如果插入到右边，则平衡因子加1，如果插入到左边，平衡因子减1；

2、判断平衡因子是否合法，不合法则调整节点（旋转）

插入完成后平衡因子有以下几种情况：

4.1 parent的平衡因子为0

如果此时parent的平衡因子为0，那么之前的平衡因子是1或-1，这棵树的高度不会变，不用向上更新，插入完成。

4.2 parent的平衡因子为1或-1

如果此时parent的平衡因子为1或-1，那么之前的平衡因子为0，高度改变了，需要向上更新。

4.3 parent的平衡因子为2或-2

如果此时parent的平衡因子为2或-2，那么需要通过旋转调平衡。

4.3.1 左单旋

    void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
 
		parent->_right = curleft;
		cur->_left = parent;
		if (curleft)
			curleft->_parent = parent;
 
		Node* ppnode = parent->_parent;
		parent->_parent = cur;
 
		if (parent == _root)
		{
			cur->_parent = nullptr;
			_root = cur;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}
		parent->_bf = cur->_bf = 0;//更新平衡因子
	}

4.3.2 右单旋

    void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
 
		parent->_left = curright;
		cur->_right = parent;
 
		if (curright)
			curright->_parent = parent;
 
		Node* ppnode = parent->_parent;
		parent->_parent = cur;
 
		if (parent == _root)
		{
			cur->_parent = nullptr;
			_root = cur;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}
		parent->_bf = cur->_bf = 0;
	}

4.3.3 先左单旋再右单旋

    void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		int bf = curright->_bf;
 
		RotateL(parent->_left);
		RotateR(parent);
 
		//更新平衡因子
		if (bf == 0)
		{
			parent->_bf = curright->_bf = cur->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			curright = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			curright = 0;
		}
		else
		{
			assert(false);
		}
	}

4.3.4 先右单旋再左单旋

    void RotateRL(Node* parent)
    {
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		int bf = curleft->_bf;
 
		RotateR(parent->_right);
		RotateL(parent);
 
		//更新平衡因子
		if (bf == 0)
		{
			parent->_bf = curleft->_bf = cur->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			cur->_bf = 0;
			curleft = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			cur->_bf = 1;
			curleft = 0;
		}
		else
		{
			assert(false);
		}
	}

4.4 插入节点完整代码：

    bool insert(const pair& kv)
	{
		//如果root为空
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//插入
		Node* cur = _root;
		Node* parent = cur;
		
		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;
		}
		cur->_parent = parent;//刚开始忘记写了
 
		//插入完成，开始判断是否平衡
		//最坏走到根就不再判断了，根的parent为空
		while (parent)
		{
			//更新平衡因子
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			//如果此时parent的平衡因子为0，那么之前的平衡因子是1或-1，这棵树的高度不会变，不用向上更新
			if (parent->_bf == 0)
			{
				break;
			}
			//如果此时parent的平衡因子为1或-1，那么之前的平衡因子为0，高度改变了，需要向上更新
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//向上更新
				cur = parent;
				parent = parent->_parent;
			}
			//如果此时parent的平衡因子为2或-2，那么需要通过旋转调平衡
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//左单旋
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				//右单旋
				if(parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				//先右单旋，再左单旋
				if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				//先左单旋，再右单旋
				if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
 
				break;//忘记写了
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

五、AVL树判断是否平衡

    bool isBalance()
	{
		return _isBalance(_root);
	}
 
    int Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int lh = Height(root->_left);
		int rh = Height(root->_right);
 
		return lh > rh ? lh + 1 : rh + 1;
	}
 
	bool _isBalance(Node* root)
	{
		if (root == nullptr)
			return true;
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		int diff = abs(rightHeight - leftHeight);
		return diff <= 1 && _isBalance(root->_left) && _isBalance(root->_right);
	}

六、AVL树的验证

int main()
{
	//常规场景
	AVLTree<int, int>* root1 = new AVLTree<int, int>();
	int a1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	for (auto e : a1)
	{
		root1->insert(make_pair(e, e));
	}
	root1->InOrder();
	cout << "isBalance: " << root1->isBalance() << endl;
 
	//特殊场景
	AVLTree<int, int>* root2 = new AVLTree<int, int>();
	int a2[] = { 4,2,6,1,3,5,15,7,16,14 };
	for (auto e : a2)
	{
		root2->insert(make_pair(e, e));
	}
	root2->InOrder();
	cout << "isBalance: " << root2->isBalance() << endl;
 
	//随机数
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (int i = 0; i < N; i++)
	{
		int n = rand();
		v.push_back(n);
	}
	AVLTree<int, int>* root3 = new AVLTree<int, int>();
	for (auto e : v)
	{
		root3->insert(make_pair(e, e));
	}
	//root->InOrder();
	cout << "isBalance: " << root3->isBalance() << endl;
	return 0;
}

运行结果：