AVL 树

• • AVL树的概念
  • AVL树节点的定义
  • AVL树的插入(难点)

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

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

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在

O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)。

template
struct AVLTreeNode
{
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	pair _kv;
	
	//平衡因子
	int _bf;


	AVLTreeNode(const pair& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_bf(0)
	{}
};

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

1. 按照二叉搜索树的方式插入新节点
   搜索二叉树
2. 调整节点的平衡因子

情况1：新节点插入较高左子树的左侧-进行右单旋

void RotateR(Node* cur)
	{
		Node* SubL = cur->_left;
		Node* SubLR = SubL->_right;
		//     60
		//  30
		//10
		Node* parent = cur->_parent;

		cur->_left = SubLR;
		if(SubLR)
			SubLR->_parent = cur;


		SubL->_right = cur;
		cur->_parent = SubL;


		if (parent == nullptr)
		{
			_root = SubL;
			SubL->_parent = parent;
		}
		else
		{
			if (parent->_left == cur)
			{
				parent->_left = SubL;
				SubL->_parent = parent;
			}
			else if (parent->_right == cur)
			{
				parent->_right = SubL;
				SubL->_parent = parent;
			}
			else
			{
				assert(false);
			}
		}

	}

情况2：新节点插入较高右子树的右侧-进行左单旋

void RotateL(Node* cur)
	{
		Node* SubR = cur->_right;
		Node* SubRL = SubR->_left;
		//10
		//  30
		//	   60
		Node* parent = cur->_parent;

		cur->_right = SubRL;
		if (SubRL)
			SubRL ->_parent = cur;


		SubR->_left = cur;
		cur->_parent = SubR;


		if (parent == nullptr)
		{
			_root = SubR;
			SubR->_parent = parent;
		}
		else
		{
			if (parent->_left == cur)
			{
				parent->_left = SubR;
				SubR->_parent = parent;
			}
			else if (parent->_right == cur)
			{
				parent->_right = SubR;
				SubR->_parent = parent;
			}
			else
			{
				assert(false);
			}
		}
	}

情况三： 新节点插入较高左子树的右侧-先左单旋再右单旋
1.在b树插入新节点

2.在c树插入新节点

3.60即为插入的新节点

以上三种情况都是先左旋再右旋，区别：旋转完之后节点的平衡因子不同

		Node* node = cur->_right;
		int bf = node->_bf;
		RotateL(cur);
		RotateR(parent);

		if (bf == 0)
		{
			parent->_bf = cur->_bf = node->_bf = 0;
		}
		else if (bf == -1)
		{
			cur->_bf = node->_bf = 0;
			parent->_bf = 1;

		}
		else if (bf == 1)
		{
			parent->_bf = node->_bf = 0;
			cur->_bf = -1;
		}

情况4：新节点插入较高右子树的左侧-先右单旋再左单旋

与情况三相同，60的平衡因子会影响旋转完之后30 60 90 的平衡因子

	Node* node = cur->_left;
	int bf = node->_bf;
	RotateR(cur);
	RotateL(parent);
	if (bf == 0)
	{
		parent->_bf = cur->_bf = node->_bf = 0;
	}
	else if (bf == 1)
	{
		cur->_bf = node->_bf = 0;
		parent->_bf = -1;
	}

	else if (bf == -1)
	{
		node->_bf = parent->_bf = 0;
		cur->_bf = 1;
	}