【重走C++学习之路】16、AVL树

目录

一、概念

二、AVL树的模拟实现

2.1 AVL树节点定义

2.2 AVL树的基本结构 

2.3 AVL树的插入

1. 插入步骤

2. 调节平衡因子

3. 旋转处理 

 4. 开始插入

2.4 AVL树的查找

2.5 AVL树的删除

1. 删除步骤

2. 调节平衡因子

3. 旋转处理

4. 开始删除

结语

---

一、概念

二叉搜索树查找效率为O(logN)，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率变为O(N)，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1(超过则需要对树中的节点进行调整)，即可降低树的高度，从而减少平均搜索长度。

AVL树具有以下特点：

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

平衡因子的取值由自己规定，在这里为了模拟实现，规定左子树的高度在根结点中为负值，右子树的高度在根结点中为正值，即平衡因子= 右子树高度 - 左子树高度。

二、AVL树的模拟实现

2.1 AVL树节点定义

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;    // 该节点的左孩子AVLTreeNode<K, V>* _right;   // 该节点的右孩子AVLTreeNode<K, V>* _parent;  // 该节点的父结点pair<K, V> _kv;int _bf;                     // 该节点的平衡因子AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

2.2 AVL树的基本结构 

template <class K, class V>
class AVLTree
{typedef AVTreeNode<K, V> Node;
public:bool Insert(const std::pair<K, V>& kv)；bool Find(const K& key)；bool Erase(const K& key)；private:Node* _root = nullptr;
};

2.3 AVL树的插入

1. 插入步骤

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

2. 调节平衡因子

插入节点后，会影响该节点到根节点这一条路径上节点的平衡因子，因此需要进行迭代，将这一条路径上的平衡因子更新。

步骤：

第一步： 对插入的节点的父节点进行更新，会发生两种情况：

1. 如果插入的是根节点，则无父节点，不用更新。
2. 如果插入的是父节点的左节点，则父节点的平衡因子-1；如果插入的是父节点的右节点，则父节点的平衡因子+1。

第二步： 父节点的平衡因子在插入节点后会有三种变化，也对应着三种措施：

1. 父节点的平衡因子变为0，则说明在插入前两颗子树高度相差1，插入后整体的高度没有发生变化，不需要向上继续调整。
2. 父节点的平衡因子变为-1或1，则说明在插入前两颗子树高度相等，插入后整体的高度+1，需要对父节点的父节点的平衡因子进行更新，这样就回到了步骤一。
3. 父节点的平衡因子变为-2或2，则说明在插入前两个子树高度相差1，且插入的节点为高度较高的那颗子树的叶子节点，这导致了高度相差变为2，需要进行旋转处理，降低树的高度，从而达到平衡整颗树的要求。

图解：

第一种情况：

第二种情况：

可以看到这里在更新平衡因子的时候，只会影响节点到根节点路径上的节点的平衡因子，其它的节点不需要考虑。

第三种情况：

更新平衡因子的时候，发现不满足规则后，直接停止更新，转而进行旋转处理。

3. 旋转处理 

旋转有四种情况：

第一种情况：右单旋

新节点插入到较高左子树的左侧，左侧的高度变高需要将右边的调整下来，因此叫做右单旋。

具体操作：

让subL的右孩子成为parent的左孩子，然后让parent成为subL的右孩子，最后把两个节点的平衡因子修改为0。

 图解：

实现代码：

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 1.先让把subL的右边作为parent的左边parent->_left = subLR;// 2.如果subLR不为空，就让subLR的父指针指向parentif (subLR) subLR->_parent = parent;// 3.记录parent的父节点的位置，然后把parent作为subL的右边Node* pParent = parent->_parent;subL->_right = parent;// 4.parent的父指针指向subLparent->_parent = subL;// 5.如果ppNode为空，说明subR现在是根节点，就让subL的父指针指向nullptr//   不是根节点就把subL的父指针指向parent的父节点，parent的父节点（左或右）指向subLif (pParent == nullptr){// 更新根节点_root = subL;subL->_parent = nullptr;}else{// 判断parent是pparent的左还是右if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;subL->_parent = pParent;}// 6.把parent和subL的平衡因子更新为0subL->_bf = parent->_bf = 0;
}

第二种情况：左单旋 

新节点插入到较高右子树的右侧，右侧的高度变高需要将左边的调整下来，因此叫做右单旋。

 具体操作：

让subR的左孩子成为parent的右孩子，然后让parent成为subR的左孩子，最后把两个节点的平衡因子修改为0。

图解：

实现代码：

void RotateL(Node* parent)
{		Node* subR = parent->_right;Node* subRL = subR->_left;// 1.先让把subR的左边作为parent的右边parent->_right = subRL;// 2.如果subRL不为空，就让subRL的父指针指向parentif (subRL) subRL->_parent = parent;// 3.先记录parent的父节点的位置，然后把parent作为subR的左边 Node* pParent = parent->_parent;subR->_left = parent;// 4.parent的父指针指向subRparent->_parent = subR;// 5.如果ppNode为空，说明subR现在是根节点，就让subR的父指针指向nullptr//   不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subRif (pParent == nullptr){// 更新根节点_root = subR;subR->_parent = nullptr;}else{// 判断parent是ppNode的左还是右if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;subR->_parent = pParent;}// 6.把parent和subR的平衡因子更新为0subR->_bf = parent->_bf = 0;
}

第三种情况：左右双旋 

新节点插入在较高左子树右侧，这里和第一种情况的区别就是前者是直线，后者是折线

具体操作：

先对subL进行一个左单旋，然后对parent进行右单旋，修改平衡因子，有三种改法。三个节点从左至右的三个节点一次是：subL、subLR和parent。
如果subLR的平衡因子为0，就将它们依次改为0，0, 0；
如果subLR的平衡因子为1，就将它们依次改为-1，0, 0；
如果subLR的平衡因子为-1，就将它们依次改为0，0, 1。

图解：（这里只画出了一种情况，剩下的类似）

实现代码：

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;// 保留subLR的平衡因子的值，方便知道新插入的节点是在subLR的左子树还是右子树// 旋转 先对subL进行左旋转，再对parent进行右旋转RotateL(subL);RotateR(parent);// 从左到右 subL subLR parentif (bf == -1)// subLR的左子树  bf: 0 0 1{subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1)// subLR的右子树 bf: -1 0 0{subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}
}

第四种情况：右左单旋 

新节点插入在较高右子树左侧，这里和第二种情况的区别就是前者是直线，后者是折线

 具体操作：

先对subR进行一个右单旋，然后对parent进行左单旋，修改平衡因子，有三种改法。三个节点从左至右的三个节点一次是：parent、subRL和subR。
如果subRL的平衡因子为0，就将它们依次改为0，0, 0；
如果subRL的平衡因子为1，就将它们依次改为-1，0, 0；
如果subRL的平衡因子为-1，就将它们依次改为0，0, 1。

图解：（这里只画出了一种情况，剩下的类似）

实现代码：

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;// 保留subRL的平衡因子的值，方便知道新插入的节点是在subRL的左子树还是右子树// 旋转 先对subR进行右旋转，再对parent进行左旋转RotateR(subR);RotateL(parent);// 从左到右 parent subRL subRif (bf == -1)// subRL的左子树  bf: 0 0 1{parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1)// subRL的右子树 bf: -1 0 0{parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}
}

 4. 开始插入

bool Insert(const pair<K, V>& kv)
{// 先按照二叉搜索数一样插入元素// 无节点是插入if (_root == nullptr){_root = new Node(kv);return true;}// 有节点时插入Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;// 小于往左走if (kv.first < cur->_kv.first){cur = cur->_left;}// 大于往右走else if (kv.first > cur->_kv.first){cur = cur->_right;}else{// 找到了，就返回falsereturn false;}}cur = new Node(kv);// 判断cur应该插在parent的左还是右 // 小于在左，大于在右		if (cur->_kv.first < parent->_kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}// 更新parent的平衡因子// 节点的插入只会影响cur的祖先的平衡因子（不是所有的，是一部分，分情况）while (parent){// 更新parent的平衡因子// cur在parent的左，parent->_bf--// cur在parent的右，parent->_bf++if (cur == parent->_left)parent->_bf--;elseparent->_bf++;// bf 可能为 -2、-1、0、1、2if (parent->_bf == 0){// 对上层无影响，退出break;}else if (parent->_bf == -1 || parent->_bf == 1){// 对上层有影响，迭代更新cur = parent;parent = parent->_parent;}else{// 平衡树出现了问题，需要调整// 1.右边高，左旋转调整if (parent->_bf == 2){// 如果是一条直线==>左旋转即可// 如果是一条折线==>右左旋转if (cur->_bf == 1)RotateL(parent);else if (cur->_bf == -1)RotateRL(parent);}// 2.左边高，右旋转调整else if (parent->_bf == -2){// 如果是一条直线==>右旋转即可// 如果是一条折线==>左右旋转if (cur->_bf == -1)RotateR(parent);else if (cur->_bf == 1)RotateLR(parent);}// 调整后是平衡树，bf为0，不需要调整了break;}}return bool;
}

2.4 AVL树的查找

与二叉搜索树的过程一致，这里就不多解释了，直接上代码：

bool Find(const K& key)
{if (_root == nullptr)return false;Node* cur = _root;while (cur){// 小于往左走if (key < cur->_kv.first){cur = cur->_left;}// 大于往右走else if (key > cur->_kv.first){cur = cur->_right;}else{// 找到了return true;}}return false;
}

2.5 AVL树的删除

1. 删除步骤

1. 我们先按照二叉搜索树树删除节点的方式，删除节点。
2. 根据对应删除情况更新平衡因子，更新平衡因子的方法与插入的更新方法是相反的。

2. 调节平衡因子

步骤：

第一步：

1. 删除节点后，如果删除的节点为根节点，就结束。
2. 如果删除节点是父节点的左孩子，那么父节点的平衡因子加1；删除节点是父节点的右孩子，那么父节点的平衡因子减1。

第二步：父节点的平衡因子在插入节点后会有三种变化，也对应着三种措施：

1. 父节点的平衡因子变为0，则说明删除前父亲的平衡因子为1或-1，多出一个左节点或右节点，删除节点后，左右高度相等，整体高度减1，对上层有影响，需要继续调节。
2. 父节点的平衡因子变为-1或1，则说明删除前父亲的平衡因子为0，左右高度相等，删除节点后，少了一个左节点或右节点，但是整体高度不变，对上层无影响，不需要继续调节。
3. 父节点的平衡因子变为-2或2，则说明删除前父亲的平衡因子为-1或1，多了一个左节点或一个右节点，删除了一个右节点或左节点，此时多了两个左节点和右节点，这棵子树一边已经被拉高了，此时这棵子树不平衡了，需要旋转处理。

3. 旋转处理

这里的旋转与插入时旋转的没有区别，就不详细解答了，直接上代码。

4. 开始删除

bool Erase(const K& key)
{if (_root == nullptr)return false;// 有节点时插入Node* parent = nullptr;Node* cur = _root;while (cur){// 小于往左走if (key < cur->_kv.first){parent = cur;cur = cur->_left;}// 大于往右走else if (key > cur->_kv.first){parent = cur;cur = cur->_right;}else{// 找到了// 1.左边为空，把parent指向cur的右// 2.右边为空，把parent指向cur的左// 3.左右都不为空，用右子树的最左边的节点的值替换要删除的节点，然后转换为用1的情况删除该节点if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;delete cur;break;}else{if (parent->_left == cur){parent->_left = cur->_right;parent->_bf++;}else{parent->_right = cur->_right;parent->_bf--;}}if (parent->_bf != -1 && parent->_bf != 1) UpdateBf(parent);delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;delete cur;break;}else{if (parent->_left == cur){parent->_left = cur->_left;parent->_bf++;}else{parent->_right = cur->_left;parent->_bf--;}}if (parent->_bf != -1 && parent->_bf != 1) UpdateBf(parent);delete cur;}else{Node* rightMinParent = cur;Node* rightMin = cur->_right;// 先去右子树while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;// 一种往左走}cur->_kv = rightMin->_kv;// 替代删除// 删除minNode  第一种情况：左节点为空if (rightMinParent->_left == rightMin){rightMinParent->_left = rightMin->_right;rightMinParent->_bf++;}else{rightMinParent->_right = rightMin->_right;rightMinParent->_bf--;}if (rightMinParent->_bf != -1 && rightMinParent->_bf != 1)                 UpdateBf(rightMinParent);delete rightMin;}return true;}}return false;
}void UpdateBf(Node* parent)
{if (parent == nullptr)return;Node* cur = parent;goto first;while (parent){// 更新parent的平衡因子// cur在parent的左，parent->_bf++// cur在parent的右，parent->_bf--if (cur == parent->_left)parent->_bf++;elseparent->_bf--;// bf 可能为 -2、-1、0、1、2first:if (parent->_bf == 0){// 对上层有影响，迭代更新// 如果parent是根节点就结束if (parent->_parent == nullptr)break;cur = parent;parent = parent->_parent;}else if (parent->_bf == -1 || parent->_bf == 1){// 对上层无影响，退出break;}else{// 平衡树出现了问题，需要调整// 1.右边高，左旋转调整if (parent->_bf == 2){// 如果是一条直线==>左旋转即可// 如果是一条折线==>右左旋转if (parent->_right->_bf == 1){RotateL(parent);cur = parent->_parent;parent = cur->_parent;continue;}else if (parent->_right->_bf == -1)// 调整后 p sL s  如果sL是1或-1可以退出 {Node* s = parent->_right;Node* sL = s->_left;RotateRL(parent);// 不平衡向上调整if (sL->_bf != 1 && sL->_bf != -1){cur = sL;parent = cur->_parent;continue;}}else if (parent->_right->_bf == 0)    // 平衡因子修改{RotateL(parent);parent->_bf = 1;parent->_parent->_bf = -1;}}// 2.左边高，右旋转调整else if (parent->_bf == -2){// 如果是一条直线==>右旋转即可// 如果是一条折线==>左右旋转if (parent->_left->_bf == -1){RotateR(parent);cur = parent->_parent;parent = cur->_parent;continue;    //parent不是-1或1就继续}else if (parent->_left->_bf == 1)// 调整后 s sR p  如果sL是1或-1可以退出{Node* s = parent->_left;Node* sR = s->_right;RotateLR(parent);// 不平衡向上调整 为0时如果parent为根//if (sR->_bf != 1 && sR->_bf != -1){cur = sR;parent = cur->_parent;continue;}}else if (parent->_left->_bf == 0)    // 平衡因子修改{RotateR(parent);parent->_parent->_bf = 1;parent->_bf = -1;}}// 调整后是平衡树，bf为1或-1，不需要调整了break;}}
}

结语

上面这些是AVL树的大致内容，其中旋转是有些难的地方，但是面试会考察，需要着重掌握，而删除是二叉搜索树的删除加上旋转的叠加，难度更上一层了，这里如果没能理解，可以自己画一画图，并且配合着插入的图来分析，应该会有所帮助。

下一篇将会介绍二叉搜索树的另一种改良：红黑树，有兴趣的朋友可以关注一下。