当前位置: 首页 > news >正文

C++ AVL树

1.AVL树的概念

  为什么需要产生AVL树,由于二叉树中在某种特殊情况下会出现“一边高”的形状,这对于查找是极为不利的,所以就产生了AVL树。AVL树一棵空树或者具备下列性质的二叉搜索树:左右子树都是AVL树,且左右子树高度差绝对值不超过1。AVL树是一颗高度平衡的二叉搜索树,通过控制高度差来控制平衡。

  AVL树实现需要引用一个平衡因子的概念,每个节点都有一个平衡因子, 任何节点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度,也就是说任何结点的平衡因⼦等于0/1/-1,保证了左右子树高度差绝对值不超过1。

  AVL树整体结点数量和分布和完全⼆叉树类似,⾼度可以控制在 ,那么增删查改的效率也可以控制在O(logN)。

2.AVL树的实现

2.1AVL树的结构

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;AVLTreenode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<class K, class V>
class AVLTree
{typedef AVLTreenode<K, V> Node;
public:private:Node* _root = nullptr;
};

2.2 AVL树的插⼊

2.2.1 AVL树插⼊⼀个值的⼤概过程

1.插入值按照二叉树的规则进行插入

2.新增节点以后只会影响祖先的节点,也就是可能会影响部分祖先的节点,最坏情况下会影响到根节点。

3. 更新平衡因⼦过程中没有出现问题,则插⼊结束。

4. 更新平衡因⼦过程中出现不平衡,对不平衡⼦树旋转,旋转后本质调平衡的同时,本质降低了⼦树 的⾼度,不会再影响上⼀层,所以插⼊结束。

2.2.2

平衡因⼦更新

更新原则:

• 平衡因⼦=右⼦树⾼度-左⼦树⾼度

• 只有⼦树⾼度变化才会影响当前结点平衡因⼦。

• 插⼊结点,会增加⾼度,所以新增结点在parent的右⼦树,parent的平衡因⼦++,新增结点在 parent的左⼦树,parent平衡因⼦--

• parent所在⼦树的⾼度是否变化决定了是否会继续往上更新

更新停⽌条件:

• 更新后parent的平衡因⼦等于0,更新中parent的平衡因⼦变化为-1->0或者1->0,说明更新前 parent⼦树⼀边⾼⼀边低,新增的结点插⼊在低的那边,插⼊后parent所在的⼦树⾼度不变,不会 影响parent的⽗亲结点的平衡因⼦,更新结束。

• 更新后parent的平衡因⼦等于1或-1,更新前更新中parent的平衡因⼦变化为0->1或者0->-1,说 明更新前parent⼦树两边⼀样⾼,新增的插⼊结点后,parent所在的⼦树⼀边⾼⼀边低,parent所 在的⼦树符合平衡要求,但是⾼度增加了1,会影响parent的⽗亲结点的平衡因⼦,所以要继续向 上更新。

• 更新后parent的平衡因⼦等于2或-2,更新前更新中parent的平衡因⼦变化为1->2或者-1->-2,说 明更新前parent⼦树⼀边⾼⼀边低,新增的插⼊结点在⾼的那边,parent所在的⼦树⾼的那边更⾼ 了,破坏了平衡,parent所在的⼦树不符合平衡要求,需要旋转处理,旋转的⽬标有两个:1、把 parent⼦树旋转平衡。2、降低parent⼦树的⾼度,恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新,插⼊结束。

如图更新到节点十时,平衡因子为2,10所在子树已经不平衡了,需要旋转处理。

2.3旋转

 旋转的原则
1. 保持搜索树的规则
2. 让旋转的树从不满⾜变平衡,其次降低旋转树的⾼度
旋转总共分为四种,左单旋/右单旋/左右双旋/右左双旋。
void RotateL(Node* parent)//左单选{Node* subR = parent->_right;Node* subRL = subR->_left;Node* Pparent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (Pparent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == Pparent->_left){Pparent->_left = subR;}else{Pparent->_right = subR;}subR->_parent = Pparent;}parent->_bf = subR->_bf = 0;}void RotateR(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* Pparent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (Pparent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == Pparent->_left){Pparent->_left = subL;}else{Pparent->_right = subL;}subL->_parent = Pparent;}parent->_bf = subL->_bf = 0;}void RotateRL(Node* parent)//右左双旋{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 0)//当subRL为新增{subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 1)//当subRL右节点为新增{subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == -1)//当subRL左节点为新增{subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}elseassert(false);}void RotateLR(Node* parent)//左右双旋{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateR(subL);RotateL(parent);if (bf == 0)//当subLR为新增{subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else if (bf == -1)//当subLR左节点为新增{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1)//当subLR右节点为新增{subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}elseassert(false);}bool insert(pair<K, V>kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent) {if (cur == parent->_left){parent->_bf--;}else{parent->_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)//同号需要单旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//异号需要双旋{RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}elseassert(false);}}}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}

2.4 AVL树的查找

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

测试代码

AVLTree<int, int> t;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.insert({ e,e });}t.InOrder();

http://www.xdnf.cn/news/9541.html

相关文章:

  • HAL库通过FATFS和SDIO+DMA写入SD卡数据错误
  • 2025MathorcupD题 短途运输货量预测及车辆调度问题 保姆级教程讲解|模型讲解
  • L2-006 树的遍历
  • DHTMLX宣布推出支持 Redux、TypeScript 和 MUI 的 React Gantt甘特图控件
  • redis利用备忘录
  • Jsp技术入门指南【五】详细讲解jsp结构页面
  • 【含文档+PPT+源码】基于Python爬虫二手房价格预测与可视化系统的设计与实现
  • 论文阅读:2024 arxiv AI Safety in Generative AI Large Language Models: A Survey
  • 自然语言处理入门7——注意力机制
  • 数据结构——顺序表(C语言实现)
  • [250418] 智谱 AI 发布新一代模型,同时推出新域名 Z.ai
  • yocto编译使用共享缓存
  • IntelliSense 已完成初始化,但在尝试加载文档时出错
  • 前端单元测试实战:如何开始?
  • Vue2+Vue3 130~180集学习笔记
  • Google Colab测试部署Qwen大模型,实现PDF转MD场景OCR 识别(支持单机环境)
  • 迭代器模式:统一不同数据结构的遍历方式
  • ctf.show—Web(1-10)详细通关教程
  • 2025年行业AI Agent选型专业指南
  • RT-Thread RTThread studio 初使用
  • 零基础玩转AI数学建模:从理论到实战
  • LINUX学习——守护进程的含义及编程实现
  • Function Calling的机制 (含示例)
  • Sqlite3交叉编译全过程
  • 2025妈妈杯数学建模B题完整分析论文
  • 游戏引擎学习第233天
  • 【go】什么是Go语言中的GC,作用是什么?调优,sync.Pool优化,逃逸分析演示
  • 深度学习神经网络全连接笔记day1
  • 2025年03月中国电子学会青少年软件编程(Python)等级考试试卷(四级)真题
  • python flask 项目部署