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

C++AVL树（二）详解

article 2025/1/26 14:53:59

文章目录

  • AVL树
  • 旋转
    • 单旋
      • 右单旋
      • 左单旋
    • 双旋
      • 左右双旋
      • 右左双旋
    • 平衡因子的更新
      • 左右双旋
      • 右左双旋
  • 判断是不是AVL树
  • 时间复杂度分析
  • 全部的代码

AVL树

旋转

单旋

单旋是纯粹的一边高
单旋平衡因子是同号

右单旋

a,b,c自身不能发生旋转
并且也不能不向上继续更新（不能停止更新）
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

插入之前是h+2，插入后进行旋转后是h+2，没有对pParent它的子树的高度产生影响，不用继续向上更新

// 链接孩子和父亲
// 右单旋,旋转点是parent
void Rotate(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	// b可能为空树
	if (suLR != nullptr)
		subLR->_parent = parent;

	// 记录parent的parent
	pParent = parent->_parent;

	subL->_right = parent;
	parent->_parent = subL;

	// 1. 10是这棵树的总根
	if (parent == _root)
	{
		subL = _root;
		subL->_parent = nullptr;
	}
	else
	{
		// 2. 10是这棵树的局部根
		// 就有父亲的父亲节点
		// pParent左可能是parent,右也可能是parent
		if (pParent->_left == parent)
		{
			pParent->_left = subL;
		}
		else
		{
			pParent->_right = subL;
		}
		subL->_parent = pParent;
    }
    // 更新平衡因子
    subL->_bf = 0;
    parent->_bf = 0;
 }

左单旋

左单旋和右单旋类似
在这里插入图片描述

// 左单旋,旋转点是parent
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	// b不是空树
	if (subRL)
		subRL->_parent = parent;

	// 记录父亲节点的父亲节点
	Node* pParent = parent->_parent;

	subR->_left = parent;
	parent->_parent = subR;

	// 1. 10是这棵树的总根
	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		// 2. 10是这棵树的局部根
		if (pParent->_left == parent)
		{
			pParent->_left = subR;
		}
		else
		{
			pParent->_right = subR;
		}
		subR->_parent = pParent;
	}
	subR->_bf = 0;
	parent->_bf = 0;
}

双旋

双旋平衡因子会异号
双旋是进行两次单旋

对于5来说右边高，对于10来说左边高，需要进行双旋
下面是进行的单旋解决不了问题
在这里插入图片描述
对于5来说右边高，对于10来说左边高，需要进行双旋
进行单旋解决不了问题，会变成下面的样子
在这里插入图片描述

左右双旋

h == 0
在这里插入图片描述

h == 1
在这里插入图片描述

右左双旋

右左双旋和左右双旋类似，这里就不画了

平衡因子的更新

左右双旋

双旋和单旋的平衡因子更新方式不同，双旋按照单旋的方式更新后5,10，8都是0，不符合逻辑

左右双旋中h0和h1具体场景分析，下面我们将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。

在这里插入图片描述
8的平衡因子会影响其它的平衡因子：

  • 插入到8的左边，8的平衡因子为-1
  • 插入到8的右边，8的平衡因子为1
  • 8本身就是要插入的节点，8的平衡因子为0
// 左右双旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// 提前存平衡因子
	int bf = subLR->_bf;

	RotateL(parent->_left);
	RotateR(parent);

	if (subLR->_bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (subLR->_bf == 1)
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (subLR->_bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

右左双旋

跟左右双旋类似，下面我们将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。

在这里插入图片描述

3种情况：

  • 插入到e那边
  • 插入到f那边
  • b本身就是插入的点
// 右左双旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	// 提前存放平衡因子
	int bf = subRL->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	if (bf == -1)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 1)
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == 0)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

判断是不是AVL树

用高度差的绝对值是否 <= 1来检查

// 算树的高度,左右子树高的那个加1
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;
}

// 判断是不是AVL树
bool _IsBalanceTree(Node* root)
{
	// 空树也是AVL树
	if (root == nullptr)
		return true;

	// pRoot的子树的平衡因子,左右子树的高度差
	int _leftheight = _Height(root->_left);
	int _rightheight = _Height(root->_right);
	int diff = _rightheight - _leftheight;

	// 高度差超过2或者pRoot的平衡因子不等于计算出的平衡因子就不是AVL树
	if (abs(diff) >= 2)
	{
		cout << root->_kv.first << "高度差异常" << endl;
		return false;
	}
	else if (diff != root->_bf)
	{
		cout << root->_kv.first << "平衡因子异常" << endl;
		return false;
	}
    
	// pRoot节点的左树和右树都是AVL树,那么就是AVL树
	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

时间复杂度分析

插入：logN,寻找插入的位置，会找到叶子的位置
旋转：常数次
调整：假设最坏情况调整到根logN，平衡因子为-1/1,要继续调整
时间复杂度：logN

全部的代码

#pragma once
#include<iostream>
#include<assert.h>

using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	// 需要parent指针
	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)// 刚插入的节点平衡因子都是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 (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 (parent->_left == cur)
				parent->_bf--;
			else // if (parent->_right == cur)
				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)
			{
				// 旋转
				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
			{
				// 逻辑错误,之前就不是AVL树
				assert(false);
			}
		}
		return true;
	}

	// 右单旋,旋转点是parent
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		// b可能为空树
		if (subLR != nullptr)
			subLR->_parent = parent;

		// 记录parent的parent
		Node* pParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		// 1. 10是这棵树的总根
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			// 2. 10是这棵树的局部根
			// pParent左可能是parent,右也可能是parent
			if (pParent->_left == parent)
			{
				pParent->_left = subL;
			}
			else
			{
				pParent->_right = subL;
			}
			subL->_parent = pParent;
		}
		// 更新平衡因子
		subL->_bf = 0;
		parent->_bf = 0;
	}

	// 左单旋,旋转点是parent
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		// b不是空树
		if (subRL)
			subRL->_parent = parent;

		// 记录父亲节点的父亲节点
		Node* pParent = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		// 1. 10是这棵树的总根
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			// 2. 10是这棵树的局部根
			if (pParent->_left == parent)
			{
				pParent->_left = subR;
			}
			else
			{
				pParent->_right = subR;
			}
			subR->_parent = pParent;
		}
		subR->_bf = 0;
		parent->_bf = 0;
	}

	// 左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		// 提前存平衡因子
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (subLR->_bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (subLR->_bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (subLR->_bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	// 右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		// 提前存放平衡因子
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == -1)
		{
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			subRL->_bf = 0;
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == 0)
		{
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 0;
		}
		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.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
	    }

		return nullptr;
	}

	// 大小
	int Size()
	{
		return _Size(_root);
	}
    
	// 判断是不是AVL树
	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}
	
	// 算树的高度
	int Height()
	{
		_Height(_root);
	}

	// 中序
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	// 算树的高度,左右子树高的那个加1
	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;
	}

	// 判断是不是AVL树
	bool _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树
		if (root == nullptr)
			return true;

		// pRoot的子树的平衡因子,左右子树的高度差
		int _leftheight = _Height(root->_left);
		int _rightheight = _Height(root->_right);
		int diff = _rightheight - _leftheight;

		// 高度差超过2或者pRoot的平衡因子不等于计算出的平衡因子就不是AVL树
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "高度差异常" << endl;
			return false;
		}
		else if (diff != root->_bf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
        
		// pRoot节点的左树和右树都是AVL树,那么就是AVL树
		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 << endl;
		_InOrder(root->_right);
	}

private:
	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.kler.cn/a/517434.html

相关文章：

  • （Halcon）轮廓等分切割（项目分析）
  • StarRocks常用命令
  • frida的常用api
  • ORB-SLAM2源码学习：Initializer.cc⑧: Initializer::CheckRT检验三角化结果
  • LabVIEW项目中的工控机与普通电脑选择
  • 二叉树相关oj题 1. 检查两颗树是否相同。
  • 港科夜闻 | 香港科大获三千万基金资助,开发人工智能英语评估及学习系统,供全港中学生免费使用...
  • PostgreSQL中级专家是什么意思？
  • AI问答：在后端开发语境中 VO 是什么 / Value Object / 值对象
  • 第12章 volatile关键字的介绍（Java高并发编程详解：多线程与系统设计）
  • Lua语言的图形用户界面
  • Vue3 插槽（Slots）用法总结
  • 一组开源、免费、Metro风格的 WPF UI 控件库
  • DBeaver下载安装及数据库连接（MySQL）
  • 初步理解数据结构
  • 每日一题 419. 棋盘上的战舰
  • GESP2024年6月认证C++六级( 第三部分编程题（2）二叉树）
  • react native i18n插值：跨组件trans
  • 麒麟操作系统基础知识保姆级教程（二十一）进入单用户模式
  • UE5 特效
  • 面试-二维数组
  • Oracle 创建用户和表空间
  • 第15章 监控任务的生命周期(Java高并发编程详解：多线程与系统设计)
  • Servlet 详解
  • EMC常用器件选型（一）
  • 提示词的艺术 ---- AI Prompt 进阶（提示词框架）