二叉树之AVL树

文章目录

- 1. AVL树的概念（logN)
- - 1.1背景
  - 1.2规则
- 2.AVL树节点的定义
- 3.AVL树的插入
- 4. AVL树的旋转(重点）
- - 4.1 新节点插入较高的右子树的右侧：左单璇；
  - 4.2 新节点插入较高左子树的左侧：右单璇；
  - 4.3（双旋）新节点插入较高右子树的左侧---右左：先右单旋再左单旋
  - - 4.3.1添加节点位置的三种情况
  - 4.4 新节点插入较高左子树的右侧---左右：先左单旋再右单旋
- 5.判断AVL树是否平衡

1. AVL树的概念（logN)

1.1背景

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素效率低下。

1.2规则

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

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

平衡因子：右子树节点个数减左子树的个数

注意：平衡因子不是必须的，只是辅助；

问题：为什么平衡因子不能超过1呢；
原因：因为实现不了0，最低的高度差就是1；

2.AVL树节点的定义

AVL树节点的定义

template<class T>
struct AVLTreeNode
{
 AVLTreeNode(const T& data)
     : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
 , _data(data), _bf(0)
 {}
 AVLTreeNode<T>* _pLeft;   // 该节点的左孩子
 AVLTreeNode<T>* _pRight;  // 该节点的右孩子
 AVLTreeNode<T>* _pParent; // 该节点的双亲
 T _data;
 int _bf;                  // 该节点的平衡因子
};

3.AVL树的插入

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

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

bool Insert(const T& data)
{
    // 1. 先按照二叉搜索树的规则将节点插入到AVL树中
    // ...
    
    // 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否
破坏了AVL树
    //   的平衡性
    
 /*
 pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent
 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
  1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
  2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可
  
 此时：pParent的平衡因子可能有三种情况：0，正负1， 正负2
  1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整
成0，此时满足
     AVL树的性质，插入成功
  2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
新成正负1，此
     时以pParent为根的树的高度增加，需要继续向上更新
  3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进
行旋转处理
 */
 while (pParent)
 {
   // 更新双亲的平衡因子
 if (pCur == pParent->_pLeft)
 pParent->_bf--;
 else
 pParent->_bf++;
 // 更新后检测双亲的平衡因子
 if (0 == pParent->_bf)
       {    
            break;
       }
 else if (1 == pParent->_bf || -1 == pParent->_bf)
 {
  // 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲
为根的二叉树
  // 的高度增加了一层，因此需要继续向上调整
 pCur = pParent;
 pParent = pCur->_pParent;
 }
 else
 {
 // 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以pParent
 // 为根的树进行旋转处理
               if(2 == pParent->_bf)
             {
                  // ...
             }
              else
             {
                  // ...
             }
 }
 }
 return true;
}

4. AVL树的旋转(重点）

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：
注意：前两者是单旋他们的模型是相同的；
后俩者是双旋他们的模型相同；
在这里插入图片描述

4.1 新节点插入较高的右子树的右侧：左单璇；

左单璇的情况是：根的左子树是单身汉（成对的少）；
解决方法：将根右子树的左子树过继根的左子树的右子树；这样根的右子树就帮了根的忙；根就认了右子树为义父；
在这里插入图片描述
代码实现

	void _RotateL(Node* pParent)
	{
		Node* ppParent = pParent->_parent;
		Node* rChild = pParent->_right;
		Node* rlChild = pParent->_right->_left;
		rChild->_left = pParent;
		pParent->_right = rlChild;

		if(rlChild)//这里判断rlchild是否为空
		rlChild->_parent = pParent;
		pParent->_parent = rChild;
		if (_root == pParent)
		{
			_root = rChild;
			rChild->_parent = nullptr;
		}
		else
		{
			if (ppParent->_right == pParent)
			{
				ppParent->_right = rChild;
			}
			else
			{
				ppParent->_left = rChild;
			}
			rChild->_parent = ppParent;

		}
		pParent->_bf = rChild->_bf = 0;//这里的目的就是将者里的2和1的节点干成0；
	}

4.2 新节点插入较高左子树的左侧：右单璇；

在这里插入图片描述
代码实现

void _RotateR(Node* pParent)
	{
		Node* ppParent = pParent->_parent;
		Node* lChild = pParent->_left;
		Node* lrChild = pParent->_left->_right;
		lChild->_right = pParent;
		pParent->_left = lrChild;

		if (lrChild)//这里判断rlchild是否为空
			lrChild->_parent = pParent;
		pParent->_parent = lChild;
		if (_root == pParent)
		{
			_root = lChild;
			lChild->_parent = nullptr;
		}
		else
		{
			if (ppParent->_right == pParent)
			{
				ppParent->_right = lChild;
			}
			else
			{
				ppParent->_left = lChild;
			}
			lChild->_parent = ppParent;

		}
		pParent->_bf = lChild->_bf = 0;//这里的目的就是将者里的2和1的节点干成0；
	}

4.3（双旋）新节点插入较高右子树的左侧—右左：先右单旋再左单旋

4.3.1添加节点位置的三种情况

在这里插入图片描述
代码实现

//主函数
else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateR(parent);
				}

//函数体
void _RotateRL(Node* pParent)
	{
		_RotateR(pParent->_right);
		_RotateL(pParent);
		Node* subR = pParent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		if (bf == -1)
		{
			subRL->_bf = 0;
			subR->_bf = 1;
			pParent->_bf = 0;
		}
		else if (bf == -1)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			pParent->_bf = -1;
		}
		else if (bf == 0)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			pParent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

4.4 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

在这里插入图片描述

5.判断AVL树是否平衡

这里不可以使用遍历平衡因子，原因：平衡因子有可能是错的；
使用左右子树的高度想减的方法：

	//先想空
	//在使用递归
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}


	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);

	}