1. Toy模板网首页
  2. > Toy博客

【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改

7月前 作者：鳄鱼麻薯球 分类：Toy博客 阅读(36) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

平衡二叉搜索树（AVL树）

  为什么要引入平衡二叉搜索树？

  在之前我们学习了二叉搜索树，二叉搜索树的结构类似于一个倒置的树，而左子树的值小于根节点的值，右节点的值大于根节点的值，这种结构使得二叉搜索树在处理有序数据时非常高效。但是如果在传入的数据为有序或接近有序，二叉搜索树会退化为单支树，类似链表、此时二叉搜索树在查找、插入、删除的优异性能都消失了。

  同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改,数据结构,数据结构

  最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： l o g 2 N log_2 N log2​N

  最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： N 2 \frac{N}{2} 2N​

             文章来源地址https://www.toymoban.com/news/detail-725768.html

1.AVL树的概念和介绍

  对此我们引入了平衡二叉搜索树，也叫AVL树。

  AVL树是由两位俄罗斯的数学家G. M. Adelson-Velsky和E. M. Landis在1962年的论文《An algorithm for the organization of information》中发明的。这是一种自平衡二叉查找树，任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。

  一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  （1）它的左右子树都是AVL树

  （2）左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改,数据结构,数据结构

  如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)

             

2.AVL树的简单实现

  和实现二叉搜索树的节点类似，只需要考虑多平衡因子和父子节点的关系即可。

  以下为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;   //平衡因子

	AVLTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};

  定义AVL树类:

template<class K,class V>
class AVLTree
{
	//便于书写Node节点
	typedef AVLTreeNode<K, V> Node;
public:
	//AVL树增删查改函数的实现
private:
	Node* _root = nullptr;
};

             

2.1AVL树的插入

  AVL树的插入操作包括插入节点和平衡调整。具体实现步骤如下：

  （1）插入节点：首先，按照普通二叉搜索树的插入方法进行插入。

  （2）平衡调整：插入节点后，从插入节点开始沿着通向根节点的路径向上检查所有节点，观察它们是否仍然保持平衡。如果某个节点的平衡因子绝对值大于1，就需要进行旋转操作以重新平衡这个树。旋转操作包括单旋转和双旋转。

  插入节点实现：

//AVL树插入一个节点
bool AVLInsert(const pair<K, V>& kv)
{
	//创建cur指向根节点
	Node* cur = _root;
	Node* parent = nullptr;

	//如果AVL树为空，直接返回创建的新节点
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	
	//如果AVL树不为空，寻找可以插入的节点
	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;

	//AVL树要保持平衡，控制平衡因子为-1、0、1
	//while()
	
	return true;
}

平衡调整实现：

新节点插入之前：

  平衡因子=右子树的高度-左子树的高度，cur插入后，parent的平衡因子一定需要调整，在插入之前，parent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

   （1）如果cur插入到parent的左侧，左子树高+1，只需给parent的平衡因子-1即可。

   （2）如果cur插入到parent的右侧，右子树高+1，只需给parent的平衡因子+1即可。

【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改,数据结构,数据结构

while (parent)
{
	if (cur == parent->_left)//cur插入在parent左边
	{
		parent->_bf--;
	}
	else if (cur == parent->_right)//cur插入在parent右边
	{
		parent->_bf++;
	}
}

新节点插入之后：

  当cur插入以后，parent的平衡因子可能有三种情况：0，+1 \ -1， +2 \ -2

   （3）如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功且无需旋转。

   （4）如果pParent的平衡因子为+1 \ -1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新，判断是否旋转。

  （5）如果pParent的平衡因子为+2 \ -2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理。

【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改,数据结构,数据结构

【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改,数据结构,数据结构

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)
{
	//子树不平衡了，需要旋转
}
else//如果有其他情况直接报错
{
	assert(false);
}

             

2.2AVL树的旋转

  AVL的旋转分为4种情况：

  （1）左单旋转（Left Single Rotation）：当新节点cur插入在较高右子树的右侧时进行左单旋转。具体步骤为将curleft变为parent的右子树，将parent节点变为cur的左子树，然后更新相关节点的指向。如果parent是根节点，那么cur将成为新的根节点。

  （2）右单旋转（Right Single Rotation）：当新节点cur插入在较低左子树的左侧时进行右单旋转。具体步骤为将curright变为parent的左子树，将parent节点变为cur的右子树，然后更新相关节点的指向。

  （3）右左双旋转（Right Left Double Rotation）：先进行右单旋转，再进行左单旋转。当新节点cur插入在的左子树的右侧时，先进行右单旋转，再进行左单旋转。

  （4）左右双旋转（Left Right Double Rotation）：先进行左单旋转，再进行右单旋转。当新节点cur插入在的右子树的左侧时，先进行左单旋转，再进行右单旋转。

else if (parent->_bf == 2 || parent->_bf == -2)
{
	//子树不平衡了，需要旋转
	if (parent->_bf == 2 && cur->_bf == 1)//左旋
	{
		RotateL(parent);
	}
	else if (parent->_bf == -2 && cur->_bf == -1)//右旋
	{
		RotateR(parent);
	}
	else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋
	{
		RotateRL(parent);
	}
	else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋
	{
		RotateLR(parent);
	}

	break;
}

             

2.2.1左旋

  （1）左单旋转（Left Single Rotation）：当新节点cur插入在较高右子树的右侧时进行左单旋转。具体步骤为将curleft变为parent的右子树，将parent节点变为cur的左子树，然后更新相关节点的指向。如果parent是根节点，那么cur将成为新的根节点。

【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改,数据结构,数据结构

//左旋
void RotateL(Node* parent)
{
	//创建cur节点和父节点
	Node* cur = parent->_right;
	Node* curleft = cur->_left;

	//将右子树的左节点连接在parent的右节点上
	parent->_right = curleft;//关键步骤1
	if (curleft)//如果右子树的左节点不为空，连接一下父节点
	{
		curleft->_parent = parent;
	}

	//将父节点断开连接到原来右节点的左子树上，降低二叉树高度
	cur->_left = parent;//关键步骤2

	//仍需要处理特殊情况
	//如果原父节点不为_root,保存父节点的父节点
	Node* ppnode = parent->_parent;
	
	//两个节点连接
	parent->_parent = cur;

	//如果父节点为_root，直接更新
	if (parent == _root)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else//如果父节点不为_root，需要重新连接
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else//判断是父父节点的左节点还是右节点
		{
			ppnode->_right = cur;

		}

		//反转将cur节点连接父节点
		cur->_parent = ppnode;
	}

	//更新平衡因子
	parent->_bf = cur->_bf = 0;
}

             

2.2.2右旋

  （2）右单旋转（Right Single Rotation）：当新节点cur插入在较低左子树的左侧时进行右单旋转。具体步骤为将curright变为parent的左子树，将parent节点变为cur的右子树，然后更新相关节点的指向。

【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改,数据结构,数据结构

//右旋
	void RotateR(Node* parent)
	{
		//取子节点和子节点中的最大节点，作为父节点的左子树
		Node* cur = parent->_left;
		Node* curright = cur->_right;

		//将父节点和左子树中的最大节点连接，降低层高
		parent->_left = curright;//重要步骤1
		if (curright)
		{
			curright->_parent = parent;
		}

		//将子节点作为根，并将原来父节点连接在子节点的右节点
		cur->_right = parent;//重要步骤2

		//上面的代码基本可以完成右旋操作，但是还要考虑parent是否为_root
		Node* ppnode = parent->_parent;

		parent->_parent = cur;

		if (ppnode == nullptr)//parent为_root
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else//parent不为_root
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else//判断cur节点在原来子树的右边还是左边，并且连接
			{
				ppnode->_right = cur;
			}

			cur->_parent = ppnode;
		}

		//右旋完成，更新平衡因子
		parent->_bf = cur->_bf = 0;
	}

             

2.2.3右左双旋

  双旋源码放在全部源码中。

  （3）右左双旋转（Right Left Double Rotation）：先进行右单旋转，再进行左单旋转。当新节点cur插入在的左子树的右侧时，先进行右单旋转，再进行左单旋转。

【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改,数据结构,数据结构

             

2.2.4左右双旋

  （4）左右双旋转（Left Right Double Rotation）：先进行左单旋转，再进行右单旋转。当新节点cur插入在的右子树的左侧时，先进行左单旋转，再进行右单旋转。

【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改,数据结构,数据结构

             

全部源码

#pragma once

#include<assert.h>

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:
	//AVL树插入一个节点
	bool AVLInsert(const pair<K, V>& kv)
	{
		//创建cur指向根节点
		Node* cur = _root;
		Node* parent = nullptr;

		//如果AVL树为空，直接返回创建的新节点
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		
		//如果AVL树不为空，寻找可以插入的节点
		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;

		//AVL树要保持平衡，控制平衡因子为-1、0、1
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else if (cur == parent->_right)
			{
				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)//左旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)//右旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋
				{
					RotateLR(parent);
				}

				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}

	//左旋
	void RotateL(Node* parent)
	{
		//创建cur节点和父节点
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		//将右子树的左节点连接在parent的右节点上
		parent->_right = curleft;//关键步骤1
		if (curleft)//如果右子树的左节点不为空，连接一下父节点
		{
			curleft->_parent = parent;
		}

		//将父节点断开连接到原来右节点的左子树上，降低二叉树高度
		cur->_left = parent;//关键步骤2

		//仍需要处理特殊情况
		//如果原父节点不为_root,保存父节点的父节点
		Node* ppnode = parent->_parent;
		
		//两个节点连接
		parent->_parent = cur;

		//如果父节点为_root，直接更新
		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else//如果父节点不为_root，需要重新连接
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else//判断是父父节点的左节点还是右节点
			{
				ppnode->_right = cur;

			}

			//反转将cur节点连接父节点
			cur->_parent = ppnode;
		}

		//更新平衡因子
		parent->_bf = cur->_bf = 0;
	}

	//右旋
	void RotateR(Node* parent)
	{
		//取子节点和子节点中的最大节点，作为父节点的左子树
		Node* cur = parent->_left;
		Node* curright = cur->_right;

		//将父节点和左子树中的最大节点连接，降低层高
		parent->_left = curright;//重要步骤1
		if (curright)
		{
			curright->_parent = parent;
		}

		//将子节点作为根，并将原来父节点连接在子节点的右节点
		cur->_right = parent;//重要步骤2

		//上面的代码基本可以完成右旋操作，但是还要考虑parent是否为_root
		Node* ppnode = parent->_parent;

		parent->_parent = cur;

		if (ppnode == nullptr)//parent为_root
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else//parent不为_root
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else//判断cur节点在原来子树的右边还是左边，并且连接
			{
				ppnode->_right = cur;
			}

			cur->_parent = ppnode;
		}

		//右旋完成，更新平衡因子
		parent->_bf = cur->_bf = 0;
	}

	//右左双旋
	void RotateRL(Node* parent)
	{
		//找到双旋节点
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		int bf = curleft->_bf;//记录平衡因子

		RotateR(parent->_right);//先右旋cur，让节点保持在一条直线上
		RotateL(parent);//左旋parent

		//不同情况更新不同的平衡因子
		if (bf == 0)//新增的节点就是所需要右左旋的节点
		{
			cur->_bf = 0;
			curleft->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)//新增节点的父节点平衡因子为1，新增在了左边
		{
			cur->_bf = 0;
			curleft->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)//新增节点的父节点平衡因子为-1，新增在了右边
		{
			cur->_bf = 1;
			curleft->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	//左右双旋
	void RotateLR(Node* parent)
	{
		//找到双旋节点
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		int bf = curright->_bf;

		RotateL(parent->_left);//先右旋
		RotateR(parent);//再左旋

		//更新平衡因子，新增节点更新位置不同，节点的平衡因子也不同
		if (bf == 0)
		{
			cur->_bf = 0;
			curright->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			cur->_bf = -1;
			curright->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			cur->_bf = 0;
			curright->_bf = 0;
			parent->_bf = 1;
		}
	}

	//求AVL树高
	int AVLHeight()
	{
		return _AVLHeight(_root);
	}

	int _AVLHeight(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		int leftHeight = _AVLHeight(root->_left);
		int rightHeight = _AVLHeight(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	//判断AVL树是否平衡
	bool AVLIsBalance()
	{
		return _AVLIsBalance(_root);
	}

	bool _AVLIsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		int leftHeight = _AVLHeight(root->_left);
		int rightHeight = _AVLHeight(root->_right);

		if (rightHeight - leftHeight != root->_bf)
		{
			cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;
			return false;
		}

		return abs(rightHeight = leftHeight) < 2 && _AVLIsBalance(root->_left)&& _AVLIsBalance(root->_right);
	}

private:
	Node* _root = nullptr;
};

到了这里，关于【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】平衡二叉树（AVL树）

    【数据结构与算法】平衡二叉树（AVL树）

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

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

    数据结构07：查找[C++][平衡二叉排序树AVL]

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

    2024年02月11日
    浏览(37)
  • 计算机基础---＞数据结构（6）【AVL树（平衡二叉树）】

    计算机基础---＞数据结构（6）【AVL树（平衡二叉树）】

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

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

    数据结构奇妙旅程之二叉平衡树进阶---AVL树

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

    2024年03月13日
    浏览(75)
  • C/C++数据结构（十一）—— 平衡二叉树（AVL树）

    C/C++数据结构（十一）—— 平衡二叉树（AVL树）

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

    2024年02月02日
    浏览(36)
  • 【C++】AVL（平衡二叉搜索树）树的原理及实现

    【C++】AVL（平衡二叉搜索树）树的原理及实现

    文章目录 一、引言 二、AVL树的概念 三、AVL树的插入 3、1 AVL树的简单插入 3、2 旋转分类  3、2、1 新节点插入较高右子树的右侧：左单旋 3、2、2 新节点插入较高左子树的左侧：右单旋 3、2、3 新节点插入较高左子树的右侧：左右双旋（先左后右） 3、2、4 新节点插入较高右

    2024年02月13日
    浏览(33)
  • 【数据结构】7.平衡搜索树（AVL树和红黑树）

    【数据结构】7.平衡搜索树（AVL树和红黑树）

    对于普通的搜索树，如果一直插入比第一个元素小的元素，它会退化成一个无限向左下角眼神的单链表，使得时间复杂度退化为O(n)。如果我们在插入时保持树的结构是平衡的，则可以保证查找、插入和删除的时间复杂度有对数级的时间性能，下面讲到的AVL树和红黑树都是平衡

    2024年02月08日
    浏览(31)
  • 数据结构之平衡二叉树的平衡调整

    数据结构之平衡二叉树的平衡调整

    1：LL型调整 2：RR型调整 3：LR型调整 4：RL型调整 5：总结 作者约定：将导致不平衡的结点称作 被破坏者 ，破坏了结点的平衡的结点成为 破坏者 ，经过调整可以让该树平衡的结点称为 调整结点 。 LL型不平衡调整方法：以调整结点为中心，进行右旋操作，就可以使树平衡。

    2024年02月09日
    浏览(33)
  • 数据结构和算法学习记录——平衡二叉树（基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度）

    数据结构和算法学习记录——平衡二叉树（基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度）

    目录 基本介绍 平衡因子 平衡二叉树  平衡二叉树的高度  什么是平衡二叉树？ 以一个例子来解释一下： 搜索树结点按不同的插入次序，将会导致不同的深度和平均查找长度ASL   在二叉搜索树中查找一个元素：  （a）要找到Jan，需要查找一次；要找到Feb，需要查找两次；

    2023年04月26日
    浏览(49)
  • 【数据结构】二叉排序树——平衡二叉树的调整

    【数据结构】二叉排序树——平衡二叉树的调整

    参考视频： 懒猫老师-数据结构-(59)平衡二叉树【互动视频】 （1）什么是平衡二叉树 平衡二叉树（Balanced Binary Tree）是一种特殊的二叉查找树，它的目的是保持树的高度尽量平衡，以保证查找、插入、删除等操作的时间复杂度为 O(log n)。 常见的平衡二叉树算法包括 AVL 树、红

    2024年02月04日
    浏览(32)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包