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

【数据结构】—AVL树（C++实现）

10月前 作者：慕斯( ˘▽˘)っ 分类：Toy博客 阅读(49) 违法举报

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

【数据结构】—AVL树（C++实现）,高阶数据结构炼体 锻体中,数据结构,c++

                                                      🎬慕斯主页：修仙—别有洞天

                                                 💜本文前置知识： 搜索二叉树

                                                      ♈️今日夜电波：Letter Song—ヲタみん

                                                                1:36━━━━━━️💟──────── 5:35
                                                                    🔄   ◀️   ⏸   ▶️    ☰  

                                      💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍

目录

一、前言          

        AVL树的概念

        AVL树同二叉搜索树的异同 

二、AVL树的实现

         节点的定义

         AVL树的初始化定义

         AVL树的插入（重点及难点！！！） 

         插入大致步骤

        根据规则找节点

         插入并且链接节点

         向上更新bf（平衡因子）的值

        左单旋

        右单旋

        左右双旋 

        右左双旋 

判断是否符合AVL树

三、整体代码 

一、前言          

        本文是基于二叉搜索树的知识前提下对于AVL树进行叙述的，主要叙述的方面在于AVL树的插入方面，因为AVL树同二叉搜索树的最大区别就在于插入的操作和删除操作，删除操作也是类似的，但是难就难在更新平衡因子，后续会补上。而对于其他的操作如：二叉搜索树的查找操作等等都是相似的，因此本文主要介绍AVL树的插入操作。

        AVL树的概念

         AVL树是一种自平衡二叉搜索树，它的特点是保证了每个节点的左右子树的高度差不超过1。它在插入和删除时会自动平衡，以保持树的高度始终在log N的范围内，从而保证了查找、插入、删除等操作的高效性。AVL树的名字来源于其发明者G.M.Adelson-Velsky和E.M.Landis的姓氏缩写。以下为一颗AVL树：

【数据结构】—AVL树（C++实现）,高阶数据结构炼体 锻体中,数据结构,c++

        AVL树同二叉搜索树的异同 

AVL树和二叉搜索树有很多相似之处，但也有许多不同之处。以下是它们的主要异同点：

相同点：

  1. 它们都是自平衡二叉搜索树，也就是说，在插入和删除节点后，它们能够保持一定的平衡性，从而保证查询操作的时间复杂度始终保持在O(logn)级别。
  2. 它们都遵循二叉搜索树的基本性质，即左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点。

不同点：

  1. 在AVL树中，除了左右子树高度差不能超过1之外，每个叶子节点还必须在左右子树的高度之间，而在二叉搜索树中则没有这样的限制。（AVL中通常定义一个bf值（balance factor）用于记录节点左右子树的高度差）
  2. 在AVL树中，任何路径上的节点数差异不能超过1，而在二叉搜索树中则没有这样的要求。
  3. 在插入和删除节点后，AVL树需要进行更多的旋转操作来恢复平衡，而二叉搜索树则不需要这样的步骤。
  4. AVL树更适合于查找操作，因为它通过严格的平衡性保证了查询操作的效率，而二叉搜索树更适合于插入和删除操作，因为它可以通过简单的旋转操作来快速调整树结构。

二、AVL树的实现

         节点的定义

         通过KV模型定义AVL树节点，定义三叉链的结构储存父节点以及左右子树节点的地址，定义了bf（平衡因子）用于记录节点右子树与左子树之差（右-左），通过构造函数初始化列表，特别要将bf置为0，如果不置0后续操作可能会出错（别问作者怎么知道的(〃＞皿＜)）。

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf; // balance factor

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

         AVL树的初始化定义 

// AVL: 二叉搜索树 + 平衡因子的限制
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
    // 在AVL树中插入节点
	bool Insert(const pair<K, V>& kv);
    
    // AVL树的验证
    bool _IsBalance(Node* root)
    {
        return _IsBalance(_root);
    }
    
private:
    // 右单旋
	void RotateR(Node* parent);
    // 左单旋
	void RotateL(Node* parent);
    // 右左双旋
	void RotateRL(Node* parent);
    // 左右双旋
	void RotateLR(Node* parent);
    // 求高度
	int _Height(Node* root );
    // 根据AVL树的概念验证pRoot是否为有效的AVL树
    bool _IsBalance(Node* root);

private:
	Node* _root = nullptr;
};

AVL树的插入（重点及难点！！！） 

         插入大致步骤

AVL树的插入操作可以分为以下几步：

  1. 向AVL树中插入一个新节点，首先找到该节点的位置。这可以通过比较新节点的值与当前节点的值来完成，直到找到一个空位置或者到达一个叶子节点为止。按照大往左，小往右，相等返回false的规则。
  2. 依次向下搜索直到找到相应的位置，就将新节点插入到这个位置，并且更新该节点的父节点和兄弟节点的指针。就将新节点插入到这个位置，然后向上更新节点的bf值。
  3. 插入完成后，需要检查新插入的节点是否破坏了AVL树的平衡性。如果破坏了平衡性，就需要执行一系列旋转操作来修复不平衡状态。具体来说，如果新插入的节点使得某个分支的深度增加了一级，那么可以执行一次相应的旋转操作：左旋、右旋、左右旋、右左旋，最后按要求更新各个节点的bf值。

以上就是AVL树的插入操作步骤。需要注意的是，每次插入操作都需要按照这些步骤来进行，才能保证AVL树的平衡性。

        根据规则找节点

         如果_root为空（即空树）则新建节点并返回。比较节点的值，如果插入节点大则往右子树遍历，小则往左子树遍历，如果与节点值相同则无需插入直接返回。后续找到相应的位置后就可跳出循环进行下一步操作。

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;
	}
}
         插入并且链接节点

         更新节点信息，新插入节点的_parent值，以及父节点链接他在左子树还是右子树的判断，链入AVL树中。

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
         向上更新bf（平衡因子）的值

在插入之前，parent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

        1. 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可。

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

此时：parent的平衡因子可能有三种情况：0，正负1， 正负2

        1. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功。

        2. 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新。

        3. 如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理。

while (parent)
{
	if (cur == parent->_left)//根据在左还是右改变bf值
	{
		parent->_bf--;
	}
	else
	{
		parent->_bf++;
	}

	if (parent->_bf == 0)//bf=0则向上都无需变化
	{
		break;
	}
	else if (parent->_bf == 1 || parent->_bf == -1)//bf变化向上遍历改变bf值
	{
		cur = parent;
		parent = parent->_parent;
	}
	else if (parent->_bf == 2 || parent->_bf == -2)//破坏了bf值需要-1<=bf<=1的区间，需要旋转矫正
	{
		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);
		}

		// 1、旋转让这颗子树平衡了
		// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
		break;
	}
	else
	{
		assert(false);//其它情况的bf值表示这颗avl树本身就有问题
	}
}

         左单旋

        由于我们每次插入都会进行调整操作，对此AVL树在新的节点插入前都是合法的，也就是说bf值只会在-1~1之间波动。 当 parent->_bf == 2 && cur->_bf == 1时，我们需要进行左单旋的操作以确保AVL树的合法性（也就是当父节点的右子树高时需要进行左单旋），以下为对此以下为大致的操作图：

【数据结构】—AVL树（C++实现）,高阶数据结构炼体 锻体中,数据结构,c++

        详细旋转过程： 

        对于左单旋操作，我们需要先记录几个节点，分别如下为parent、subR、subRL，因为我们主要是改变这三个的位置。在旋转完成后我们也通过图清晰可见，parent和subR的bf值都是0。

【数据结构】—AVL树（C++实现）,高阶数据结构炼体 锻体中,数据结构,c++

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

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)//判断节点subRL是否为空，防止出错
			subRL->_parent = parent;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}

		parent->_bf = subR->_bf = 0;
	}

        右单旋

        对于右单旋，操作同左单旋相似，也是需要记录三个节点：parent、subL、subLR,只不过此时我们是向右旋转。当 parent->_bf == -2 && cur->_bf == -1时，我们需要进行右单旋的操作以确保AVL树的合法性（也就是当父节点的左子树高时需要进行右单旋）。在旋转完成后我们也通过图清晰可见，parent和subR的bf值都是0。以下为对此以下为大致的操作图：

【数据结构】—AVL树（C++实现）,高阶数据结构炼体 锻体中,数据结构,c++

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

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		

		subL->_right = parent;
		
		Node* parentParent = parent->_parent;

		parent->_parent = subL;

		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}

		parent->_bf = subL->_bf = 0;
	}

        左右双旋 

         当parent->_bf == -2 && cur->_bf == 1时，也就意味着我们的插入操作在如下的b的位置，插入后的图为第二张图，对此我们仅仅只进行一次旋转是远远不够的，如下第三张图为以30为父节点（即subL）只进行了一次左单旋后所变化的图，如果我们仔细观察可以发现这非常符合需要右单旋的操作，因此，此时我们以90为父节点再进行一次右单旋操作。 当然双旋最重要的其实是bf值的确定，我们需要根据最开始的subLR的bf值来确定。

当bf == 0，则subLR自己就是新增因此
            parent->_bf = subL->_bf = subLR->_bf = 0;

当bf==-1，则subLR的左子树新增
           parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;

当bf==1，则subLR的右子树新增
           subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;

【数据结构】—AVL树（C++实现）,高阶数据结构炼体 锻体中,数据结构,c++

	void RotateLR(Node* parent)
	{
		//...
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

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

		if (bf == 0)
		{
			// subLR自己就是新增
			parent->_bf = subL->_bf = subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			// subLR的左子树新增
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			// subLR的右子树新增
			subL->_bf = -1;
			parent->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

          右左双旋 

        当parent->_bf == 2 && cur->_bf == -1时，我们需要进行右左双旋操作，当然同左右双旋一样，只进行一次旋转肯定是不够的，我们也可以猜到先对subR作为一次父节点进行右单旋，在再对parent进行左单旋。

当然双旋最重要的其实是bf值的确定，我们需要根据最开始的subRL的bf值来确定。

当bf == 0，则subRL自己就是新增
            parent->_bf = subR->_bf = subRL->_bf = 0;

当bf==-1，则subRL的左子树新增
            parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;

当bf==1，则subRL的右子树新增

            parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;

 【数据结构】—AVL树（C++实现）,高阶数据结构炼体 锻体中,数据结构,c++

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

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

		if (bf == 0)
		{
			// subRL自己就是新增
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

判断是否符合AVL树

        主要运用递归的思想，不多阐述，实在不明白可以画递归展开图。 

		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;
		}

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

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

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

三、整体代码 

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf; // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _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 (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;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		while (parent)
		{
			if (cur == parent->_left)//根据在左还是右改变bf值
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)//bf=0则向上都无需变化
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)//bf变化向上遍历改变bf值
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)//破坏了bf值需要-1<=bf<=1的区间，需要旋转矫正
			{
				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);
				}

				// 1、旋转让这颗子树平衡了
				// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
				break;
			}
			else
			{
				assert(false);//其它情况的bf值表示这颗avl树本身就有问题
			}
		}

		return true;
	}


	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	private:

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

			parent->_right = subRL;
			subR->_left = parent;

			Node* parentParent = parent->_parent;

			parent->_parent = subR;
			if (subRL)//判断节点subRL是否为空，防止出错
				subRL->_parent = parent;

			if (_root == parent)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (parentParent->_left == parent)//链接subR给父节点的父节点，需要判断是在左子树还是右子树
				{
					parentParent->_left = subR;
				}
				else
				{
					parentParent->_right = subR;
				}

				subR->_parent = parentParent;
			}

			parent->_bf = subR->_bf = 0;
		}


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

			parent->_left = subLR;
			if (subLR)
				subLR->_parent = parent;


			subL->_right = parent;

			Node* parentParent = parent->_parent;

			parent->_parent = subL;

			if (_root == parent)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				if (parentParent->_left == parent)
				{
					parentParent->_left = subL;
				}
				else
				{
					parentParent->_right = subL;
				}

				subL->_parent = parentParent;
			}

			parent->_bf = subL->_bf = 0;
		}

		void RotateRL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			int bf = subRL->_bf;

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

			if (bf == 0)
			{
				// subRL自己就是新增
				parent->_bf = subR->_bf = subRL->_bf = 0;
			}
			else if (bf == -1)
			{
				// subRL的左子树新增
				parent->_bf = 0;
				subRL->_bf = 0;
				subR->_bf = 1;
			}
			else if (bf == 1)
			{
				// subRL的右子树新增
				parent->_bf = -1;
				subRL->_bf = 0;
				subR->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}

		void RotateLR(Node* parent)
		{
			//...
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			int bf = subLR->_bf;

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

			if (bf == 0)
			{
				// subLR自己就是新增
				parent->_bf = subL->_bf = subLR->_bf = 0;
			}
			else if (bf == -1)
			{
				// subLR的左子树新增
				parent->_bf = 1;
				subL->_bf = 0;
				subLR->_bf = 0;
			}
			else if (bf == 1)
			{
				// subLR的右子树新增
				subL->_bf = -1;
				parent->_bf = 0;
				subLR->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;

			_InOrder(root->_left);
			cout << root->_kv.first << " ";
			_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;
		}

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

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

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

	private:
		Node* _root = nullptr;
};

                         感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！ 

                                       【数据结构】—AVL树（C++实现）,高阶数据结构炼体 锻体中,数据结构,c++

                                                                         给个三连再走嘛~  文章来源地址https://www.toymoban.com/news/detail-754481.html

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

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

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

相关文章

  • [数据结构 C++] AVL树的模拟实现

    [数据结构 C++] AVL树的模拟实现

    问题引入： 在上一篇文章中，我们提到了二叉搜索树在插入时，可能会形成单边树，会降低二叉搜索的性能。因此我们需要平衡二叉搜索树，降低二叉搜索树的高度，使得二叉搜索树趋于一颗完全二叉树的样子，这样就可以提高二叉搜索树的性能。本篇文章就来介绍一种平衡

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

    C++数据结构之平衡二叉搜索树（一）——AVL的实现（zig与zag/左右双旋/3+4重构）

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

    2024年02月13日
    浏览(38)
  • 数据结构：AVL树讲解（C++）

    数据结构：AVL树讲解（C++）

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

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

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

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

    2024年02月11日
    浏览(48)
  • 手撕哈希表（HashTable）——C++高阶数据结构详解

    手撕哈希表（HashTable）——C++高阶数据结构详解

    小编是双非本科大一菜鸟不赘述，欢迎米娜桑来指点江山哦（QQ：1319365055） 🎉🎉非科班转码社区诚邀您入驻🎉🎉 小伙伴们，打码路上一路向北，彼岸之前皆是疾苦 一个人的单打独斗不如一群人的砥砺前行 这是我和梦想合伙人组建的社区，诚邀各位有志之士的加入！！ 社

    2023年04月08日
    浏览(37)
  • 【C++高阶(三)】AVL树深度剖析&模拟实现

    【C++高阶(三)】AVL树深度剖析&模拟实现

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 如果你不知道什么是二叉搜索树 请一定先阅读这篇文章: 二叉搜索树深度剖析 为了解决二叉搜索树不稳定的问题 于是乎有人提出了AVL树结

    2024年02月05日
    浏览(45)
  • Java 数据结构篇-实现 AVL 树的核心方法

    Java 数据结构篇-实现 AVL 树的核心方法

    🔥博客主页： 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍   文章目录         1.0 AVL 树的说明         2.0 AVL 树的成员变量及其构造方法         3.0 实现 AVL 树的核心方法         3.1 获取当前节点的高度 height(AVLNode node)         3.2 更新当前节点的高度 updateHe

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

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

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

    2024年02月07日
    浏览(49)
  • 【数据结构】AVL树

    【数据结构】AVL树

    🐱作者：一只大喵咪1201 🐱专栏：《数据结构与算法》 🔥格言： 你只管努力，剩下的交给时间！ 我们知道，二叉搜索树的搜索效率非常高，平均时间复杂度是O(log 2 N)，但是当数据原本就有序时，插入二叉树中就会形成单支结构，此时搜索的时间复杂度就是O(N)。 为了避免

    2023年04月18日
    浏览(36)
  • 【数据结构】AVL 树

    【数据结构】AVL 树

    前面对 map / multimap / set / multiset 进行了简单的介绍【C++】map set，在其文档介绍中发现，这几个容器有个共同点是： 其底层都是按照二叉搜索树来实现的 ，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度

    2024年04月12日
    浏览(32)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包