二叉树之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， 正负21. 如果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--;elsepParent->_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);}