枫の个人主页

你不能改变过去，但你可以改变未来

算法/C++/数据结构/C

Hello，这里是小枫。C语言与数据结构和算法初阶两个板块都更新完毕，我们继续来学习C++的内容呀。C++是接近底层有比较经典的语言，因此学习起来注定枯燥无味，西游记大家都看过吧~，我希望能带着大家一起跨过九九八十一难，降伏各类难题，学会C++，我会尽我所能，以通俗易懂、幽默风趣的方式带给大家形象生动的知识，也希望大家遇到困难不退缩，遇到难题不放弃，学习师徒四人的精神！！！故此得名【C++游记】

 话不多说，让我们一起进入今天的学习吧~~~  

目录

一、AVL 树的概念

为什么 AVL 树高度差不要求为 0？

二、AVL 树的实现

2.1 AVL 树的结构

2.2 AVL 树的插入

2.2.1 插入过程概述

2.2.2 平衡因子更新规则

2.2.3 插入及平衡因子更新代码实现

2.3 旋转操作

2.3.1 旋转原则

2.3.2 右单旋

2.3.3 左单旋

2.3.4 左右双旋

2.3.5 右左双旋

2.4 AVL 树的查找

2.5 AVL 树平衡检测

 三、结语

一、AVL 树的概念

AVL 树是最先发明的自平衡二叉查找树，它要么是一颗空树，要么具备下列性质的二叉搜索树：左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。AVL 树是一种高度平衡的搜索二叉树，通过控制高度差来维持平衡。

AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 E. M. Landis（两位前苏联科学家），他们在 1962 年的论文《An algorithm for the organization of information》中发表了这一数据结构。

在 AVL 树实现中，我们引入平衡因子 (balance factor) 的概念。每个结点都有一个平衡因子，其值等于右子树的高度减去左子树的高度，因此任何结点的平衡因子只能是 0、1 或 - 1。平衡因子就像一个风向标，能方便我们观察和控制树是否平衡。

为什么 AVL 树高度差不要求为 0？

可能有人会疑惑，为什么 AVL 树要求高度差不超过 1 而不是 0 呢？0 不是更平衡吗？

其实并非不想这样设计，而是在某些情况下无法做到高度差为 0。例如，当树有 2 个结点、4 个结点等情况时，高度差最好就是 1，无法做到高度差为 0。

AVL 树的整体结点数量和分布与完全二叉树类似，高度可以控制在logN，因此增删查改的效率也可以控制在O(logN)，相比普通二叉搜索树有了本质的提升。

二、AVL 树的实现

2.1 AVL 树的结构

AVL 树的结点结构需要包含键值对、左右孩子指针、父节点指针以及平衡因子。具体定义如下：

template<class K, class V>
struct AVLTreeNode
{// 需要parent指针，后续更新平衡因子会用到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){}
};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 所在子树的高度是否变化决定了是否继续往上更新

更新停止条件：

  1. 若更新后 parent 的平衡因子等于 0（变化为 - 1->0 或 1->0）：说明更新前 parent 子树一边高一边低，新增结点插入在低的那边，插入后 parent 所在子树高度不变，不会影响 parent 的父亲结点的平衡因子，更新结束
  2. 若更新后 parent 的平衡因子等于 1 或 - 1（变化为 0->1 或 0->-1）：说明更新前 parent 子树两边一样高，插入后一边高一边低，子树符合平衡要求但高度增加了 1，会影响 parent 的父亲结点的平衡因子，需要继续向上更新
  3. 若更新后 parent 的平衡因子等于 2 或 - 2（变化为 1->2 或 - 1->-2）：说明更新前 parent 子树一边高一边低，新增结点插入在高的那边，破坏了平衡，需要旋转处理。旋转后子树高度恢复，不需要继续往上更新
  4. 更新到根结点，若根的平衡因子是 1 或 - 1 也停止
2.2.3 插入及平衡因子更新代码实现
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;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因子while (parent){// 更新当前parent的平衡因子if (cur == parent->_left)parent->_bf--;elseparent->_bf++;// 根据平衡因子判断后续操作if (parent->_bf == 0){// 平衡因子为0，子树高度不变，更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){// 平衡因子为1或-1，子树高度增加，继续向上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 平衡因子为2或-2，子树不平衡，需要旋转处理break;}else{// 平衡因子异常，程序出错assert(false);}}// 若需要旋转处理if (parent){if (parent->_bf == 2){if (parent->_right->_bf == 1){// 右右情况，左单旋RotateL(parent);}else if (parent->_right->_bf == -1){// 右左情况，右左双旋RotateRL(parent);}else{assert(false);}}else if (parent->_bf == -2){if (parent->_left->_bf == -1){// 左左情况，右单旋RotateR(parent);}else if (parent->_left->_bf == 1){// 左右情况，左右双旋RotateLR(parent);}else{assert(false);}}}return true;
}

2.3 旋转操作

2.3.1 旋转原则

旋转操作需要遵循两个原则：

  1. 保持搜索树的规则（即旋转后仍满足二叉搜索树的性质）
  2. 让旋转的树从不平衡变为平衡，同时降低旋转树的高度

旋转总共分为四种：左单旋、右单旋、左右双旋、右左双旋。

2.3.2 右单旋

右单旋适用于 "左左" 情况，即 parent 的平衡因子为 - 2，且其左孩子的平衡因子为 - 1。

旋转核心步骤：

  1. 将 parent 的左孩子（subL）的右子树（subLR）变为 parent 的左子树
  2. 将 parent 变为 subL 的右子树
  3. 更新相关结点的父指针
  4. 若 parent 是根结点，则更新根指针为 subL；否则将 subL 与 parent 的父结点连接
  5. 重置 parent 和 subL 的平衡因子为 0

右单旋代码实现：

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 将subL的右子树变为parent的左子树parent->_left = subLR;if (subLR)subLR->_parent = parent;// 保存parent的父节点Node* parentParent = parent->_parent;// 将parent变为subL的右子树subL->_right = parent;parent->_parent = subL;// 处理与parent的父节点的连接if (parentParent == nullptr){// parent是根节点_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;}// 重置平衡因子parent->_bf = subL->_bf = 0;
}
2.3.3 左单旋

左单旋适用于 "右右" 情况，即 parent 的平衡因子为 2，且其右孩子的平衡因子为 1。

旋转核心步骤：

  1. 将 parent 的右孩子（subR）的左子树（subRL）变为 parent 的右子树
  2. 将 parent 变为 subR 的左子树
  3. 更新相关结点的父指针
  4. 若 parent 是根结点，则更新根指针为 subR；否则将 subR 与 parent 的父结点连接
  5. 重置 parent 和 subR 的平衡因子为 0

左单旋代码实现：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;// 将subR的左子树变为parent的右子树parent->_right = subRL;if (subRL)subRL->_parent = parent;// 保存parent的父节点Node* parentParent = parent->_parent;// 将parent变为subR的左子树subR->_left = parent;parent->_parent = subR;// 处理与parent的父节点的连接if (parentParent == nullptr){// parent是根节点_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left)parentParent->_left = subR;elseparentParent->_right = subR;subR->_parent = parentParent;}// 重置平衡因子parent->_bf = subR->_bf = 0;
}
2.3.4 左右双旋

左右双旋适用于 "左右" 情况，即 parent 的平衡因子为 - 2，且其左孩子的平衡因子为 1。

旋转核心步骤：

  1. 先以 parent 的左孩子（subL）为旋转点进行左单旋
  2. 再以 parent 为旋转点进行右单旋
  3. 根据 subL 的右孩子（subLR）的平衡因子，调整相关结点的平衡因子

左右双旋代码实现：

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf; // 保存subLR的平衡因子，用于后续调整// 先对subL进行左单旋RotateL(parent->_left);// 再对parent进行右单旋RotateR(parent);// 根据subLR的平衡因子调整各节点的平衡因子if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{assert(false); // 平衡因子异常}
}
2.3.5 右左双旋

右左双旋适用于 "右左" 情况，即 parent 的平衡因子为 2，且其右孩子的平衡因子为 - 1。

旋转核心步骤：

  1. 先以 parent 的右孩子（subR）为旋转点进行右单旋
  2. 再以 parent 为旋转点进行左单旋
  3. 根据 subR 的左孩子（subRL）的平衡因子，调整相关结点的平衡因子

右左双旋代码实现：

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf; // 保存subRL的平衡因子，用于后续调整// 先对subR进行右单旋RotateR(parent->_right);// 再对parent进行左单旋RotateL(parent);// 根据subRL的平衡因子调整各节点的平衡因子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); // 平衡因子异常}
}

2.4 AVL 树的查找

AVL 树的查找操作与普通二叉搜索树的查找逻辑相同，由于 AVL 树的高度平衡特性，查找效率为O(logN)。

查找代码实现：

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.5 AVL 树平衡检测

为了验证实现的 AVL 树是否合格，我们可以通过检查左右子树高度差以及结点的平衡因子来进行验证。

平衡检测相关代码：

// 计算树的高度
int _Height(Node* root)
{if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}// 检测是否为平衡树
bool _IsBalanceTree(Node* root)
{// 空树也是AVL树if (nullptr == root)return true;// 计算当前节点的平衡因子（右子树高度 - 左子树高度）int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 检查平衡因子是否符合要求if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}// 检查记录的平衡因子是否与计算值一致if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// 递归检查左右子树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

测试代码：

void TestAVLTree1()
{
AVLTree<int, int> t;
// 常规的测试⽤例
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试⽤例
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert({ e, e });
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
}

 三、结语

今日C++到这里就结束啦，如果觉得文章还不错的话，可以三连支持一下。感兴趣的宝子们欢迎持续订阅小枫，小枫在这里谢谢宝子们啦~小枫の主页还有更多生动有趣的文章，欢迎宝子们去点评鸭~C++的学习很陡，时而巨难时而巨简单，希望宝子们和小枫一起坚持下去~你们的三连就是小枫的动力，感谢支持~

​

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/news/920853.shtml
繁体地址，请注明出处：http://hk.pswp.cn/news/920853.shtml
英文地址，请注明出处：http://en.pswp.cn/news/920853.shtml

如若内容造成侵权/违法违规/事实不符，请联系英文站点网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

音视频学习（六十二）：H264中的SEI

音视频学习（六十二）：H264中的SEI

什么是SEI? 在 H.264 视频编码标准中&#xff0c;补充增强信息&#xff08;Supplemental Enhancement Information&#xff0c;SEI&#xff09; 是一种特殊的 NAL&#xff08;网络抽象层&#xff09;单元。它不像序列参数集&#xff08;SPS&#xff09;或图像参数集&#xff0…
阅读更多...
docker run 后报错/bin/bash: /bin/bash: cannot execute binary file总结

docker run 后报错/bin/bash: /bin/bash: cannot execute binary file总结

以下方法来源于AI&#xff0c;个人仅验证了第三条便成功执行 1. 镜像与宿主机架构不匹配 比如&#xff1a; 你是 x86_64 的机器&#xff0c;但镜像是 ARM64 的&#xff08;或反之&#xff09;。在 PC 上拉了树莓派用的镜像。查看镜像架构 docker inspect <image_name> | …
阅读更多...
【Redisson 加锁源码解析】

【Redisson 加锁源码解析】

Redisson 源码解析 —— 分布式锁实现过程 在分布式系统中&#xff0c;分布式锁 是非常常见的需求&#xff0c;用来保证多个节点之间的互斥操作。Redisson 是 Redis 的一个 Java 客户端&#xff0c;它提供了对分布式锁的良好封装。本文将从源码角度剖析 Redisson 的分布式锁实现…
阅读更多...
uni-app支持单多选、搜索、查询、限制能否点击组件

uni-app支持单多选、搜索、查询、限制能否点击组件

<template><view class="multi-select-container" :class="{ single-select: !multiple, no-search: !searchable }"><!-- 当组件被禁用时，直接显示选中的内容 --><view class="disabled-display" v-if="disabled &a…
阅读更多...
TFT屏幕：STM32硬件SPI+DMA+队列自动传输

TFT屏幕：STM32硬件SPI+DMA+队列自动传输

看了网上的很多的SPIDMA的代码&#xff0c;感觉都有一些缺陷&#xff0c;就是基本都是需要有手动等待DMA完成的这个操作&#xff0c;我感觉这种等待操作在很大程度上浪费了时间&#xff0c;那么我加入的“队列”就是一种将等待时间利用起来的方法。原本的SPIDMA的操作逻辑如下图…
阅读更多...
AI操作系统语言模型设计 之1 基于意识的Face-Gate-Window的共轭路径的思维-认知-情感嵌套模型

AI操作系统语言模型设计 之1 基于意识的Face-Gate-Window的共轭路径的思维-认知-情感嵌套模型

摘要&#xff08;AI生成&#xff09;本文提出了一种创新的AI操作系统语言模型设计框架&#xff0c;将人类意识活动的分层结构映射到人工智能系统中。该模型包含三个嵌套层次&#xff1a;理性思维层&#xff08;Face层&#xff09;&#xff1a;采用双面胶隐喻&#xff08;A/B面&…
阅读更多...
疯狂星期四文案网第57天运营日记

疯狂星期四文案网第57天运营日记

网站运营第57天&#xff0c;点击观站&#xff1a; 疯狂星期四 crazy-thursday.com 全网最全的疯狂星期四文案网站 运营报告 今日访问量 今日搜索引擎收录情况
阅读更多...
SQLark：一款面向信创应用开发者的数据库开发和管理工具

SQLark：一款面向信创应用开发者的数据库开发和管理工具

SQLark 是一款面向信创应用开发者的数据库开发和管理工具&#xff0c;用于快速查询、创建和管理不同类型的数据库系统&#xff0c;现已支持达梦、Oracle、MySQL、PostgreSQL 数据库。 SQLark 提供了对多种数据库的连接支持&#xff0c;实现跨平台数据库管理的无缝切换&#xff…
阅读更多...
BigDecimal——解决Java浮点数值精度问题：快速入门与使用

BigDecimal——解决Java浮点数值精度问题：快速入门与使用

在Java开发中&#xff0c;涉及金额计算、科学计数或需要高精度数值处理时&#xff0c;你是否遇到过这样的困惑&#xff1f;用double计算0.1加0.2&#xff0c;结果竟不是0.3&#xff1b;用float存储商品价格&#xff0c;小数点后两位莫名多出几位乱码&#xff1b;甚至在金融系统…
阅读更多...
wpf之WrapPanel

wpf之WrapPanel

前言 WrapPanel类似winform中的FlowLayoutPanel&#xff0c;采用流式布局。 1、Orientation 该属性指定WrapPanel中子空间布局的方向&#xff0c;有水平和垂直方向两种 1&#xff09;Horizontal 水平方向 子元素Button按照水平方向排列&#xff0c;如果一行排满了自动换下一…
阅读更多...
Woody：开源Java应用性能诊断分析工具

Woody：开源Java应用性能诊断分析工具

核心价值 Woody是一款专注于Java应用性能问题诊断的工具&#xff0c;旨在帮助开发者 定位高GC频率问题&#xff0c;识别内存分配热点分析CPU使用率过高的代码路径追踪接口耗时瓶颈&#xff0c;定位内部操作耗时占比诊断锁竞争问题&#xff0c;支持精准优化针对特定业务接口/请…
阅读更多...
《山东棒球》板球比赛规则·棒球1号位

《山东棒球》板球比赛规则·棒球1号位

⚾ Baseball vs Cricket 终极科普&#xff5c;规则异同发展史全解&#xff01;Hey sports babes&#xff01;别再傻傻分不清棒球⚾和板球&#xff01;全网最清晰双运动对照指南来啦&#xff5e;⚾ 棒球 Baseball&#xff5c;美式激情风暴Core Goal核心目标击球员&#xff08;Ba…
阅读更多...
【游戏开发】Houdini相较于Blender在游戏开发上有什么优劣势？我该怎么选择开发工具？

【游戏开发】Houdini相较于Blender在游戏开发上有什么优劣势？我该怎么选择开发工具？

在游戏开发中&#xff0c;Houdini与Blender的选择需结合项目规模、技术需求和团队资源综合考量。以下是两者的核心优劣势对比及决策建议&#xff1a; 一、核心优劣势对比 Houdini的优势与局限 优势&#xff1a;程序化内容生成的统治力 Houdini的节点系统&#xff08;如VEX语言、…
阅读更多...
基于开源AI智能名片链动2+1模式S2B2C商城小程序的用户活跃度提升与价值挖掘策略研究

基于开源AI智能名片链动2+1模式S2B2C商城小程序的用户活跃度提升与价值挖掘策略研究

摘要&#xff1a;本文聚焦于在开源AI智能名片链动21模式S2B2C商城小程序环境下&#xff0c;探讨如何提高用户活跃度并挖掘用户价值。在用户留存的基础上&#xff0c;通过分析该特定模式与小程序的特点&#xff0c;提出一系列针对性的策略&#xff0c;旨在借助开源AI智能名片以及…
阅读更多...
《投资-41》- 自然=》生物=》人类社会=》商业=》金融=》股市=》投资，其层层叠加构建中内在的相似的规律和规则

《投资-41》- 自然=》生物=》人类社会=》商业=》金融=》股市=》投资，其层层叠加构建中内在的相似的规律和规则

从自然到投资的层层递进中&#xff0c;尽管各领域看似差异巨大&#xff0c;但内在遵循着相似的规律和规则。这些规律体现了“底层逻辑的普适性”&#xff0c;即不同系统在动态平衡、资源分配、信息传递和反馈调节等方面具有共性。以下是关键规律的解析&#xff1a;1. 能量流动与…
阅读更多...
VSCode中调试python脚本

VSCode中调试python脚本

VSCode中安装以下插件 ms-python.python&#xff1a;python调试ms-python.vscode-pylance&#xff1a;代码跳转&#xff08;非必要&#xff09; 配置launch.json 在当前工作区&#xff0c;按此路径.vscode\launch.json新建launch.json文件&#xff0c;并配置以下参数&#x…
阅读更多...
动作指令活体检测通过动态交互验证真实活人，保障安全

动作指令活体检测通过动态交互验证真实活人，保障安全

在当今社会&#xff0c;人脸识别技术已深入日常生活的方方面面&#xff0c;从手机解锁、移动支付到远程开户、门禁考勤&#xff0c;人脸识别技术已无处不在。然而&#xff0c;这项技术也面临着严峻的安全挑战&#xff1a;打印照片、播放视频、制作3D面具等简单的“欺骗手段”都…
阅读更多...
KingbaseES数据库：开发基础教程，从部署到安全的全方位实践

KingbaseES数据库：开发基础教程，从部署到安全的全方位实践

KingbaseES数据库&#xff1a;开发基础教程&#xff0c;从部署到安全的全方位实践 KingbaseES数据库&#xff1a;开发基础教程&#xff0c;从部署到安全的全方位实践&#xff0c;本文围绕 KingbaseES 数据库开发核心基础展开。先介绍三种部署模式&#xff0c;即单机、双机热备、…
阅读更多...
安装nodejs安装node.js安装教程（Windows Linux）

安装nodejs安装node.js安装教程（Windows Linux）

文章目录Linux**一、下载 Node.js**1. **访问官网**&#xff1a;2. **选择版本**&#xff1a;**二、安装 Node.js****方法 1&#xff1a;使用包管理器&#xff08;推荐&#xff09;****Ubuntu/Debian 系统**1. **更新包列表**&#xff1a;2. **安装 Node.js**&#xff1a;3. **…
阅读更多...
shell脚本函数介绍

shell脚本函数介绍

1. 函数 (Functions)定义与优势函数是可重复使用的功能模块优势&#xff1a;代码复用&#xff0c;直接调用解决问题分类内置函数&#xff1a;编程语言自带的函数&#xff08;如 print&#xff09;自定义函数&#xff1a;程序员自己编写的函数定义语法# 方式一 function 函数名(…
阅读更多...
最新文章

Copyright @ 2022~2023