【C++】AVL树

前言

前面我们在数据结构中学习了树，以及二叉树，还有二叉排序树，这节来学习平衡二叉树。

数据结构专题学习：数据结构学习
C++专题学习：深入学习C++

平衡二叉树的定义

在使用二叉排序树时，二叉排序树的查找效率取决于树的高度，当构造二叉排序树的输入序列是有序的时候，它就会形成只有左子树（从大到小输入）或者只有右子树（从小到大输入）的单支树，此时二叉排序树的性能显著变坏。
因此，为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除节点时，要保证任意节点的左、右子树高度差的绝对值不超过1，将这样的树就称为平衡二叉树，即AVL树。
它给树中的每个节点都定义了一个平衡因子（bf）。
节点的平衡因子=左子树高度-右子树高度。（当然也有右子树高度-左子树高度的，只要不违背高度差的绝对值不超过一即可）
平衡二叉树具有以下几个性质：

AVL树是一棵二叉排序树
AVL树的左右子树也都是AVL树
AVL树节点的平衡因子的值只能为-1，0，1

AVL树如下图所示：
在这里插入图片描述

AVL树是一个三叉链结构，不仅有指向左右孩子节点的指针，还有指向父节点的指针，AVL树的代码定义如下：

template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;//std::pair是C++标准库中的一个模板类，它能把两个不同类型的值组合成一个单元，这两个值分别由 first 和 second 成员访问。AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr),_bf(0){}
};

AVL树的插入

AVL树插入的大致过程

在插入值时会按照二叉排序树的插入规则进行插入。
插入新节点后，会影响祖先节点的高度，即影响祖先的平衡因子，因此要检查其插入路径上的节点是否因为此次操作而导致了不平衡。
如果导致了不平衡，也就是平衡因子变为了2或-2，此时就要调整这棵子树，进行旋转，从而调节平衡因子。从新插入的节点开始往上找，找到第一个不平衡的节点，调整以该节点为根的最小不平衡子树。
如果更新平衡因子没有出现问题，则插入结束。

更新平衡因子

根据节点的平衡因子=左子树高度-右子树高度。在插入节点后，对节点进行更新平衡因子。
代码如下：

bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){//如果要插入节点的值大于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);//判断插在parent节点的左边还是右边if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因子while (parent){if (cur == parent->_left)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){// 继续往上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 不平衡了，旋转处理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){//左孩子的右子树高了，先左旋再右旋RotateLR(parent);}else{//右孩子的左子树高了，先右旋再左旋RotateRL(parent);}break;}else{assert(false);}}return true;}

调整最小不平衡因子

为了既能保证搜索树的规则，又能降低树的高度，调整平衡因子，总共有四种旋转操作：左单旋/右单旋/左右双旋/右左双旋。下面依次来解释。
首先，在调整之前，我们先要找到第一个不平衡的节点，从上面的调整平衡因子就可以知道。然后以该节点作为根节点，它所对应的子树就是我们要调整的最小不平衡子树。如下图：
在这里插入图片描述
因为==只要把最小的这棵不平衡子树让它恢复之后，它的祖先节点的平衡因子也都会恢复，==因此在插入一个新节点导致不平衡之后，我们只需要调整最小的这棵子树，就可以让其它节点也恢复平衡。

左单旋

当在节点A的右孩子的右子树上插入了一个新节点后，导致了A的平衡因子由-1减至-2，导致以A为节点的子树失去平衡，此时就需要一次左单旋操作。如下图所示：
在这里插入图片描述

图中：
H代表各个子树的高度都为H，至于为什么都为H，而不是H-1或者H+1，大家可以自行带入，找平衡因子就可以知道了。
RR插入，指的是在右孩子的右子树上插入了一个新节点导致树的不平衡。
BL：B的左孩子，BR：B的右孩子，AL：A的左孩子
二叉排序树的特性：左子树节点值 < 根节点值 < 右子树节点值

左单旋的过程为：将A的右孩子B左上旋转代替A成为根节点，将A节点左下旋转成为B的左孩子，而B的原左子树成为A的右子树。

void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)//如果subRL，即右孩子的左子树不为空，则更新它的父节点subRL->_parent = parent;//找到原来父节点的父节点Node* parentParent = parent->_parent;//将父节点更新到原来右孩子的左边subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr)//如果原来父节点就是根节点，则更新根节点{_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}//更新平衡因子。parent->_bf = subR->_bf = 0;}

可能有些复杂，学会大致思路也行，大致思路如下（设节点A是f，节点B是p，节点A的父节点是gf）：

f->left = p -> right;
p->right = f;
gf->left/right = p;

右单旋

当在节点A的左孩子的左子树上插入了一个新节点后，导致了A的平衡因子由1增至2，导致以A为节点的子树失去平衡，此时就需要一次右单旋操作。如下图所示：
在这里插入图片描述

右单旋的过程为：将A的左孩子B向右上旋转代替A成为根结点，将A右下旋转成为B的右孩子，而B的右子树变为A的左子树。

void  RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_bf = subL->_bf = 0;}

大致思路如下（设节点A时f，节点B是p，节点A的父节点是gf）：

f->right = p->left;
p->left = f;
gf->left/right = p;

左右双旋

当在节点A的左孩子的右子树上插入了一个新节点后，导致了A的平衡因子由1增至2，导致以A为节点的子树失去平衡，此时就需要两次旋转操作，先左旋一次，再进行右旋。如下图所示：
在这里插入图片描述

左右双旋的过程为：先将A的左孩子B的右子树的根节点C向左上旋转提升到B的位置，然后把C向右上提升到A的位置。

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

右左双旋

当在节点A的右孩子的左子树上插入了一个新节点后，导致了A的平衡因子由-1减至-2，导致以A为节点的子树失去平衡，此时就需要两次旋转操作，先右旋转一次，再进行左旋。如下图所示：
在这里插入图片描述

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

AVL树的删除

AVL树的删除有以下几个步骤：

用二叉排序树的方法对节点w执行删除操作。
若导致了不平衡，则从节点w开始向上回溯，找到第一个不平衡的节点z(最小不平衡子树)，找到节点z的高度最高的孩子y(即"个头"最高的儿子)，再找到节点y的高度最高的孩子x(即"个头"最高的孙子)。
对以z为根的子树进行平衡调整：
①孙子在LL，则进行右单旋。
②孙子在LR，则进行左右双旋。
③孙子在RR，则进行左单旋。
④孙子在RL，则进行右左双旋。
若调整后子树高度减1，则可能需要对z的祖先节点进行平衡调整直至回溯到根节点。

二叉排序树的删除操作可参考下图：
在这里插入图片描述
删除操作如下图：

AVL树的查找

在AVL树上查找的过程与BST数相同。因此查找过程中，进行关键字比较次数不超过树的深度。假设n_h表示深度为h的AVL树中含有的最少节点数。显然有n₀=1，n₁=1，n₂=2并且有n_h=n_h-2+n_h-1+1，如下图所示，则可以依次推出深度为h的AVL树含有的最少节点。含有n个节点的AVL树的最大深度为O(log~2~n)，因此平均查找效率为O(log~2~n)。
在这里插入图片描述
查找的代码如下：

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;
}