深入理解AVL树：结构、旋转及C++实现

1. AVL树的概念

什么是AVL树？

AVL树是一种自平衡的二叉搜索树，其发明者是Adelson-Velsky和Landis，因此得名“AVL”。AVL树是首个自平衡二叉搜索树，通过对树的平衡因子进行控制，确保任何节点的左右子树高度差最多为1，从而保证树的高度为对数级别，即 O(log⁡N)O(\log N)O(logN)。

在AVL树中，插入、删除和查找的时间复杂度都可以保持在 O(log⁡N)O(\log N)O(logN)，这使得AVL树在需要频繁查询数据的应用场景中非常高效。

AVL树的平衡因子

每个节点有一个平衡因子（Balance Factor），定义如下：

  • 平衡因子 = 右子树高度 - 左子树高度
  • 对于任何节点，平衡因子的可能取值为 -1、0、1。

AVL树通过保持所有节点的平衡因子在上述范围内，确保了树的平衡。这个平衡性减少了树的高度，从而提高了数据查找效率。

为什么要平衡？

普通的二叉搜索树（BST）在最坏情况下会退化成链表。例如，按照递增顺序插入节点会使树的所有节点都集中在右边，导致高度等于节点数，查找复杂度为 O(N)O(N)O(N)。AVL树通过自动维护平衡性，避免了这种情况，确保所有操作的复杂度始终为对数级别。

2. AVL树的实现

2.1 AVL树的结构

AVL树的节点结构非常类似于普通的二叉树节点，不过增加了一个字段用于存储平衡因子。以下是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 factor）

    AVLTreeNode(const pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};

2.2 AVL树的插入

AVL树的插入操作和普通二叉搜索树的插入类似，但需要额外的步骤来确保树的平衡。如果插入新节点后某些节点失衡，我们需要通过旋转来恢复平衡。

插入步骤概述
  1. 按普通BST的规则插入：首先将节点按照二叉搜索树的规则插入。
  2. 更新平衡因子：从插入节点开始，向上遍历其祖先节点，更新每个节点的平衡因子。
  3. 检查并旋转平衡树：如果某节点的平衡因子变为2或-2，说明该节点失衡。此时需要通过旋转操作恢复平衡。
插入代码实现

以下是AVL树插入节点的代码实现：

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) {
        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) {
            // 失衡，需要进行旋转操作
            Balance(parent);
            break;
        } else {
            assert(false); // 不应存在其他情况
        }
    }

    return true;
}

2.3 旋转操作

当AVL树失去平衡时，通过旋转操作来恢复平衡。旋转的类型分为四种：右单旋、左单旋、左右双旋和右左双旋。每种旋转操作都有其适用场景和具体的实现。

旋转的类型
  1. 右单旋（Right Rotation）：用于修正左子树过高的情况。
  2. 左单旋（Left Rotation）：用于修正右子树过高的情况。
  4. 左右双旋（Left-Right Rotation）：用于修正节点插入在左子树的右侧，导致子树高度增加的情况。
  5. 右左双旋（Right-Left Rotation）：用于修正节点插入在右子树的左侧，导致子树高度增加的情况。
右单旋实现

右单旋用于修正某个节点的左子树过高的情况。以下是右单旋的代码：

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;
}
左单旋实现

左单旋用于修正某个节点的右子树过高的情况。以下是左单旋的代码实现：

void RotateL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    if (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;
}
左右双旋和右左双旋实现

当子树的高度增加发生在左右子树中的某一侧时，单次旋转无法恢复平衡，需要进行双次旋转。

  • 左右双旋（Left-Right Rotation）：首先对左子树进行左旋，再对祖先节点进行右旋。
  • 右左双旋（Right-Left Rotation）：首先对右子树进行右旋，再对祖先节点进行左旋。
void RotateLR(Node* parent) {
    RotateL(parent->_left);
    RotateR(parent);
}

void RotateRL(Node* parent) {
    RotateR(parent->_right);
    RotateL(parent);
}

2.4 AVL树的查找操作

AVL树的查找操作和普通二叉搜索树类似，由于AVL树保持平衡，查找操作的时间复杂度始终为 O(log⁡N)O(\log N)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树的平衡性检测旨在验证每个节点是否满足AVL树的平衡要求，即每个节点的左右子树高度差绝对值不超过1，同时保证每个节点的平衡因子正确反映左右子树的高度差。

为了验证AVL树的平衡性，检测的目标有两个：

  1. 验证左右子树的高度差是否满足AVL条件。
  2. 验证每个节点的平衡因子是否正确反映了其子树的高度差。

平衡性检测的挑战

在进行平衡性检测时，我们面临两个主要挑战：

  1. 递归遍历的深度与效率问题：对树的每个节点，我们需要递归计算其子树的高度，较高的递归深度可能导致性能下降。
  2. 同步验证平衡因子：在递归计算高度的过程中，我们需要同时验证每个节点的平衡因子是否正确。

平衡性检测的代码实现

以下是用于检测AVL树平衡性和正确性的代码：

int _Height(Node* root) {
    if (root == nullptr) return 0;

    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    return max(leftHeight, rightHeight) + 1;
}

bool _IsBalanceTree(Node* root) {
    if (root == nullptr) return true;

    // 计算左右子树的高度
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int diff = rightHeight - leftHeight;

    // 检查高度差是否符合AVL条件
    if (abs(diff) > 1) {
        cout << root->_kv.first << " 高度差异常: 左高=" << leftHeight << ", 右高=" << rightHeight << endl;
        return false;
    }

    // 检查平衡因子是否正确
    if (root->_bf != diff) {
        cout << root->_kv.first << " 平衡因子异常: 期望=" << diff << ", 实际=" << root->_bf << endl;
        return false;
    }

    // 递归检测左右子树是否平衡
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
代码说明
  1. 高度计算：_Height 函数用于计算节点的高度，递归遍历每个节点的左右子树，返回最大的高度加1。
  2. 平衡性验证：_IsBalanceTree 函数用于检测树的平衡性。它首先计算每个节点的左右子树高度差，然后检查其平衡因子是否符合AVL树的定义。
  3. 详细输出：为了帮助调试，函数在检测到异常时输出详细的信息，包括节点的键值、高度差和不匹配的平衡因子值。

平衡性检测的改进：优化高度计算

在上述实现中，_Height 函数被重复调用多次，可能会导致效率低下。特别是在平衡性检测过程中，每次都要重新递归计算子树的高度。我们可以通过以下优化来提升效率。

同时计算高度与检测平衡性

我们可以通过一次递归同时计算高度和检测平衡性，避免重复的高度计算。以下是改进后的代码：

// 新的平衡检测函数，返回子树的高度并同时检测是否平衡
int _CheckBalance(Node* root, bool& isBalanced) {
    if (root == nullptr) return 0;

    int leftHeight = _CheckBalance(root->_left, isBalanced);
    int rightHeight = _CheckBalance(root->_right, isBalanced);

    // 如果在递归过程中已经发现不平衡，直接返回
    if (!isBalanced) return 0;

    // 计算当前节点的高度差
    int diff = rightHeight - leftHeight;

    // 检查高度差是否符合AVL条件
    if (abs(diff) > 1) {
        cout << "节点 " << root->_kv.first << " 高度差异常: 左高=" << leftHeight << ", 右高=" << rightHeight << endl;
        isBalanced = false;
    }

    // 检查平衡因子是否正确
    if (root->_bf != diff) {
        cout << "节点 " << root->_kv.first << " 平衡因子异常: 期望=" << diff << ", 实际=" << root->_bf << endl;
        isBalanced = false;
    }

    // 返回子树的高度
    return max(leftHeight, rightHeight) + 1;
}

// 检测整棵树是否平衡的入口函数
bool IsBalanceTree() {
    bool isBalanced = true;
    _CheckBalance(_root, isBalanced);
    return isBalanced;
}
代码改进点

  1. 高度计算与平衡检测结合：

    • 在新的实现中，_CheckBalance 函数同时执行高度计算和平衡性检测。
    • 递归调用返回子树的高度，同时检查每个节点的平衡性，从而减少了重复的递归操作。

  2. 标志位：

    • 通过 bool& isBalanced 参数作为标志位，当发现树中有不平衡的节点时，将其设为 false，并立即终止后续的递归。
    • 这样可以避免不必要的计算，提高检测的整体效率。

  3. 减少重复计算：

    • 与之前的版本相比，新的实现避免了重复的高度计算，每个节点只需一次遍历即可完成高度计算和平衡性检测。

进阶：检查树的平衡因子及其更新的正确性

除了检测平衡性之外，还可以扩展检测模块，进一步确保AVL树中的每个节点的平衡因子在插入和旋转操作之后都得到了正确更新。以下是检测平衡因子的代码。

验证每个节点的平衡因子

在进行插入、删除等操作后，平衡因子必须保持正确更新。我们可以通过递归遍历整棵树来验证每个节点的平衡因子是否准确反映其子树的高度差。

bool ValidateBalanceFactors(Node* root) {
    if (root == nullptr) return true;

    // 递归获取左右子树高度
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int expectedBF = rightHeight - leftHeight;

    // 检查平衡因子是否正确
    if (root->_bf != expectedBF) {
        cout << "节点 " << root->_kv.first << " 的平衡因子不正确。应为 " << expectedBF << "，实际为 " << root->_bf << endl;
        return false;
    }

    // 递归验证左右子树的平衡因子
    return ValidateBalanceFactors(root->_left) && ValidateBalanceFactors(root->_right);
}
代码说明
  • ValidateBalanceFactors 函数遍历整个树，检查每个节点的平衡因子是否与其左右子树的高度差匹配。
  • 这种检测可以在每次插入、删除或旋转之后调用，以确保树在操作后没有出现错误的平衡因子。
  • 如果发现平衡因子不正确，程序会输出详细的错误信息，包括节点的键值、应有的平衡因子和当前存储的平衡因子。

平衡性检测的应用场景

  • 单元测试：在开发AVL树时，可以在每次插入、删除或旋转操作后调用平衡性检测函数，作为单元测试的一部分。
  • 调试与验证：通过详细的错误信息输出，开发者可以快速定位到问题节点，从而帮助调试和验证代码的正确性。
  • 性能优化：平衡性检测不仅可以帮助验证算法的正确性，还可以用于评估在不同数据分布和操作顺序下，AVL树的性能表现是否达到了预期。

3. AVL树的应用场景及优势

AVL树适合应用于需要高效查找的场景中，例如数据库中的索引结构、缓存系统中的快速查找等。相比于普通的二叉搜索树，AVL树保证了每次操作的时间复杂度为 O(log⁡N)O(\log N)O(logN)，特别适合频繁插入和删除的应用。

4. C++实现的完整代码示例

以下是一个AVL树完整的C++实现代码示例，结合了插入、旋转、查找和检测的实现。

template<class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;

public:
    bool Insert(const pair<K, V>& kv);
    Node* Find(const K& key);
    void InOrder() const;
    bool IsBalanceTree();

private:
    Node* _root = nullptr;

    void RotateR(Node* parent);
    void RotateL(Node* parent);
    void RotateLR(Node* parent);
    void RotateRL(Node* parent);
};

在实际编程中，使用AVL树可以保证数据的有序性，同时保证在最坏情况下依然具有高效的时间复杂度，非常适合需要高频率动态数据维护的场景。

5. 结论

AVL树是一种经典的自平衡二叉搜索树，通过引入平衡因子和旋转操作，保持了树的平衡性，确保了插入、删除和查找操作的高效性。通过学习AVL树，我们可以深入理解数据结构的自平衡机制，以及如何在二叉树中保持最优的性能。

希望通过这篇博客，大家对AVL树的概念、实现和用途有更深的了解。如果你有任何疑问或者想了解更多相关内容，欢迎随时交流。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/928695.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

电脑插入耳机和音响，只显示一个播放设备

电脑插入耳机和音响，只显示一个播放设备

1. 控制面板-硬件和声音-Realtek高清音频-扬声器-设备高级设置-播放设备里选择使用前部和后部输出设备同时播放两种不同的音频流 在声音设置中就可以看到耳机播放选项
阅读更多...
网络练级宝典-＞ UDP传输层协议

网络练级宝典-＞ UDP传输层协议

目录 传输层 端口号 端口号和进程的关系 UDP协议 UDP协议格式 UDP数据封装&#xff1a; UDP数据分用&#xff1a; 面向数据报 UDP的缓冲区 UDP的缺点 基于UDP的应用层协议 传输层 端口号 我们知道端口号对应的其实就是一个进程的pid&#xff0c;在操作系统中二者的…
阅读更多...
基于飞腾S2500处理器的全国产加固服务器

基于飞腾S2500处理器的全国产加固服务器

近日&#xff0c;西安康德航测电子科技有限公司凭借其深厚的行业底蕴和创新精神&#xff0c;正式推出了基于飞腾S2500处理器的全国产加固服务器。这一产品的问世&#xff0c;不仅标志着我国在信息技术领域的自立自强迈出了坚实的一步&#xff0c;更以其卓越的性能、坚固的设计和…
阅读更多...
移植NIOS10.1工程，NIOS10.1路径修改

移植NIOS10.1工程，NIOS10.1路径修改

移植NIOS10.1工程&#xff0c;NIOS10.1路径修改 因工程的需要&#xff0c;使用的NIOS10.1&#xff0c;比较老&#xff0c;这个版本的路径是使用的绝对路径&#xff0c;导致移植工程市回报路径的错误&#xff0c;在13.1之后改为了相对路径&#xff0c;不存在这个问题。 需要修…
阅读更多...
`pnpm` 不是内部或外部命令,也不是可运行的程序或批处理文件（问题已解决，2024/12/3

`pnpm` 不是内部或外部命令,也不是可运行的程序或批处理文件（问题已解决，2024/12/3

主打一个有用 只需要加一个环境变量 直接安装NodeJS的情况使用NVM安装NodeJS的情况 本篇博客主要针对第二种情况&#xff0c;第一种也可参考做法&#xff0c;当然眨眼睛建议都换成第二种 默认情况下的解决方法&#xff1a;⭐⭐⭐ 先找到node的位置&#xff0c;默认文件夹名字…
阅读更多...
FFmpeg：强大的音视频处理工具指南

FFmpeg：强大的音视频处理工具指南

FFmpeg&#xff1a;强大的音视频处理工具指南 1. FFmpeg简介2. 核心特性2.1 基础功能2.2 支持的格式和编解码器 3. 主要组件3.1 命令行工具3.2 开发库 4. 最新发展5. 安装指南5.1 Windows系统安装5.1.1 直接下载可执行文件5.1.2 使用包管理器安装 5.2 Linux系统安装5.2.1 Ubunt…
阅读更多...
openEuler卸载 rpm安装的 redis

openEuler卸载 rpm安装的 redis

停止 Redis 服务 sudo systemctl stop redis禁用 Redis 服务 sudo systemctl disable redis 卸载 Redis 软件包 sudo yum remove redis查找并删除 Redis 的残留文件 find / -name red*删除 Redis 配置文件 删除 Redis 数据文件 sudo rm -rf /var/lib/redis检查 Redis 是否…
阅读更多...
1.kettle保姆级安装教程

1.kettle保姆级安装教程

1 配置java 1.1 安装jdk 1.双击软件&#xff08;kettle要用jdk 1.8版本&#xff09; 2.选择安装路径地址&#xff0c;可以选择默认。要记好安装路径地址&#xff0c;等会要用 1.2 配置环境变量 1.右击计算机&#xff0c;属性 2.高级系统设置 3.环境变量 4.系统变量 – 新建 …
阅读更多...
【Elasticsearch】实现分布式系统日志高效追踪

【Elasticsearch】实现分布式系统日志高效追踪

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…
阅读更多...
K8s 十年回顾（Ten Year Review of K8s）

K8s 十年回顾（Ten Year Review of K8s）

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。Kubernetes 十年回顾 起源与…
阅读更多...
大数据新视界 -- Hive 元数据管理：核心元数据的深度解析（上）（27 / 30）

大数据新视界 -- Hive 元数据管理：核心元数据的深度解析（上）（27 / 30）

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…
阅读更多...
Lambda表达式提取字段名

Lambda表达式提取字段名

文章目录 前言例子原理writeReplace反序列化对象缓存元数据 写一个工具 前言 实体类:方法这种方式获取字段名&#xff0c;摒弃了字符串拼接方式&#xff0c;避免拼接出现的问题&#xff0c;提高框架维护性和可修改性。 例子 引入Mybatis-Plus <dependency><groupId…
阅读更多...
Dataset用load_dataset读图片和对应的caption的一个坑

Dataset用load_dataset读图片和对应的caption的一个坑

代码&#xff1a; data_files {} if args.train_data_dir is not None:data_files["train"] os.path.join(args.train_data_dir, "**")dataset load_dataset("imagefolder",data_filesdata_files,cache_dirargs.cache_dir,) 数据&#xff1…
阅读更多...
git查看本地库对应的远端库的地址

git查看本地库对应的远端库的地址

git查看本地库对应的远端库的地址 git remote -v 如果想要查看特定的远端库的url地址&#xff0c;可以使用如下命令&#xff0c;其中origin是默认的远端库的名称&#xff0c;可以使用其他远端库的名称 get remote get-url origin
阅读更多...
传统PID和模糊控制在matlab仿真效果的对比

传统PID和模糊控制在matlab仿真效果的对比

通过学习汇总和复现&#xff0c;利用matlab和simulink进行对传统PID和添加了模糊控制器的仿真效果进行对比&#xff1a; 上图中红色信号为传统PID仿真信号&#xff0c;比直接作用到对象的信号拟合度好很多PID的积分和比例的作用&#xff0c;直接作用到对象相当于只通过了二阶函…
阅读更多...
网络编程（JavaEE）

网络编程（JavaEE）

前言&#xff1a; 熟悉了网络的基本概念之后&#xff0c;接下来就需要针对网络进行一系列的编程&#xff0c;其中可能涉及到新的一些编程操作&#xff0c;需要我们进一步探索&#xff01; 网络编程套接字&#xff1a; 套接字其实是socket的翻译。 操作系统给应用程序(传输层给…
阅读更多...
算法第一弹-----双指针

算法第一弹-----双指针

目录 1.移动零 2.复写零 3.快乐数 4.盛水最多的容器 5.有效三角形的个数 6.查找总价值为目标值的两个商品 7.三数之和 8.四数之和 双指针通常是指在解决问题时&#xff0c;同时使用两个指针&#xff08;变量&#xff0c;常用来指向数组、链表等数据结构中的元素位置&am…
阅读更多...
Linux-虚拟环境

Linux-虚拟环境

文章目录 一. 虚拟机二. 虚拟化软件三. VMware WorkStation四. 安装CentOS操作系统五. 在VMware中导入CentOS虚拟机六. 远程连接Linux系统1. Finalshell安装2. 虚拟机网络配置3. 连接到Linux系统 七. 虚拟机快照 一. 虚拟机 借助虚拟化技术&#xff0c;我们可以在系统中&#…
阅读更多...
分而治之—利用决策树和规则进行分类

分而治之—利用决策树和规则进行分类

当在几个具有不同薪资和福利水平的工作机会之间做出选择时&#xff0c;很多人会从列出利弊开始&#xff0c;并基于简单的规则来排除选项。比如&#xff0c;“如果我上下班的时间超过1小时&#xff0c;那么我会不高兴”。通过这种方式&#xff0c;通过这种方式&#xff0c;预测一…
阅读更多...
【spring mvc】全局处理请求体和响应体

【spring mvc】全局处理请求体和响应体

目录 说明实现效果逻辑图 实现步骤创建公共处理的请求和响应的类api接口测试前端请求响应结果 扩展Response响应格式实体ResponseCode 响应状态码RSA工具类 RequestBodyAdvice 介绍使用场景 ResponseBodyAdvice 介绍使用场景 说明 由于项目中需要进行加密传输数据提高项目安全…
阅读更多...
最新文章

Copyright @ 2022~2023