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

AVL树实现

news 2025/5/11 7:24:23

1.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树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。
  • AVL树整体节点数量的分布和完全二叉树类似，高度可以控制在lonN，那么增删查改的效率也可以控制在O(logN)，相比二叉搜索树有了本质的提升。

插入后平衡因子改变，并且它的高度差大于1。下面我们来看如何调整。

2.AVL树的实现

2.1 AVL树的结构

#include<iostream>
#include<assert.h>using namespace std;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):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K,V> Node;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子树的高度，恢复到插入节点以前的高度。所以旋转后也不需要继续向上更新，插入结束。
  • 不断更新，更新到根，根的平衡因子是1或-1也停止了。

更新到10节点，平衡因子为2，10的所在的子树已经不平衡，需要旋转处理

更新到中间节点，3为根的子树高度不变，不会影响上一层，更新结束

最坏更新到根停止

插入的代码

bool insert(const 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 (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)//平衡因子为0，平衡就退出{break;}else if (parent->_bf == 1 || parent->_bf == -1)//平衡因子为1或者-1，就继续向上调整{parent = parent->_parent;cur = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//平衡因子为2时就已经不平衡了，旋转{//旋转，旋转完了退出break;}else{assert(false);}}return true;}

2.3 旋转

2.3.1 旋转的原则

1、保持搜索树的规则

2、让旋转的数从不平衡变成平衡，其次降低旋转树的高度。

旋转总共分为四种：左单旋/右单旋/左右双旋/右左双旋。（左右单旋时，全是一边高的情况）

2.3.2 右单旋

  • 本图1展示的是10为根的树，有a/b/c抽象为三颗高度为h的子树（h>=0），a/b/c均符号AVL树的要求。10可能是整棵树的根，也有可能是一棵树中局部子树的根。这里a/b/c是高度为h的子树是一种概况抽象表示，它代表了所以右单旋的场景，实际右单旋形态有很多种，具体图2/图3/图4/图5进行了详细描述。
  • 在a子树中插入一个新结点，导致a子树的高度从h变为了h+1，不断向上更新平衡因子，导致10的平衡因子从-1变成了-2,，10为根的树左右高度差超过了1，违反了平衡规则。10为根的树左边太高了，需要往右旋转，控制两颗树的平衡。
  • 旋转核心步骤，因为 5 < b子树的值 < 10，将b变成10的左子树，10变成5的右子树，5变成了这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵树的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前10整棵树是一个局部子树，旋转之后不会再影响上一层，插入结束。

情况1：插入前a/b/c高度h = 0

:情况2：插入前a/b/c高度h = 1

情况3：插入前a/b/c的高度h = 2

情况4：插入前a/b/c高度h = 3

右单旋的代码：

	void RatoteRight(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//将subL的右给了parent的左if (subLR){subLR->_parent = parent;}subL->_right = parent;//parent成为了subL右if (parent == _root)//如果parent是根，旋转后subL就是新的根{_root = subL;}else//当parent是局部子树的根{Node* Pparent = parent->_parent;//记录上个_parent节点if (Pparent->_left == parent){Pparent->_left = subL;}else{Pparent->_right = subL;}subL->_parent = Pparent;}parent->_parent = subL;//旋转完后 subL和parent平衡因子都是0parent->_bf = subL->_bf = 0;}

2.3.3 左单旋

  • 本图6展示的是10为根的树，有a/b/c抽象为三颗高度为h的子树（h >= 0），a/b/c均符号AVL树的要求。10可能是整棵树的根，也可能是一整棵树中局部子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体根上面左旋类似。
  • 在a子树中插入一个新节点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变成了2，10为根的树左右高度差超过了1，违反平衡规则。10为根的树右边太高了，需要往左边旋转，控制两棵树的平衡。
  • 旋转的核心步骤，因为 10 < b子树的值 < 15，将b变成10的右子树，10变成15的左子树，15变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵树的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前10整棵树是一个局部子树，旋转后不会再影响上一层，插入结束了。

左旋代码

void Ratoteleft(Node* parent)//左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* Pparent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (Pparent->_left == parent){Pparent->_left = subR;}else{Pparent->_right = subR;}subR->_parent = Pparent;}subR->_bf = parent->_bf = 0;}

2.3.4 左右双旋

通过图7和图8可以看到，左边高时，如果插入位置不是在a子树，而是插入在b子树，b子树高度从h变成h+1，引发旋转，右单旋无法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的是纯粹左边高的问题，但是插入在b子树中，10为根的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，需要用两次旋转才能解决，以5为旋转点进行一个左单旋，以10为旋转点进行一个右单旋，这棵树就平衡了。

  • 图7和图8分别为左右双旋中h = 0和h = 1具体场景分析，下面我们将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进一步展开成8和左子树高度为h - 1的e和f子树，因为我们要对b的父亲5为旋转点进行左单旋，左单旋需要动b树中的左子树。b子树中新增节点的位置不同，平衡因子更新的细节也不同，通过观察8的平衡因子不同，这里我们要分三个场景讨论。
  • 场景1：h>=1时，新增节点插入在e子树，e子树高度从h-1变为h并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因子为-1，旋转后8和5平衡因子为0,10的平衡因子为1。
  • 场景2：h>=1时，新增节点插入在f子树，f子树高度从h-1变为h并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因子为1，旋转后8和10平衡因子为0,5平衡因子为-1。
  • 场景3：h==0时，a/b/c都是空树，b自己就是一个新增节点，不断更新5->10平衡因子，引发旋转，其中8的平衡因子为0，旋转后8和10和5的平衡因子都是0。

void RatoteLR(Node* parent)//左右双旋{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//记录插入时引发旋转的子树的平衡因子RatoteLeft(parent->_left);RatoteRight(parent);if (bf == 0)//平衡因子等于0时，场景3{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if(bf == -1)//平衡因子等于-1时场景1{parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if(bf == 1)//平衡因子等于1时场景2{parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else{assert(false);}}

2.3.5 右左双旋

  • 跟左右双旋类似，下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析，另外我们需要把b⼦树的细节进⼀步展开为12和左⼦树⾼度为h-1的e和f⼦树，因为我们要对b的⽗亲15为旋转点进⾏右单旋，右单旋需要动b树中的右⼦树。b⼦树中新增结点的位置不同，平衡因⼦更新的细节也不同，通过观察12的平衡因⼦不同，这⾥我们要分三个场景讨论。
  • 场景1：h >= 1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为-1，旋转后10和12平衡因⼦为0，15平衡因⼦为1。
  • 场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为1，旋转后15和12平衡因⼦为0，10平衡因⼦为-1。
  • 场景3：h == 0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新15->10平衡因⼦，引发旋转，其中12的平衡因⼦为0，旋转后10和12和15平衡因⼦均为0。 

void RatoteRL(Node* parent)//右左双旋{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RatoteRight(parent->_right);RatoteLeft(parent);if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else{assert(false);}}

2.4 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.second > key){cur = cur->_left;}else{return cur;}}return nullptr;}

2.5 AVL树平衡检测

bool _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者// pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}

3.代码附录

#pragma once
#include<iostream>
#include<assert.h>using namespace std;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):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K,V> Node;public:bool insert(const 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 (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)//平衡因子为0，平衡就退出{break;}else if (parent->_bf == 1 || parent->_bf == -1)//平衡因子为1或者-1，就继续向上调整{parent = parent->_parent;cur = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//旋转，旋转完了退出if (parent->_bf == -2 && cur->_bf == -1){RatoteRight(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RatoteLeft(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RatoteLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RatoteRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}void RatoteRight(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//将subL的右给了parent的左if (subLR){subLR->_parent = parent;}subL->_right = parent;//parent成为了subL右if (parent == _root)//如果parent是根，旋转后subL就是新的根{_root = subL;}else//当parent是局部子树的根{Node* Pparent = parent->_parent;//记录上个_parent节点if (Pparent->_left == parent){Pparent->_left = subL;}else{Pparent->_right = subL;}subL->_parent = Pparent;}parent->_parent = subL;//旋转完后 subL和parent平衡因子都是0parent->_bf = subL->_bf = 0;}void RatoteLeft(Node* parent)//左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* Pparent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (Pparent->_left == parent){Pparent->_left = subR;}else{Pparent->_right = subR;}subR->_parent = Pparent;}subR->_bf = parent->_bf = 0;}void RatoteLR(Node* parent)//左右双旋{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//记录插入时引发旋转的子树的平衡因子RatoteLeft(parent->_left);RatoteRight(parent);if (bf == 0)//平衡因子等于0时，场景3{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if(bf == -1)//平衡因子等于-1时场景1{parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if(bf == 1)//平衡因子等于1时场景2{parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else{assert(false);}}void RatoteRL(Node* parent)//右左双旋{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RatoteRight(parent->_right);RatoteLeft(parent);if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else{assert(false);}}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.second > key){cur = cur->_left;}else{return cur;}}return nullptr;}int Height(){_Height(_root);}void InOrder(){_InOrder(_root);}bool IsBalanceTree(){return _IsBalanceTree(_root);}private: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 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;// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者// pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}Node* _root = nullptr;
};
#include"AVLTree.h"// 测试代码
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;
}int main()
{TestAVLTree1();return 0;
}

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

相关文章：

  • LLMs之ChatGPT：《Connecting GitHub to ChatGPT deep research》翻译与解读
  • 湖北理元理律师事务所：债务优化如何实现还款与生活的平衡？
  • window 显示驱动开发-AGP 类型伸缩空间段
  • Python基于Django的高校教室管理系统【附源码、文档说明】
  • 等价无穷小代换
  • LeetCode LCR 007. 三数之和 (Java)
  • 学习适应对智能软件对对象的属性进行表征、计算的影响
  • day010-命令实战练习题
  • 《C++中插入位的函数实现及示例说明》
  • 大模型中的三角位置编码实现
  • PySide6 GUI 学习笔记——常用类及控件使用方法（常用类边距QMarginsF）
  • 【部署】win10的wsl环境下启动dify的web前端服务
  • 21.【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--单体转微服务--身份认证服务拆分规划
  • linux perf top分析系统性能
  • 光流 ｜ 基于深度学习的光流估计算法汇总，原理，公式，流程图，代码
  • 人形机器人量产元年开启，AI与物理世界深度融合
  • CAS操作
  • Ceph集群故障处理 - PG不一致修复
  • [SV]等待32个instance的某一个信号的pulse，该怎么写？
  • Windows 系统 - Trae 内 终端 无法使用 node (重新配置 nodejs 路径)
  • 青藏高原东北部祁连山地区250m分辨率多年冻土空间分带指数图（2023）
  • AtCoder AT_abc405_d ABC405D - Escape Route
  • 智慧能源大数据平台建设方案（PPT）
  • 数字孪生实战笔记（1）数字孪生的含义、应用及技术体系
  • RPA 浏览器自动化：高效扩展与智能管理的未来
  • SpringBoot学习(上) , SpringBoot项目的创建(IDEA2024版本)
  • 基于阿伦尼斯模型的电池寿命预测：原理、应用与挑战
  • 数据结构：树（树的定义和基本术语）
  • JGL069垃圾填埋场模拟装置试验台
  • 力扣top100 矩阵置零