AVL树(平衡二叉搜索树)

这篇具有很好参考价值的文章主要介绍了AVL树(平衡二叉搜索树)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

如果BST树插入的顺序是有序的,那么BST树就会退化成一个双链表结构,查询的速率就会很慢,

所以有了AVL树的意义。

AVL树的定义:

是具有下列性质的二叉搜索树

        1、它的左子树和右子树都是AVL树

        2、左子树和右子树的高度之差的绝对值不超过1

结点的平衡因子:每一个结点都有一个平衡因子,代表着右子树(左子树)高度减去左子树(右子树)高度的高度差,AVL树任一结点的平衡因子只能取-1,0,1。

AVL树的插入:

向一棵本来是平衡的AVL树插入时,出现了不平衡,则需要做平衡话处理,使其平衡

平衡化旋转

1、如单旋转(左旋和右旋)

2、双旋转(左平衡和右平衡)

3、每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变,因此,需要从插入位置沿通向根的路径回溯,检查各结点的平衡因子(左、右子树的高度差)。

如果在某一结点发现高度不平衡,停止回溯。

1、从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点

2、如果这三个结点处于一条直线上,则采用单旋转进行平衡化,单旋转可按其方向分为左单旋和右单旋,其中一个是另一个的镜像,其方向与不平衡的形状相关

3、如果这三个结点处于一条折现上,则采用双旋转进行平衡化,双旋转也分两种。

左单旋转

AVL树(平衡二叉搜索树)

void RotateLeft(AVLTree* ptree, AVLNode* ptr)//左单旋
{
	assert(ptree != nullptr && ptr != nullptr);
	AVLNode* newroot = ptr->rightchild;
	newroot->parent = ptr->parent;
	ptr->rightchild = newroot->leftchild;
	if (newroot->leftchild != nullptr)
	{
		newroot->leftchild->parent = ptr;
	}
	newroot->leftchild = ptr;
	AVLNode* pa = ptr->parent;
	if (pa == nullptr)
	{
		ptree->root = newroot;
	}
	if (pa->leftchild = ptr)
	{
		pa->leftchild = newroot;
	}
	else
	{
		pa->rightchild = newroot;
	}
	ptr->parent = newroot;
}

右单旋

void RotateRight(AVLTree* ptree, AVLNode* ptr)//右单旋
{
	assert(ptree != nullptr && ptr != nullptr);
	AVLNode* newroot = ptr->leftchild;
	newroot->parent = ptr->parent;
	ptr->leftchild = newroot->rightchild;
	if (newroot->rightchild != nullptr)
	{
		ptr->leftchild->parent = ptr;
	}
	newroot->rightchild = ptr;
	AVLNode* pa = ptr->parent;
	if (pa == nullptr)
	{
		ptree->root = newroot;
	}else
	{
	if (pa->leftchild == ptr)
	{
		pa->leftchild = newroot;
	}
	else
	{
		pa->rightchild = newroot;
	}
	ptr->parent = newroot;
	}
}

双旋转

AVL树(平衡二叉搜索树)

 

//双旋转 分为两次单旋转
void LeftBalance(AVLTree* ptree, AVLNode* ptr)//左平衡
{
	assert(ptree != nullptr && ptr != nullptr);
	AVLNode* leftsub = ptr->leftchild, * rightsub = nullptr;
	switch (leftsub -> balance)
	{
	case 0:
		cout << "left banlance!" << endl;
		break;
	case -1:
		ptr->balance = 0;
		leftsub->balance = 0;
		RotateRight(ptree, ptr);
		break;
	case 1:
		rightsub = leftsub->rightchild;
		switch (rightsub->balance)
		{
		case 0:
			ptr->balance = 0;
			leftsub->balance = 0;
			break;
		case 1:
			ptr->balance = 0;
			leftsub->balance = -1;
			break;
		case -1:
			ptr->balance = 1;
			leftsub->balance = 0;
			break;
		}
		rightsub->balance = 0;
		RotateLeft(ptree, leftsub);
		RotateRight(ptree, ptr);
		break;
	}
}
void RightBalance(AVLTree* ptree, AVLNode* ptr)//右平衡
{
	assert(ptree != nullptr && ptr != nullptr);
	AVLNode* rightsub = ptr->rightchild, * leftsub = nullptr;
	switch (rightsub->balance)
	{
	case 0:
		cout << "avl tree right balance" << endl;
		break;
	case 1:
		ptr->balance = 0;
		rightsub->balance = 0;
		RotateLeft(ptree, ptr);
		break;
	case -1:
		leftsub = rightsub->leftchild;
		switch (leftsub->balance)
		{
		case 0: 
			ptr->balance = 0;
			rightsub->balance = 0;
			break;
		case 1:
			ptr->balance = -1;
			rightsub->balance = 0;
			break;
		case -1:
			ptr->balance = 0;
			rightsub->balance = 1;
			break;
		}
		leftsub->balance = 0;
		RotateRight(ptree, rightsub);
		RotateLeft(ptree, ptr); 
		break;
	}
	
}

插入和调整

void Adjust_Insert_Item(AVLTree* ptree, AVLNode* ptr)
{
	assert(ptree != nullptr && ptr != nullptr);
	bool taller = true;
	AVLNode* pa = ptr->parent;
	while (pa != nullptr && taller)
	{
		if (pa->leftchild == ptr)
		{
			switch (pa->balance)
			{
			case 0: pa->balance = -1; break;
			case 1: pa->balance = 0;
				taller = false;
				break;
			case -1:
				LeftBalance(ptree, pa);
				taller = false;
				break;
			}
		}
		else
		{	// ptr pa->rightchild
			switch (pa->balance)
			{
			case 0: pa->balance = 1; break;
			case -1: pa->balance = 0;
				taller = false;
				break;
			case 1:
				RightBalance(ptree, pa);
				taller = false;
				break;
			}
		}
		ptr = pa;
		pa = ptr->parent;
	}
}

bool Insert_Item(AVLTree* ptree, const KeyType kx)
{
	assert(ptree != nullptr);
	AVLNode* ptr = ptree->root, * pa = nullptr;
	while (ptr != nullptr && ptr->key != kx)
	{
		pa = ptr;
		ptr = kx > ptr->key ? ptr->rightchild : ptr->leftchild;
	}
	if (ptr != nullptr && ptr->key == kx) return false;

	ptr = Buynode();
	ptr->key = kx;
	ptr->parent = pa; //
	if (pa != nullptr)
	{
		if (ptr->key > pa->key)
		{
			pa->rightchild = ptr;
		}
		else
		{
			pa->leftchild = ptr;
		}
	}
	else
	{
		ptree->root = ptr;
	}
	Adjust_Insert_Item(ptree, ptr);
	ptree->cursize += 1;
}

删除

和删除BST树结点思路相同,如果是双分支,则删除中序遍历的下一个结点文章来源地址https://www.toymoban.com/news/detail-448423.html

到了这里,关于AVL树(平衡二叉搜索树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)

    前面我们对 map / multimap / set / multiset 进行了简单的介绍,可以发现,这几个容器有个共同点是: 其底层都是按照 二叉搜索树 来实现的。 但是二叉搜索树有其自身的缺陷,假如 往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成 O(N) ,

    2024年02月06日
    浏览(45)
  • 【数据结构】平衡二叉搜索树(AVL树)——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改

      为什么要引入平衡二叉搜索树?   在之前我们学习了二叉搜索树,二叉搜索树的结构类似于一个倒置的树,而左子树的值小于根节点的值,右节点的值大于根节点的值,这种结构使得二叉搜索树在处理有序数据时非常高效。但是如果 在传入的数据为有序或接近有序,

    2024年02月07日
    浏览(49)
  • C++数据结构之平衡二叉搜索树(一)——AVL的实现(zig与zag/左右双旋/3+4重构)

    本文是介绍众多平衡二叉搜索树(BBST)的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树(BST)在极度退化的情况下,十分不平衡,不平衡到只朝一侧偏,成为一条链表,复杂度可达 O ( n ) O(n) O ( n ) ,所以我们要在“平衡”方面做一些约束,以防

    2024年02月13日
    浏览(38)
  • 【C++】AVL树(平衡二叉树)

    AVL树,全称 平衡二叉搜索(排序)树 。 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下 。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法

    2024年02月12日
    浏览(41)
  • AVL——平衡搜索树

    ✅1主页 :我的代码爱吃辣 📃2知识讲解 :数据结构——AVL树 ☂️3开发环境 :Visual Studio 2022 💬4前言 :AVL树是对二叉搜索树的严格高度控制,所以AVL树的搜索效率很高,但是这是需要付出很大的代价的,要维护父亲指针,和平衡因子。 目录 一.AVL的概念 二. AVL树节点及整体

    2024年02月11日
    浏览(32)
  • 【C++】AVL树(高度平衡二叉树)

    概念 二叉搜索树虽然可以缩短查找的效率,但如果数据有序或者接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。 。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新

    2024年02月11日
    浏览(38)
  • 【数据结构与算法】平衡二叉树(AVL树)

    给你一个数列{1,2,3,4,5,6},要求创建二叉排序树(BST),并分析问题所在。 BST 存在的问题分析 : 左子树全部为空,从形式上看,更像一个单链表。 插入速度没有影响。 查询速度明显降低(因为需要依次比较),不能发挥 BST 的优势,因为每次还需要比较左子树,其查询速度

    2024年02月13日
    浏览(42)
  • 计算机基础--->数据结构(6)【AVL树(平衡二叉树)】

    平衡二叉树是一种特殊的二叉搜索树,他的左子树与右子树的高度差不超过1。并且左右两个子树都是一颗平衡二叉树。保持平衡的特性使得平衡二叉树的查询、插入和删除操作在平均和最坏情况下的时间复杂度都是 O(logn) ,其中n是树中节点的数量。 相比于普通的二叉搜索树

    2024年02月12日
    浏览(57)
  • 数据结构奇妙旅程之二叉平衡树进阶---AVL树

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年03月13日
    浏览(83)
  • 数据结构07:查找[C++][平衡二叉排序树AVL]

    图源:文心一言 考研笔记整理1w+字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_2 平衡二叉树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月11日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包