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

C++进阶——AVL树的实现

news 2025/3/18 23:48:52

目录

1、AVL的概念

1.1 AVL 树的发明

1.2 AVL 树的定义

1.3 平衡因子

1.4 为什么高度差 <= 1 ？

1. 5 AVL 树的性能

2、AVL树的实现

2.1 AVL树的结构

2.2 AVL树的插入

2.2.1 AVL树插入一个值的大概过程

2.2.2 平衡因子的更新

更新原则：

2.2.3 插入的代码实现

2.3 旋转

2.3.1 旋转的原则

2.3.2 右单旋

2.3.3 右单旋的代码实现

2.3.4 左单旋

2.3.5 左单旋的代码实现

2.3.6 左右双旋

2.3.7 左右双旋的代码实现

2.3.8 右左双旋

2.3.9 右左双旋的代码实现

2.4 AVL树的查找

2.5 AVL树的平衡检测

2.6 AVL树的删除

2.7 AVL的代码实现

2.7.1 AVLTree.h

2.7.2 Test.cpp

1、AVL的概念

1.1 AVL 树的发明

AVL 树由 G.M. Adelson-Velsky 和 E.M. Landis 在 1962 年的论文《An algorithm for the organization of information》中提出。他们的设计目标是解决二叉搜索树在动态操作（插入、删除）中可能退化为链表的问题。

1.2 AVL 树的定义

AVL 树是一种自平衡二叉搜索树，满足以下性质：

  • 它是一棵空树，或者：

    • 它的左右子树都是 AVL 树。

    • 左右子树的高度差(平衡因子)的绝对值 <= 1。

1.3 平衡因子

平衡因子（Balance Factor）是 AVL 树的核心概念：

  • 定义：某个节点的平衡因子 = 右子树的高度 - 左子树的高度。

  • 平衡因子的取值范围：-1、0、1。

  • 如果某个节点的平衡因子的绝对值超过 1，则该节点不平衡，需要通过旋转操作进行调整。

1.4 为什么高度差 <= 1 ？

高度差为 0 表示左右子树的高度相等，这种理想状态在某些情况下是无法实现的。

  • 例如：

    • 当树的节点数为 2 时，高度差只能为 1。

    • 当树的节点数为 4 时，高度差也只能为 1。

  • 如果强制要求高度差为 0，会导致树的结构过于严格，难以在动态操作中保持平衡。

1. 5 AVL 树的性能

AVL 树的性能优势主要体现在其高度平衡性：

  • 高度控制：AVL 树的高度 始终保持在 O(log⁡N)。

  • 操作效率：插入、删除、查找等操作的时间复杂度均为 O(log⁡N)。

2、AVL树的实现

2.1 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 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. 更新平衡因子过程中出现不平衡(平衡因子的绝对值超过 1)，对不平衡子树 旋转，旋转后本质调平衡的同时，降低了子树的高度，不会再影响上一层，所以插入结束。

2.2.2 平衡因子的更新
更新原则：

1. 平衡因子的定义

平衡因子 = 右子树高度 - 左子树高度。

2. 影响平衡因子的条件

只有子树高度变化 才会影响当前节点的平衡因子。

3. 插入节点对平衡因子的影响

  • 如果新增节点在parent的右子树，parent的平衡因子++。

  • 如果新增节点在parent的左子树，parent的平衡因子--。

更新情况：

1. 更新后parent的平衡因子 等于 0

因为插入前，就是平衡搜索树，平衡因子只能是-1，0，1，所以一定是从-1或1变成0，子树整体的

高度不变，结束更新。

2. 更新后parent的平衡因子 等于 1 或 -1

一定是从0变成-1或1，子树整体的高度变化，继续更新。

3. 更新后parent的平衡因子等于 2 或 -2

一定是从-1变成-2或1变成2，parent高的子树更高了，不平衡了。

通过旋转，平衡(即降低树的高度)，并使子树的根的平衡因子为0。

即-1->-2(旋转)->0，或1->2(旋转)->0，相当于子树的高度没变，结束更新。

4. 更新到根节点

如果更新到根节点，且根节点的平衡因子为 1 或 -1，结束更新。因为根的parent为nullptr，不用更

新了。

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 (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因子while (parent) // parent = nullptr,为根节点的父亲,结束更新{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 = cur->_parent;}else if (parent->_bf == -2 || parent->_bf == 2){// 旋转break;}else{assert(false);}}return true;}

2.3 旋转

2.3.1 旋转的原则

1. 保持搜索树的规则。

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

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

2.3.2 右单旋

即左侧高，右侧的parent旋下来。平衡因子同号。

a,b,c子树为抽象表示，实际上有非常多种情况。

a子树自己不旋转，高度+1，将subLR给parent的左，再将parent给subL的右，subL做根。

注意：

当h = 0时，subLR为nullptr。

parent如果是局部子树的根，就改变连接关系，如果是根，就改变根。

2.3.3 右单旋的代码实现
		void RotateR(Node* parent){Node* pParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;subL->_parent = pParent;if (pParent == nullptr) // 当pParent == nullptr时,_root == parent{_root = subL;}else{if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;}subL->_bf = 0;parent->_bf = 0;}
2.3.4 左单旋

即右侧高，左侧的parent旋下来。平衡因子同号。

c子树自己不旋转，高度+1，将subRL给parent的右，再将parent给subR的左，subR做根。

注意：

当h = 0时，subRL为nullptr。

parent如果是局部子树的根，就改变连接关系，如果是根，就改变根。

2.3.5 左单旋的代码实现
		void RotateL(Node* parent){Node* pParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;subR->_parent = pParent;if (pParent == nullptr)_root = subR;else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;}subR->_bf = 0;parent->_bf = 0;}
2.3.6 左右双旋

即中间高，右侧的parent旋下来。平衡因子异号。

从过程上，是对subL进行左旋，parent进行右旋。

从结果上，subLR的左给subL的右，subLR的右给parent的左，

subLR的左为subL，右为parent，subLR自己做根。

平衡后分三种情况，即有三种情况的平衡因子。

2.3.7 左右双旋的代码实现
		void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int _bf = subLR->_bf;RotateL(subL);RotateR(parent);if (_bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (_bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (_bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}
2.3.8 右左双旋

即中间高，左侧的parent旋下来。平衡因子异号。

从过程上，是对subR进行右旋，parent进行左旋。

从结果上，subRL的左给parent的右，subRL的右给subR的左，

subRL的左为parent，右为subR，subRL自己做根。

平衡后分三种情况，即有三种情况的平衡因子。

2.3.9 右左双旋的代码实现
		void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int _bf = subRL->_bf;RotateR(subR);RotateL(parent);if (_bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else if (_bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (_bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{assert(false);}}

2.4 AVL树的查找

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

2.5 AVL树的平衡检测

		bool _IsBalanceTree(Node* root, int& height) { // 后序// 空树是 AVL 树if (nullptr == root) {height = 0;return true;}// 递归检查左子树int leftHeight = 0;bool isLeftBalanced = _IsBalanceTree(root->_left, leftHeight);// 递归检查右子树int rightHeight = 0;bool isRightBalanced = _IsBalanceTree(root->_right, rightHeight);// 当前节点的高度height = max(leftHeight, rightHeight) + 1;// 计算平衡因子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;}// 如果左右子树都是 AVL 树，且当前节点也平衡，则整棵树是 AVL 树return isLeftBalanced && isRightBalanced;}

2.6 AVL树的删除

AVL树的删除本节不做讲解，有兴趣的同学可参考：《殷人昆 数据结构：用面向对象方法与C++语 言描述》中讲解。

2.7 AVL的代码实现

2.7.1 AVLTree.h
#pragma once#include <iostream>
#include <assert.h>using namespace std;namespace Lzc
{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 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: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 (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (kv.first > parent->_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 = cur->_parent;}else if (parent->_bf == -2 || parent->_bf == 2){if (parent->_bf == -2 && cur->_bf == -1)RotateR(parent);else if (parent->_bf == 2 && cur->_bf == 1)RotateL(parent);else if (parent->_bf == -2 && cur->_bf == 1)RotateLR(parent);else if (parent->_bf == 2 && cur->_bf == -1)RotateRL(parent);elseassert(false);break;}else{assert(false);}}return true;}void RotateR(Node* parent){Node* pParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;subL->_parent = pParent;if (pParent == nullptr) // 当pParent == nullptr时,_root == parent{_root = subL;}else{if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;}subL->_bf = 0;parent->_bf = 0;}void RotateL(Node* parent){Node* pParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;subR->_parent = pParent;if (pParent == nullptr)_root = subR;else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;}subR->_bf = 0;parent->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int _bf = subLR->_bf;RotateL(subL);RotateR(parent);if (_bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (_bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (_bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int _bf = subRL->_bf;RotateR(subR);RotateL(parent);if (_bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else if (_bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (_bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{assert(false);}}void InOrder(){_InOrder(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}bool IsBalanceTree(){int height = 0;return _IsBalanceTree(_root, height);}Node* Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first)cur = cur->_right;else if (key < cur->_kv.first)cur = cur->_left;elsereturn cur;}return nullptr;}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;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}bool _IsBalanceTree(Node* root, int& height) { // 后序// 空树是 AVL 树if (nullptr == root) {height = 0;return true;}// 递归检查左子树int leftHeight = 0;bool isLeftBalanced = _IsBalanceTree(root->_left, leftHeight);// 递归检查右子树int rightHeight = 0;bool isRightBalanced = _IsBalanceTree(root->_right, rightHeight);// 当前节点的高度height = max(leftHeight, rightHeight) + 1;// 计算平衡因子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;}// 如果左右子树都是 AVL 树，且当前节点也平衡，则整棵树是 AVL 树return isLeftBalanced && isRightBalanced;}Node* _root = nullptr;};
}
2.7.2 Test.cpp
#include "AVLTree.h"
#include <vector    >namespace Lzc
{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;}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等void TestAVLTree2() {const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t 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 << "Insert:" << end2 - begin2 << endl;// 测试平衡性、高度和大小cout << "IsBalanceTree:" << t.IsBalanceTree() << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;// 测试查找性能size_t begin1 = clock();// 查找已存在的值/*for (auto e : v) {t.Find(e);}*/// 查找随机值for (size_t i = 0; i < N; i++) {t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;}
}int main()
{Lzc::TestAVLTree1();// Lzc::TestAVLTree2();return 0;
}


http://www.mrgr.cn/news/94886.html

相关文章：

  • unity基础——Navigation导航系统
  • windows ai本地化 部署常用Ollama软件详解
  • 4.JVM-垃圾回收介绍
  • Git——分布式版本控制工具使用教程
  • 流量分析实践
  • 函数（函数的概念、库函数、自定义函数、形参和实参、return语句、数组做函数参数、嵌套调用和链式访问、函数的声明和定义、static和extern）
  • AirtestIDE用法
  • 大数据学习（69）-数据架构
  • 蓝桥杯嵌入式赛道复习笔记2(按键控制LED灯，双击按键，单击按键，长按按键）
  • LeetCode Hot 100：1.两数之和、49.字母异位词分组、128.最长连续序列、283.移动零、11.盛水最多的容器
  • 11.anaconda中的jupyter使用、及整合dataspell
  • 【华为OD-E卷 -122 字符统计及重排 100分（python、java、c++、js、c）】
  • 微服务》》Kubernetes (K8S)安装
  • 【蓝桥杯每日一题】3.16
  • 使用Dependency Walker和Beyond Compare快速排查dll动态库损坏或被篡改的问题
  • hubilder打包ios app, 并上传TestFlight
  • 用uv管理python环境/项目(各种应用场景)
  • WebLogic XMLDecoder反序列化漏洞（CVE-2017-10271）深度解析与实战复现
  • PosterRender 实现微信下程序 分享商品生成海报
  • [蓝桥杯 2023 省 B] 飞机降落