【C++篇】树影摇曳，旋转无声：探寻AVL树的平衡之道

Ne0inhk

— 17 min read
【C++篇】树影摇曳，旋转无声：探寻AVL树的平衡之道

文章目录

从结构到操作：手撕AVL树的实现

💬 欢迎讨论：如果你在阅读过程中有任何疑问或想要进一步探讨的内容，欢迎在评论区留言！我们一起学习、一起成长。

👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏并分享给更多的朋友！

🚀 逐步实现AVL树：本篇文章将带你一步一步实现一个自平衡的二叉查找树——AVL树，从最基本的节点结构开始，逐步实现插入、查找等操作，并确保每个步骤都详细讲解。

一、AVL树介绍

1.1 什么是AVL树

AVL树是一种自平衡的二叉查找树（BST），由G.M. Adelson-Velsky和E.M. Landis于1962年提出。AVL树的核心特点是它保证树的每个节点的左右子树的高度差（平衡因子）不超过1，从而保证了AVL树在插入、删除和查找操作时的时间复杂度始终为O(log N)。

1.2 平衡因子的定义

每个节点都有一个平衡因子（_bf），它表示节点左子树的高度减去右子树的高度：
平衡因子 = 左子树的高度 − 右子树的高度 \text{平衡因子} = \text{左子树的高度} - \text{右子树的高度} 平衡因子=左子树的高度−右子树的高度

  • 如果平衡因子为 0，表示左右子树的高度相等。
  • 如果平衡因子为 1，表示左子树比右子树高1。
  • 如果平衡因子为 -1，表示右子树比左子树高1。

1.3 平衡的意义

AVL树的自平衡特性确保了其查询、插入和删除操作的最坏时间复杂度为O(log N)，避免了普通二叉查找树的退化（比如变成链表）。因此，AVL树非常适用于需要频繁插入和删除操作的场景。

1.4 AVL树的操作

AVL树的主要操作有：

  • 插入操作：在树中插入节点，并在插入后调整平衡因子。如果平衡因子为2或-2，执行旋转操作恢复平衡。
  • 删除操作：删除节点，并且在删除节点后，可能需要调整树的结构以保持平衡。由于AVL树的删除操作涉及复杂的旋转和调整，因此在本文中我们不会详细讲解该操作。如果你希望深入了解，可以参考《算法导论》中的相关章节来获取详细内容。
  • 查找操作：通过比较节点值来查找特定的元素。
  • 旋转操作：当树失衡时，使用旋转来恢复平衡，常见的旋转有左旋、右旋、左右旋和右左旋。

二、AVL树的节点结构

在实现AVL树之前，首先要定义节点结构。每个节点存储以下信息：

  • 键值对（_kv）：存储数据（pair<K, V>）。
  • 左右子树指针（_left, _right）：指向左右子树。
  • 父节点指针（_parent）：指向父节点。
  • 平衡因子（_bf）：用于标识该节点的左右子树的高度差。

2.1 节点结构的定义：

template<classK,classV>structAVLTreeNode{ pair<K, V> _kv;// 存储键值对 AVLTreeNode<K, V>* _left;// 左子树指针 AVLTreeNode<K, V>* _right;// 右子树指针 AVLTreeNode<K, V>* _parent;// 父节点指针int _bf;// 平衡因子// 构造函数AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};

三、插入操作

3.1 插入操作概述

AVL树的插入操作包括三步：

  1. 按二叉查找树规则插入节点；
  2. 更新每个节点的平衡因子；
  3. 如果需要，进行旋转操作来恢复树的平衡。
boolInsert(const pair<K, V>& kv);

3.2 步骤1：按二叉查找树规则插入节点

在插入节点时，我们根据值的大小，递归地找到插入位置，并在该位置插入新节点：

if(_root ==nullptr){ _root =newNode(kv);// 如果树为空，直接插入根节点returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;// 在右子树中查找插入位置}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;// 在左子树中查找插入位置}else{returnfalse;// 如果节点已存在，不插入}} cur =newNode(kv);if(parent->_kv.first < kv.first){ parent->_right = cur;}else{ parent->_left = cur;}//更新插入节点的_parent cur->_parent = parent;

3.3 步骤2：更新平衡因子

插入节点后，我们从新插入的节点开始，逐步更新路径上每个节点的平衡因子。插入时会对父节点的平衡因子进行调整：

while(parent){if(cur == parent->_left){ parent->_bf++;}else{ parent->_bf--;}if(parent->_bf ==0){break;}elseif(parent->_bf ==1|| parent->_bf ==-1){ cur = parent; parent = cur->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2){//旋转if(parent->_bf ==2&& cur->_bf ==1){RotateR(parent);}elseif(parent->_bf ==-2&& cur->_bf ==-1){RotateL(parent);}elseif(parent->_bf ==2&& cur->_bf ==-1){RotateLR(parent);}elseif(parent->_bf ==-2&& cur->_bf ==1){RotateRL(parent);}elseassert(false);break;}else{assert(false);}}returntrue;

3.4 步骤3：旋转操作详解

如果某个节点的平衡因子为2或-2，表示该节点不平衡。我们需要通过旋转操作来恢复平衡。旋转操作有四种：

  1. 右单旋（RotateR）
  2. 左单旋（RotateL）
  3. 左右双旋（RotateLR）
  4. 右左双旋（RotateRL）
3.4.1 右单旋

右单旋适用于当左子树较高时，执行旋转操作来恢复平衡。

在这里插入图片描述


在这里插入图片描述
voidRotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppNode = parent->_parent; parent->_left = subLR;if(subLR){ subLR->_parent = parent;} subL->_right = parent; parent->_parent = subL;if(parent == _root){ subL->_parent =nullptr; _root = subL;}else{ subL->_parent = ppNode;if(parent == ppNode->_right) ppNode->_right = subL;else ppNode->_left = subL;} parent->_bf =0; subL->_bf =0;}
3.4.2 左单旋

左单旋适用于当右子树较高时，执行旋转操作来恢复平衡。

在这里插入图片描述


在这里插入图片描述
voidRotateL(Node* parent){ Node* subR = parent->_right; Node* ppNode = parent->_parent; Node* subRL = subR->_left; parent->_right = subRL; parent->_parent = subR;if(subRL){ subRL->_parent = parent;} subR->_left = parent;if(parent == _root){ _root = subR; subR->_parent =nullptr;}else{ subR->_parent = ppNode;if(parent == ppNode->_right) ppNode->_right = subR;else ppNode->_left = subR;} parent->_bf =0; subR->_bf =0;}
3.4.3 左右双旋
在这里插入图片描述


在这里插入图片描述

当左子树的右子树较高时，首先进行左旋，再进行右旋，恢复平衡。

voidRotateLR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);// 左旋RotateR(parent);// 右旋if(bf ==1){ subLR->_bf =0; subL->_bf =0; parent->_bf =-1;}elseif(bf ==-1){ subLR->_bf =0; subL->_bf =1; parent->_bf =0;}elseif(bf ==0){ subL->_bf = subLR->_bf = parent->_bf =0;}}
在这里插入图片描述
3.4.4 右左双旋

当右子树的左子树较高时，首先进行右旋，再进行左旋，恢复平衡。

在这里插入图片描述


在这里插入图片描述
voidRotateRL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);// 右旋RotateL(parent);// 左旋if(bf ==0){ parent->_bf = subR->_bf = subRL->_bf =0;}elseif(bf ==1){ subRL->_bf =0; parent->_bf =0; subR->_bf =-1;}elseif(bf ==-1){ subRL->_bf =0; parent->_bf =1; subR->_bf =0;}}
在这里插入图片描述

总结：找失衡原因，决定如何旋转

  • 左子树的左子树高：进行R
  • 右子树的右子树高：进行L
  • 左子树的右子树高：进行LR
  • 右子树的左子树高：进行RL

四、其他操作

4.1 查找操作 (Find)

查找操作与普通的二叉查找树类似。通过不断比较当前节点的键值和目标值，沿树的路径查找目标节点。

Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key) cur = cur->_right;// 目标键值比当前节点大，往右子树查找elseif(cur->_kv.first > key) cur = cur->_left;// 目标键值比当前节点小，往左子树查找elsereturn cur;// 找到目标节点，返回该节点}returnnullptr;// 如果没有找到，返回空}

该方法的时间复杂度为 O(log N)，因为AVL树是平衡的，树的高度是对数级别的。

4.2 计算树的高度 (Height)

树的高度指的是从根节点到最远叶子节点的最长路径上的边数。AVL树的高度是平衡的，计算时我们需要递归地计算左右子树的高度并返回较大的一个。

intHeight(){return_Height(_root);// 从根节点开始计算树的高度}int_Height(Node* root){if(root ==nullptr)return0;// 空树的高度为0int leftHeight =_Height(root->_left);// 递归计算左子树的高度int rightHeight =_Height(root->_right);// 递归计算右子树的高度return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;// 返回较大值，并加1}

该方法的时间复杂度为 O(N)，其中N为节点总数。虽然AVL树是平衡的，但在计算高度时需要遍历整个树。

4.3 计算节点数量 (Size)

节点数量是树中所有节点的总数。通过递归遍历树，计算左右子树的节点数量，并加上当前节点。

intSize(){return_Size(_root);// 从根节点开始计算树的大小}int_Size(Node* root){if(root ==nullptr)return0;// 空树节点数量为0return_Size(root->_left)+_Size(root->_right)+1;// 左右子树的节点数量加1}

该方法的时间复杂度为 O(N)，需要遍历整个树来计算节点总数。

4.4 树是否平衡 (IsBalanceTree)

为了验证AVL树的平衡性，我们需要检查每个节点的平衡因子，并确保它们的绝对值不超过1。如果树的任意节点的平衡因子大于1或小于-1，那么树就不平衡。

bool_IsBalanceTree(Node* root){if(root ==nullptr)returntrue;// 空树是平衡的int leftHeight =_Height(root->_left);// 左子树高度int rightHeight =_Height(root->_right);// 右子树高度int diff = leftHeight - rightHeight;// 计算平衡因子if(abs(diff)>=2){ cout << root->_kv.first <<"高度差异常"<< endl;returnfalse;// 如果高度差大于等于2，树不平衡}if(root->_bf != diff){ cout << root->_kv.first <<"平衡因子异常"<< endl;returnfalse;// 如果平衡因子与实际高度差不符，树不平衡}// 递归检查左右子树是否平衡return_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}

该方法的时间复杂度为 O(N)，需要递归遍历整个树并计算每个节点的平衡因子。

五、性能分析与测试

5.1 性能分析

AVL树通过保持平衡，保证了插入、查找和删除操作的时间复杂度都为O(logN)，相比于普通的二叉查找树，AVL树避免了退化成链表的情况，极大提高了性能。

5.2 测试代码

下面是两个测试代码，用于验证AVL树的插入和查找操作。

// 测试代码voidTestAVLTree1(){ 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 }); cout <<"Insert:"<< e <<"->"; cout << t.IsBalanceTree()<< endl;} t.InOrder(); cout << t.IsBalanceTree()<< endl;}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等voidTestAVLTree2(){constint N =1000000; vector<int> v; v.reserve(N);srand((unsignedint)time(0));for(int i =0; i < N; i++){ v.push_back(rand()+ i);} size_t begin2 =clock(); AVLTree<int,int> t;for(auto e : v){ t.Insert(make_pair(e, e));} size_t end2 =clock(); cout << t.IsBalanceTree()<< endl; cout <<"Insert:"<< end2 - begin2 << endl; cout <<"Height:"<< t.Height()<< endl; cout <<"Size:"<< t.Size()<< endl; size_t begin1 =clock();// 确定在的值/*for (auto e : v) { t.Find(e); }*/// 随机值for(int i =0; i < N; i++){ t.Find((rand()+ i));} size_t end1 =clock(); cout <<"Find:"<< end1 - begin1 << endl;}

六、全部代码

AVLTree.h

#pragmaoncetemplate<classK,classV>structAVLTreeNode{ pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent;int _bf;AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<classK,classV>classAVLTree{typedef AVLTreeNode<K, V> Node;public:boolInsert(const pair<K, V>& kv){if(_root ==nullptr){ _root =newNode(kv);returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(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;}elseif(parent->_bf ==1|| parent->_bf ==-1){ cur = parent; parent = cur->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2){//旋转if(parent->_bf ==2&& cur->_bf ==1){RotateR(parent);}elseif(parent->_bf ==-2&& cur->_bf ==-1){RotateL(parent);}elseif(parent->_bf ==2&& cur->_bf ==-1){RotateLR(parent);}elseif(parent->_bf ==-2&& cur->_bf ==1){RotateRL(parent);}elseassert(false);break;}else{assert(false);}}returntrue;}voidInOrder(){_InOrder(_root);}boolIsBalanceTree(){return_IsBalanceTree(_root);} Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key) cur = cur->_right;elseif(cur->_kv.first > key) cur = cur->_left;elsereturn cur;}returnnullptr;}intHeight(){return_Height(_root);}intSize(){return_Size(_root);}private:int_Size(Node* root){if(root ==nullptr)return0;return_Size(root->_left)+_Size(root->_right)+1;}int_Height(Node* root){if(root ==nullptr)return0;int leftHeight =_Height(root->_left);int rightHeight =_Height(root->_right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}bool_IsBalanceTree(Node* root){if(root ==nullptr)returntrue;int leftHeight =_Height(root->_left);int rightHeight =_Height(root->_right);int diff = leftHeight - rightHeight;if(abs(diff)>=2){ cout << root->_kv.first <<"高度差异常"<< endl;returnfalse;}if(root->_bf != diff){ cout << root->_kv.first <<"平衡因子异常"<< endl;returnfalse;}return_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}void_InOrder(Node* root){if(root ==nullptr){return;}_InOrder(root->_left); cout << root->_kv.first <<":"<< root->_kv.second <<" ";_InOrder(root->_right);}voidRotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppNode = parent->_parent; parent->_left = subLR;if(subLR){ subLR->_parent = parent;} subL->_right = parent; parent->_parent = subL;if(parent == _root){ subL->_parent =nullptr; _root = subL;}else{ subL->_parent = ppNode;if(parent == ppNode->_right) ppNode->_right = subL;else ppNode->_left = subL;} parent->_bf =0; subL->_bf =0;}voidRotateL(Node* parent){ Node* subR = parent->_right; Node* ppNode = parent->_parent; Node* subRL = subR->_left; parent->_right = subRL; parent->_parent = subR;if(subRL){ subRL->_parent = parent;} subR->_left = parent;if(parent == _root){ _root = subR; subR->_parent =nullptr;}else{ subR->_parent = ppNode;if(parent == ppNode->_right) ppNode->_right = subR;else ppNode->_left = subR;} parent->_bf =0; subR->_bf =0;}voidRotateLR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if(bf ==1){ subLR->_bf =0; subL->_bf =0; parent->_bf =-1;}elseif(bf ==-1){ subLR->_bf =0; subL->_bf =1; parent->_bf =0;}elseif(bf ==0){ subL->_bf = subLR->_bf = parent->_bf =0;}else{assert(false);}}voidRotateRL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if(bf ==0){ parent->_bf = subR->_bf = subRL->_bf =0;}elseif(bf ==1){ subRL->_bf =0; parent->_bf =0; subR->_bf =-1;}elseif(bf ==-1){ subRL->_bf =0; parent->_bf =1; subR->_bf =0;}else{assert(false);}} Node* _root =nullptr;};// 测试代码voidTestAVLTree1(){ 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){/*if (e == 14) { int x = 0; }*/ t.Insert({ e, e }); cout <<"Insert:"<< e <<"->"; cout << t.IsBalanceTree()<< endl;} t.InOrder(); cout << t.IsBalanceTree()<< endl;}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等voidTestAVLTree2(){constint N =1000000; vector<int> v; v.reserve(N);srand((unsignedint)time(0));for(int i =0; i < N; i++){ v.push_back(rand()+ i);} size_t begin2 =clock(); AVLTree<int,int> t;for(auto e : v){ t.Insert(make_pair(e, e));} size_t end2 =clock(); cout << t.IsBalanceTree()<< endl; cout <<"Insert:"<< end2 - begin2 << endl; cout <<"Height:"<< t.Height()<< endl; cout <<"Size:"<< t.Size()<< endl; size_t begin1 =clock();// 确定在的值/*for (auto e : v) { t.Find(e); }*/// 随机值for(int i =0; i < N; i++){ t.Find((rand()+ i));} size_t end1 =clock(); cout <<"Find:"<< end1 - begin1 << endl;}

Test.cpp

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include<assert.h>#include<vector>usingnamespace std;#include"AVLTree.h"intmain(){TestAVLTree1();TestAVLTree2();return0;}

七、总结与展望

随着数据量的不断增长，如何保持高效的查找与插入操作成为了现代计算机科学的核心问题之一。AVL树作为一种自平衡二叉查找树，凭借其稳定的时间复杂度和高效的性能，已广泛应用于各类需要动态数据结构支持的场景。未来，随着算法和硬件的进一步发展，AVL树的实现和优化将迎来更多挑战与机遇。我们期待看到更高效的树形结构和操作算法，不断推动计算机科学的前沿发展，同时也期待你在实现这些算法时能够继续探索与创新，为我们带来更多启发和思考。

以上就是关于【C++篇】树影摇曳，旋转无声：探寻AVL树的平衡之道的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️

在这里插入图片描述

Read more

Flutter 三方库 appstream 的鸿蒙化适配指南 - 驾驭 Linux 生态元数据规范，打造高性能、标准化、国际化的 OpenHarmony 桌面应用商店分发基石

Flutter 三方库 appstream 的鸿蒙化适配指南 - 驾驭 Linux 生态元数据规范，打造高性能、标准化、国际化的 OpenHarmony 桌面应用商店分发基石

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 appstream 的鸿蒙化适配指南 - 驾驭 Linux 生态元数据规范，打造高性能、标准化、国际化的 OpenHarmony 桌面应用商店分发基石 前言 随着鸿蒙（OpenHarmony）生态向 PC 和平板端的高速扩张，如何为海量的三方软件建立一套标准化的“数字档案”，成了构建应用商店生态的核心痛点。过去，开发者提交应用信息时，往往采用碎片化的 JSON 或自定义文档。这会导致软件分发时详情页展示不一、多语言支持混乱，甚至连基本的截图和版本日志都难以对齐。 为了解决这个问题，我们需要引入一套具备全球化视野的元数据定义标准。appstream 作为 Linux 生态下最重要的应用信息描述规范，能够通过结构化的 XML 标签，精准定义软件的身世、功能和展示资产。适配到鸿蒙平台后，它不仅能让你的重型“鸿蒙私有应用商店”瞬间具备吞金般的解析能力，

By Ne0inhk
[特殊字符]颠覆MCP！Open WebUI新技术mcpo横空出世！支持ollama！轻松支持各种MCP Server！Cline+Claude3.7轻松开发论文检索MCP Server！

[特殊字符]颠覆MCP！Open WebUI新技术mcpo横空出世！支持ollama！轻松支持各种MCP Server！Cline+Claude3.7轻松开发论文检索MCP Server！

🔥🔥🔥本篇笔记所对应的视频：🚀颠覆MCP！Open WebUI新技术mcpo横空出世！支持ollama！轻松支持各种MCP Server！Cline+Claude3.7轻松开发MCP服务_哔哩哔哩_bilibili Open WebUI 的 MCPo 项目：将 MCP 工具无缝集成到 OpenAPI 的创新解决方案 随着人工智能工具和模型的快速发展，如何高效、安全地将这些工具集成到标准化的 API 接口中成为了开发者面临的重要挑战。Open WebUI 的 MCPo 项目（Model Context Protocol-to-OpenAPI Proxy Server）正是为了解决这一问题而设计的。本文将带您深入了解 MCPo 的功能、优势及其对开发者生态的影响。 什么是 MCPo？ MCPo 是一个简单、可靠的代理服务器，能够将任何基于 MCP 协议的工具转换为兼容

By Ne0inhk
Qwen3+Qwen Agent 智能体开发实战，打开大模型MCP工具新方式！（一）

Qwen3+Qwen Agent 智能体开发实战，打开大模型MCP工具新方式！（一）

系列文章目录 一、Qwen3+Qwen Agent 智能体开发实战，打开大模型MCP工具新方式！（一） 二、Qwen3+Qwen Agent +MCP智能体开发实战（二）—10分钟打造"MiniManus" 前言 要说最近人工智能界最火热的开源大模型，必定是阿里发布不久的Qwen3系列模型。Qwen3模型凭借赶超DeepSeek-V3/R1的优异性能，创新的混合推理模式，以及极强的MCP能力迅速成为AI Agent开发的主流基座模型。大家可参考我的文章一文解析Qwen3大模型详细了解Qwen3模型的核心能力。有读者私信我： “Qwen3官网特地强调增强了Agent和代码能力，同时加强了对MCP的支持，那么我该如何利用Qwen3快速开发MCP应用呢？” 这就就需要使用我们今天的主角——Qwen官方推荐的开发工具Qwen-Agent ，本期分享我们就一起学习快速使用Qwen3+QwenAgent 接入MCP服务端，快速开发AI Agent应用！ 一、注册 Qwen3 API-Key 本次分享通过阿里云百炼大模型服务平台API Key请求方式调用Qwen3大模型，获取服务平台

By Ne0inhk