当前位置: 首页 > article >正文

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

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 树的核心概念:

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

  • 平衡因子取值范围-101

  • 如果某个节点的平衡因子的绝对值超过 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 factor

		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:
        // ……
    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子树自己不旋转,高度+1subLRparent的左,再将parentsubL的右

注意:

h = 0时,subLRnullptr

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;
				else
					pParent->_right = subL;
			}

			subL->_bf = 0;
			parent->_bf = 0;
		}
2.3.4 左单旋

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

a子树自己不旋转,高度+1subRLparent的右,再将parentsubR的左

注意:

h = 0时,subRLnullptr

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;
				else
					pParent->_right = subR;
			}

			subR->_bf = 0;
			parent->_bf = 0;
		}
2.3.6 左右双旋

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

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

从结果上,subLRsubLsubLRparentsubLR自己做

subLRsubLparent

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

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进行左旋

从结果上,subRLparentsubRLsubRsubRL自己做

subRLparentsubR

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

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;
				else
					return 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树的删除

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 factor

		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* 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);
					else
						assert(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;
				else
					pParent->_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;
				else
					pParent->_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;
				else
					return 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.kler.cn/a/589480.html

相关文章:

  • FPGA中级项目3——IP核之时钟管理单元
  • [Linux]进程控制
  • 视频孪生技术赋能桥梁智慧化检测管理与数字化建设
  • android 后台下载任务,断点续传
  • 【数据分析】.loc和.iloc的应用2
  • 数据结构——串、数组和广义表
  • 【MM】2025投稿重点记录
  • AcWing 5960:输出前k大的数 ← 小根堆
  • 快速方便的Docker下载,包含Win、Mac
  • 汇编基础知识
  • 东方通TongHttpServer:企业级服务代理中间件的卓越之选
  • 泛型主要是用于静态类型检查的工具,它并不会在运行时自动验证返回值类型和传入类型是否一致
  • Linux驱动学习笔记(二)
  • Androidstudio实现一个app引导页(超详细)
  • 三维重建(十七)——obj文件解读+ply文件解读
  • C++ 位图 bitset
  • 使用 netstat 和 tasklist 命令排查端口占用问题
  • 解决前端文字超高度有滚动条的情况下padding失效(el-scrollbar)使用
  • 【愚公系列】《高效使用DeepSeek》012-合同文档合规性检查
  • spring中将yaml文件转换为Properties