AVL 树

一、前言

前面对map/multimap/set/multiset和二叉搜索树进行了简单的介绍，前面几个容器的底层都是由平衡树来实现的，二叉搜索树在插入的数据有序或接近有序时会退化成单支树，时间复杂度会从$O(lgN)$退化成$O(N)$，因此我们需要对二叉树进行平衡处理，即实现平衡树，本节介绍的AVL树和后面要介绍的红黑树都属于平衡树的一种。

二、AVL树

1.AVL树的概念

一棵AVL树是空树或者是具有以下性质的二叉搜索树：
a.它的左右子树都是AVL树。
b.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
平衡因子的计算：右子树的高度减左子树的高度

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

2.AVL树节点的定义

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _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树的旋转

3.1右单旋（LL型）

当插入新节点后，|平衡因子|>=1时，需要调整树的结构，使之平衡化。（因为我们插入节点时是边插入边调整平衡因子的，所以最多出现2或-2的非法情况，也只需对此进行处理）

当父节点和当前节点都是左子树偏高时，我们仅需要对当前树进行右旋。
因为当前节点的子树高度之差为1，当且节点和父节点的高度差也为1，所以可以调整当前节点和父节点的位置来调整平衡因子（调整完后满足中序遍历是递增数列）
我们可以让当前节点（subL)的右子树(subLR)成为父节点(parent)的左子树，父节点成为当前节点的右子树即可调整好平衡因子。

我们需要对subL、subLR、parent节点的位置进行调整，调整的时候需注意判断subLR是否存在，和parent节点的具体位置（是根节点或是其父节点的左节点还是右节点）。节点位置调整完后将subL和parent平衡因子置为0。

代码如下：

void RotateR(Node* parent)
{//父节点和当前节点都是左子树偏高Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;parent->_pLeft = subLR;if (subLR){subLR->_pParent = parent;}subL->_pRight = parent;Node* ppNode = parent->_pParent;parent->_pParent = subL;if (parent == _root){_root = subL;_root->_pParent = nullptr;}else{//判断父节点的位置if (ppNode->_pLeft == parent){ppNode->_pLeft = subL;}else{ppNode->_pRight = subL;}subL->_pParent = ppNode;}parent->_bf = subL->_bf = 0;
}

3.2左单旋（RR型）

当当前节点和父节点都是右子树偏高时需要进行左旋，具体思路与右旋类似：
将当前节点的左子树作为父节点的右子树，同时将父节点作为当前节点的左子树。同样的需要注意当前节点左子树的存在情况和父节点的位置。

代码如下：

	void RotateL(Node* parent)
{Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;parent->_pRight = subRL;if (subRL)subRL->_pParent = parent;subR->_pLeft = parent;Node* ppNode = parent->_pParent;parent->_pParent = subR;if (parent == _root){_root = subR;_root->_pParent = nullptr;}else{if (ppNode->_pRight == parent){ppNode->_pRight = subR;}else{ppNode->_pLeft = subR;}subR->_pParent = ppNode;}parent->_bf = subR->_bf = 0;
}

3.3右左双旋（RL型）

当父节点和当前节点不是相同子树偏高时不能靠单旋平衡树的结构，这时后可以考虑依次对子树和当前树进行单旋。
当前节点的左子树偏高并且父节点的右子树偏高时进行右左双旋。先以当前节点作为父节点进行右单旋，再进行左单旋。
旋转过程：

右旋：当前节点（subR)的左节点（subRL)的右子树（c)作subR的左子树。subR作subRL的右子树。

左旋：subRL的左子树（b)作父节点（parent）的右子树，parent作subRL的左子树。

两次单旋调用前面实现的单旋函数即可，主要注意判断parent、subR、subRL的平衡因子的变化，看图当subRL的平衡因子变化时，根据subRL的左右子树b、c的高度和树调整完后b、c子树的位置来确定最终平衡因子的大小。

代码如下：

	void RotateRL(Node* parent){Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){//subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}
}

3.4左右双旋（LR型）

当前节点的右子树偏高并且父节点的左子树偏高时进行右左双旋。
还是要注意根据b、c子树的位置和高度来判断调整完后的平衡因子。

代码如下：

		void RotateLR(Node* parent){Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;RotateL(parent->_pLeft);RotateR(parent);subLR->_bf = 0;if (bf == -1){subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;}else{subL->_bf = 0;parent->_bf = 0;}}

4.AVL树的插入

步骤：
1.在AVL树中找到节点的位置（比左子树的节点大，比右子树的节点小）
2.插入节点
3.更新平衡因子（根据父节点、当前节点的平衡因子大小调用对应的旋转方法）

代码如下：

template<class T>
class AVLTree
{typedef AVLTreeNode<T> Node;
public:AVLTree(): _root(nullptr){}// 在AVL树中插入值为data的节点bool Insert(const T& data){if (_root == nullptr)//没有节点时{_root = new Node(data);return true;}Node* parent = nullptr;Node* cur = _root;while (cur)//搜索阶段，找到插入节点在AVL树中的正确位置{if (cur->_data < data){parent = cur;cur = cur->_pRight;//根节点的父节点置空，后续调整平衡因子的结束条件。}else if (cur->_data > data){parent = cur;cur = cur->_pLeft;}else{return false;}}cur = new Node(data);//插入阶段，插入节点if (parent->_data < data){parent->_pRight = cur;}else{parent->_pLeft = cur;}cur->_pParent = parent;//更新平衡因子while (parent){if (cur == parent->_pLeft){parent->_bf--;}else parent->_bf++;if (parent->_bf == 0)//平衡因子是0时对上层平衡因子没有影响，更新结束。{break;}else if (parent->_bf == 1 || parent->_bf == -1){//上层平衡因子改变，继续向上更新。cur = parent;parent = cur->_pParent;}else if (parent->_bf == 2 || parent->_bf == -2){//与AVL树性质冲突，需要旋转平衡一下。if (parent->_bf == -2 && cur->_bf == -1){//父节点和当前节点都是负数，说明都是左子树偏高，仅需右旋。RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//父节点和当前节点都是正数，都是右子树偏高，左旋RotateL(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//父节点右子树偏高，当前节点左子树偏高，右左双旋。RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//父节点左子树偏高，当前节点右子树偏高，左右双旋。RotateLR(parent);}break;}else{//因为是边插入边调整平衡因子，不存在其他平衡因子的可能，断死。assert(false);}}return true;}

5.AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树
   如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树
   每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
   节点的平衡因子是否计算正确

代码如下：

	size_t _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_pLeft), _Height(root->_pRight)) + 1;}bool _IsAVLTree(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_pLeft);int rightHeight = _Height(root->_pRight);// 不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_data << endl;return false;}// 顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_data << endl;return false;}return_IsAVLTree(root->_pLeft)&& _IsAVLTree(root->_pRight);}

6.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这
样可以保证查询时高效的时间复杂度，即$lo{g}_2(N)$。但是如果要对AVL树做一些结构修改的操
作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，
有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数
据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。