18.AVL树的模拟实现

server/2024/12/22 14:49:51/

前面对map/multimap/set/multiset进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

1. AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

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

image-20230320203650271

2. AVL树节点的定义

// 节点的类模板
template<class K, class V>
struct AVLTreeNode
{// 键对值的对象 _kvpair<K, V> _kv;// 左子树的根节点AVLTreeNode<K, V>* _left;// 右子树的根节点AVLTreeNode<K, V>* _right;// 父节点AVLTreeNode<K, V>* _parent;int _bf;  // balance factor:平衡因子// 节点的构造函数AVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};

3.insert

bool Insert(const pair<K, V>& kv)
{// 如果根节点_root，那么就创建新节点，并其赋值给_root// 返回真，表示插入成功if (_root == nullptr){_root = new Node(kv);return true;}// 将父亲节点初始化为空Node* parent = nullptr;// 将当前节点cur初始化为根节点Node* cur = _root;// 第一步：找到kv键值对要插入的位置while (cur){// 1.cur节点对应的key值小于将要插入的key值if (cur->_kv.first < kv.first){// 迭代parent = cur;// 向右子树走cur = cur->_right;}// 2.cur节点对应的key值大于将要插入的key值else if (cur->_kv.first > kv.first){// 迭代parent = cur;// 向左走cur = cur->_left;}else{// 3.如果相等，根据二叉搜索树的性质(不允许出现重复的key值)return false;}}// 第二步：创建新节点，使用要插入的kv来初始化这个新节点// 1.parent是指向cur的，根据二叉搜索树的性质cur = new Node(kv);// 2.如果parent节点的key值小于要插入的key值，那么cur连接到parent的右子树if (parent->_kv.first < kv.first){// 父节点指向curparent->_right = cur;// cur指向父节点cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 第三步：更新平衡因子// 当parent为空，也就更新到了整棵树的根节点while (parent) {// 3.1 因为新添加了一个节点，所以要更新其对应parent的平衡因子// 平衡因子 = 右子树的高度 - 左子树的高度// 新增在右，parent->bf++;// 新增在左，parent->bf--;if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}// 3.2 是否继续更新依据：子树的高度是否变化// 如下图所示// 情况1:更新后：parent->_bf == 0 // 说明插入节点之前 parent->_bf 是 1 或者 -1// 说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新// 情况2、// 更新后：parent->_bf == 1 或 -1 // 说明插入节点之前是 parent->_bf == 0，两边一样高，现在插入一边更高了，parent所在子树高度变了，继续往上更新// 情况3、// 更新后：parent->_bf == 2 或 -2，// 说明之前parent->_bf == 1 或者 -1，现在插入节点严重不平衡，违反规则，就地处理--旋转// 旋转：// 1、让这颗子树左右高度差不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致// 3.3 迭代更新// 情况1：不需要继续往上更新，因此直接跳出循环就可以if (parent->_bf == 0){break;}// 情况2：继续往上更新（情况2向上更新可能会变为情况3，也可能迭代到parent为空，跳出循环）else if (parent->_bf == 1 || parent->_bf == -1){// 向cur的父亲节点进行迭代cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 情况3：此时必须进行旋转了旋转// 3.1 当前节点cur的父节点的平衡因子为2，当前节点的平衡因子为1if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){// 3.2RotateR(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{// 如果不满足上面的三种情况，那么就会直接报错assert(false);}}return true;
}

image-20230321195312585

image-20240424164113178

3.1 旋转

​ 如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

左单旋

image-20230321150312986

思路：

  1. val为30的这个节点的右子树的根节点的val值必然大于30（根据二叉搜索树的性质）,因此将val值为60的节点的左子树根节点链接到30的右子树

  2. 将30的根节点链接到60的左子树

  3. 这样就完成了左旋

void RotateL(Node* parent)
{// 第一步：// subR、subRL、parent的关系如上图所示// subR 是根节点的右子树的根节点// subRL 是根节点subR的左子树的根节点// parent 是整棵树的根节点Node* subR = parent->_right;Node* subRL = subR->_left;// 1.将subR的左子树根节点连接到parent节点的右子树（完成单向连接）parent->_right = subRL;// 2.如果subRL不为空，则它的父指针需要指向parent整棵树的根节点（完成双向连接）if (subRL)subRL->_parent = parent; // 第二步：// 提前保存整颗二叉树的根节点parent的父节点指针，保存为ppNodeNode* ppNode = parent->_parent;// 将parent为根节点的树连接到subR的左子树（单向连接）subR->_left = parent;// 让parent的父节点的指针指向subR（完成双向连接）parent->_parent = subR;// 第三步：连接新树的根节点subR到ppNodeif (ppNode == nullptr){// 如果ppNode为空，说明parent之前的parent->parent为空// 此时经过旋转subR就是新树的根节点，所以根节点的父指针需要指向空_root = subR;_root->_parent = nullptr;}else{//  说明parent之前不是根节点，那么就需要将其与原本的parent的上一层节点链接起来//  此时ppNode的左子树，或者右子树还指向parentif (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}// subR的父节点也需要指向ppNodesubR->_parent = ppNode;}// 第四步：更新平衡因子// 经过旋转之后，parent和subR的左右子树是平衡的，因此平衡因子为0parent->_bf = subR->_bf = 0;
}

右单旋

image-20230321155839673

//  思路与左单旋一致
void RotateR(Node* parent)
{// 第一步：// parent是整棵树的根节点// subL是parent左子树的根节点Node* subL = parent->_left;// subLR 是subL节点右子树的根节点Node* subLR = subL->_right;// 第二步：// 1.parent的left指针指向subLR(单向连接)parent->_left = subLR;// 2.subLR的父指针指向parent(完成双向连接)if (subLR){subLR->_parent = parent;}// 第二步：// 1.保存parent的父指针为ppNodeNode* ppNode = parent->_parent;// 2.subL是新树的根节点，subL的右指针，指向parent(单向连接)subL->_right = parent;// 3.parent的父指针指向subL(完成双向连接)parent->_parent = subL;// 第三步：将新树的根节点subL与ppNode完成双向连接//if (_root == parent)if (ppNode == nullptr){// 如果ppNode为空，那么subL就是根节点，没有上层节点可以连接_root = subL;// 所以_root的父节点为空_root->_parent = nullptr;}else{// 如果ppNode->_left指向parent节点，那么ppNode左子树的根节点为subL(单向连接)if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}// subL的父指针指向ppNode(完成双向连接)subL->_parent = ppNode;}// 第四步：更新平衡因子subL->_bf = parent->_bf = 0;
}

先左单旋，再右单旋

image-20230321194942365

void RotateLR(Node* parent)
{// parent->_left 指向的就是左单旋的根节点Node* subL = parent->_left;// subL->_right 就是新增的节点的子树的根节点Node* subLR = subL->_right;// 最终判断 subL  subLR  parent的平衡因子，// 需要根据新增节点后的subLR->_bf(平衡因子)来判断，因此先保存,旋转后它（平衡因子）将会改变int bf = subLR->_bf;// 以parent->_left指向的节点为根节点进行左旋RotateL(parent->_left);// 以parent节点为根节点进行右旋RotateR(parent);if (bf == -1) {// 情况1(更新平衡因子，如上图所示，如果是b新增节点，那么旋转后为情况1)// subLR左子树新增，经过左右双旋后的平衡因子subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1) {// 情况2(更新平衡因子，如上图所示，如果是c新增节点，那么旋转后为情况2)// subLR右子树新增，经过左右双旋后的平衡因子parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == 0) {// 情况3(更新平衡因子，如上图所示，如果h为0，val值为60的节点是新增节点，那么旋转后为情况3)// subLR节点本身就是新增节点，，经过左右双旋后的平衡因子parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}
}

先右单旋，再左单旋

image-20230321211623928

// 思路与先左单旋，再右单旋一致
void RotateRL(Node* parent)
{// parent->_right 指向的就是右单旋的根节点Node* subR = parent->_right;// 新增节点所在子树的根节点为subR->_leftNode* subRL = subR->_left;// 最终判断 subL  subLR  parent的平衡因子，// 需要根据新增节点后的subLR->_bf(平衡因子)来判断，因此先保存,旋转后它（平衡因子）将会改变int bf = subRL->_bf;// parent->_right 指向的就是右单旋的根节点RotateR(parent->_right);// parent是左单旋的根节点RotateL(parent);if (bf == 1){// 情况1：b树新增节点时subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){// 情况2：c树新增节点时subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 0){// 情况3：h的高度为0时subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

4.中序遍历

void Inorder()
{_Inorder(_root);
}void _Inorder(Node* root)
{if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);
}

5.AVL树的验证

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

  1. 验证其为二叉搜索树

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

  1. 验证其为平衡树
  • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
  • 节点的平衡因子是否计算正确

平衡的验证

bool IsBalance()
{return IsBalance(_root);
}int Height(Node* root)
{if (root == nullptr)return 0;// 左子树的高度int lh = Height(root->_left);// 右子树的高度int rh = Height(root->_right);// 如果左子树的高度大于右子树的高度，那么左子树的高度+1,并返回，// 反之右子树的高度+1，并返回// 如果左右子树高度相等，那么返回0return lh > rh ? lh + 1 : rh + 1;
}// 验证平衡，也就是验证左右子树的高度差的绝对值要小于2
bool IsBalance(Node* root)
{// if (root == nullptr){return true;}// 左子树的高度int leftHeight = Height(root->_left);// 右子树的高度int rightHeight = Height(root->_right);// 如果右子树的高度减左子树的高低，得到的平衡因子与根节点的平衡因子不一致，说明平衡因子异常if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first <<"平衡因子异常" << endl;return false;}//  需要判断整颗树，和子树的(左右子树的)高度差的绝对值都是小于2的，因此要递归到每一个子树return abs(rightHeight - leftHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);
}

6.类模板

#pragma once
#include <assert.h>
#include <time.h>// AVL树节点的类模板
template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;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树的类模板
template<class K, class V>
struct AVLTree
{// 将AVL树节点的类模板类型定义为Nodetypedef AVLTreeNode<K, V> Node;
public:// 插入函数bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (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);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 1、更新平衡因子while (parent) // parent为空，也就更新到根{// 新增在右，parent->bf++;// 新增在左，parent->bf--;if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}// 是否继续更新依据：子树的高度是否变化// 1、parent->_bf == 0说明之前parent->_bf是 1 或者 -1// 说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新// 2、parent->_bf == 1 或 -1 说明之前是parent->_bf == 0，两边一样高，现在插入一边更高了，// parent所在子树高度变了，继续往上更新// 3、parent->_bf == 2 或 -2，说明之前parent->_bf == 1 或者 -1，现在插入严重不平衡，违反规则// 就地处理--旋转// 旋转：// 1、让这颗子树左右高度不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致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){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}// 左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;}// 右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;//if (_root == parent)if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}// 先左单旋，再右单旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1) // subLR左子树新增{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1) // subLR右子树新增{parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == 0) // subLR自己就是新增{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}// 先右单旋，再左单旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);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 if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}// 中序遍历void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}int Height(Node* root){if (root == nullptr)return 0;int lh = Height(root->_left);int rh = Height(root->_right);return lh > rh ? lh + 1 : rh + 1;}// 判断是否平衡bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr){return true;}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);}private:Node* _root = nullptr;
};

7.验证用例

  • 常规场景1

{16, 3, 7, 11, 9, 26, 18, 14, 15}

  • 特殊场景2

{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

image-20240424164158931

void TestAVLTree1()
{srand(time(0));const size_t N = 100000;AVLTree<int, int> t;for (size_t i = 0; i < N; ++i){size_t x = rand();t.Insert(make_pair(x, x));//cout << t.IsBalance() << endl;}//t.Inorder();cout << t.IsBalance() << endl;
}

8.AVL树的性能

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


http://www.ppmy.cn/server/13101.html

相关文章

【Linux开发 第五篇】vi和vim

【Linux开发 第五篇】vi和vim

vi和vim Linux系统会内置Vi编辑器 Vim具有程序编辑的能力&#xff0c;可以看作是Vi的增强版本&#xff0c;可以主动的以字体颜色辨别语法的正确性&#xff0c;方便程序设计 三种模式 正常模式&#xff1a;vim打开一个文档就直接进入一般模式&#xff0c;可以进行复制&#x…
阅读更多...
idea同步yapi插件

idea同步yapi插件

1、前言 yapi是一个很好的接口文档维护工具&#xff0c;其swagger功能&#xff0c;可将接口信息同步到yapi平台上&#xff0c;但是swagger的编写&#xff0c;大量入侵代码&#xff0c;也加大了开发工作量&#xff0c;目前调研了idea集成yapi同步工具&#xff0c;无需嵌入式编写…
阅读更多...
RakSmart站群服务器租用注意事项科普

RakSmart站群服务器租用注意事项科普

随着互联网的飞速发展&#xff0c;站群运营成为越来越多企业和个人的选择。而RakSmart作为知名的服务器提供商&#xff0c;其站群服务器租用服务备受关注。在租用RakSmart站群服务器时&#xff0c;源库建议有一些关键的注意事项需要特别留意&#xff0c;以确保服务器的稳定运行…
阅读更多...
python练习-水仙花数

python练习-水仙花数

1. 需求 打印出所有"水仙花数"&#xff0c;所谓"水仙花数"是指一个三位数[100, 1000)&#xff0c;其各位数字立方和等于该数本身。 例如&#xff1a;153是一个"水仙花数"&#xff0c;因为1531的三次方&#xff0b;5的三次方&#xff0b;3的三次…
阅读更多...
css中backface-visibility使用

css中backface-visibility使用

backface-visibility 是一个 CSS 属性&#xff0c;用于控制元素的背面是否可见。它主要用于在进行3D转换时控制元素的背面可见性。当一个元素被旋转或进行其他3D变换时&#xff0c;通常浏览器默认会进行背面剪裁&#xff08;backface culling&#xff09;&#xff0c;使得元素的…
阅读更多...
网络机顶盒哪个好？内行分享2024热销网络机顶盒排名

网络机顶盒哪个好？内行分享2024热销网络机顶盒排名

在挑选网络机顶盒的时候不知道网络机顶盒哪个好的新手们往往会参考销量排行榜。本人身为多年从业者&#xff0c;对整个行业动态密切关注&#xff0c;接下来将要给各位分享目前业内最新发布的2024畅销网络机顶盒排名&#xff0c;想知道网络机顶盒如何选看这篇就足够了。 推荐一、…
阅读更多...
影视后期特效合成：DaVinci Fusion Studio19 激活版

影视后期特效合成：DaVinci Fusion Studio19 激活版

DaVinci Fusion Studio是一款功能强大的影视后期特效合成软件&#xff0c;可广泛应用于视觉效果、广播电视设计、动态图形设计、3D动画设计等领域。 如综合的绘图、动态掩蔽、遮片、图层叠加、字幕等工具&#xff0c;结合高效的粒子生成系统&#xff0c;通过它可以创建各种精细…
阅读更多...
BTSB-面试题

BTSB-面试题

面试笔试题 在32位系统里面&#xff0c;用C语言写一个程序&#xff0c;如何判断小端和大端 #include <stdio.h>// 判断系统字节序的函数 void checkEndianness() {unsigned int num 1;char *ptr (char*)&num;// 如果第一个字节存储的是最低有效字节&#xff0c;则…
阅读更多...
最新文章

Copyright @ 2022~2023