C++&&数据结构——AVL树

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

一,关于AVL树

根据前面对二叉搜索树的学习我们可以了解到二叉搜索树可以提高查找的效率,但是如果数据本身有序,搜索树将退化成单支树,查找时相当于顺序表查找,效率低下,如下图:

C++&&数据结构——AVL树,数据结构

为了解决上面的问题,来自俄罗斯的两位天才数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种方法:当二叉搜索树中插入新节点后,如果能保证每个节点的左右子树高度之差绝对值不超过1,即可降低树的高度,减少平均搜索长度。这就是AVL树,也称平衡二叉搜索树

AVL树具有以下性质:

①它左右子树都是AVL树

②左右子树高度差绝对值不超过1 (这里高度差我们简称为平衡因子)

下面就是一个典型的AVL树:

C++&&数据结构——AVL树,数据结构

二,AVL树节点和结构定义

2.1 节点定义

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

2.2 结构定义

template<class K,class V>
struct AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:

private:
    Node* _root = nullptr;
}

三,AVL树插入*

3.1 树的插入与平衡因子的更新

AVL树的插入和前面的二叉搜索树大体相同,只是需要多维护parent指针,更新判断平衡因子以及旋转

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;
	}
	//插入后要维护parent,反向链接
	cur->_parent = parent;

	//插入完成,接下来控制平衡//
	//更新平衡因子,如果更新过后,平衡因子没有出现问题,说明插入对树结构没有影响,不需要处理 bf的绝对值<=1
	//①新增在右,parebt->bf++; 新增在左,parent->bf--
	//②更新后parent->bf == 1 or -1,说明parent插入前的平衡因子是0,说明左右子树高度相等,插入后有一边高,parent的高度变了,需要继续往上更新
	//③更新后parent->bf ==0,说明parent插入前的平衡因子是1 or -1,左右子树一边高一边低,插入后一样高了,不需要往上更新
	//④更新后parent->bf == 2 or -2,说明之前是1或-1,已经是平衡的临界值,已打破平衡,parent所在的子树需要旋转处理。
	while (parent)//往上更新平衡因子,并判断是否需要旋转
	{
		//规则①
		if (cur == parent->_right)
		{
			parent->_bf++;
		}
		else
		{
			parent->_bf--;
		}
		//规则②
		if (parent->_bf == 0)
		{
			break;//不需要更新,跳出循环
		}
		//规则③
		else if (abs(parent->_bf) == 1)
		{
			parent = parent->_parent;//往上跳,利用循环持续更新平衡因子
			cur = cur->_parent;
		}
        //规则④
		else if (abs(parent->_bf) == 2)//已出现问题,需要旋转处理,目的是让这棵树平衡,其次使树的高度恢复正常
		{
			//这部分是旋转的具体实现部分
            //具体看下面的旋转部分
		}
		else
		{
			assert(false);//错误,直接报错
		}
	}
	return true;
}

3.2 树的旋转

3.2.1 右单旋

C++&&数据结构——AVL树,数据结构

我们在a子树插入一个节点,那么a的子树高度从h变为h+1,导致父节点平衡因子减一变成-1,祖父节点平衡因子也减一变成-2,绝对值大于1了,引发右旋转,如上图,需要改变的指针已用不同颜色标出,具体实现如下代码:

if (parent->_bf == -2 && cur->_bf == -1)
{
	RotateR(parent);
}

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

	parent->_left = subLR;
	//subLR可能是空
	if (subLR)
	{
		subLR->_parent = parent;
	}
	//记录一下要旋转的parent节点的_parent,用于当parent是子树根时的调整
	Node* ppNode = parent->_parent;

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

	//parent是整颗树的根
	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}
		subL->_parent = ppNode;
	}
	//调整sub和parent的平衡因子
	subL->_bf = parent->_bf = 0;
}

3.2.2 左单旋

C++&&数据结构——AVL树,数据结构

如图所示,我们在c子树插入一个节点,和右单选情况一样,导致祖父节点平衡因子绝对值大于1了,需要旋转处理,需要处理的指针已用不同颜色标出,具体代码实现如下:

else if (parent->_bf == 2 && cur->_bf == 1)
{
	RotateL(parent);
}

void RotateL(Node* parent)
{
	Node* subR = parent->_right; //结合图来看
	Node* subRL = subR->_left;

	parent->_right = subRL; 
	//subRL可能是空
	if (subRL) //维护subRL的parent
	{
		subRL->_parent = parent;
	}
	//记录一下要旋转的parent节点的_parent,用于当parent是子树根时的调整
	Node* ppNode = parent->_parent;

	subR->_left = parent;
	parent->_parent = subR; //维护原来parent的parent
	//parent是整棵树的根
	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else//parent是子树的根
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subR;
		}
		else
		{
			ppNode->_right = subR;
		}
		subR->_parent = ppNode;
	}
	//调整sunR和parent的平衡因子
	subR->_bf = parent->_bf = 0;
}

3.2.3 左右双旋

C++&&数据结构——AVL树,数据结构

 如上图所示,左右双旋其实就是先左单旋转再右单旋,先在b子树插入一个值,导致祖父节点平衡因子大于1,(这种情况比较复杂,建议多把流程图看几遍)我们先以30为子树根节点进行左旋,使树的“中间高”变为“一边高”,然后再以90为根进行右单旋转达到平衡,具体代码实现如下:

else if (parent->_bf == -2 && cur->_bf == 1)
{
	RotateLR(parent);
}

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

	RotateL(parent->_left);//复用
	RotateR(parent);

	//平衡因子的更新
	if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
	}
	else if(bf ==0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

3.3.4 右左双旋

C++&&数据结构——AVL树,数据结构

右左双旋和前面的差不多,直接看图理解即可,具体代码实现如下:文章来源地址https://www.toymoban.com/news/detail-806399.html

else if (parent->_bf == 2 && cur->_bf == -1)
{
	RotateRL(parent);
}

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

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

	if (bf == 1)//在c处插入
	{
		subR->_bf = 0;
		parent->_bf = -1;
		subRL->_bf = 0;
	}
	else if(bf == -1)
	{
		subR->_bf = 1;
		parent->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

四,AVL树其他接口实现

4.1 打印函数

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

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

	    _InOrder(root->_left);
	    cout << root->_kv.first << ":" << root->_kv.second << endl;
	    _InOrder(root->_right);
    }

4.2 判断平衡因子函数

private:
    int Height(Node* root)
    {
	    if (root == nullptr)
		    return 0;

	    return max(Height(root->_left),Height(root->_right)) + 1;
    }
    //判断平衡因子函数
    bool _IsBalance(Node* root) //不能直接检查平衡因子,因为是我们自己更新的,无法保证全部更新正确,所以需要老老实实去求高度
    {
	    if (root == nullptr) //空树也可以认为是平衡树
		    return true;

	    int leftHt = Height(root->_left);
	    int rightHt = Height(root->_right);
	    int diff = rightHt - leftHt;

	    if (diff != root->_bf) //在判断是否是AVL树的同时,检查平衡因子是否有问题,防止蝴蝶效应
	    {
		    cout << root->_kv.first << "平衡因子错误" << endl;
		    return false;
	    }

	    return abs(diff) < 2
		    && _IsBalance(root->_left)
		    && _IsBalance(root->_right);//还需要递归去看子树
    }

五,AVL树源代码与测试代码

 头文件

#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
#include<time.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>
struct 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;
		}
		//插入后要维护parent,反向链接
		cur->_parent = parent;

		//插入完成,接下来控制平衡//
		//1,更新平衡因子,如果更新过后,平衡因子没有出现问题,说明插入对树结构没有影响,不需要处理 bf的绝对这<=1
		//①新增在右,parebt->bf++;新增在左,parent->bf--
		//②更新后parent->bf == 1 or -1,说明parent插入前的平衡因子是0,说明左右子树高度相等,插入后有一边高,parent的高度变了,需要继续往上更新
		//③更新后parent->bf ==0,说明parent插入前的平衡因子是1 or -1,左右子树一边高一边低,插入后一样高了,不需要往上更新
        //④更新后parent->bf == 2 or -2,说明之前是1或-1,已经是平衡的临界值,已打破平衡,parent所在的子树需要旋转处理。
		while (parent)//往上更新平衡因子,并判断是否需要旋转
		{
			//规则①
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}
			//在矮的那边插入了一个
			if (parent->_bf == 0)
			{
				break;//不需要更新,跳出循环
			}
			//parent所在的子树高度变了,需要继续更新
			else if (abs(parent->_bf) == 1)
			{
				parent = parent->_parent;//往上跳
				cur = cur->_parent;
			}
			else if (abs(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)
				{
					RotateLR(parent);
				}
				//右左双旋转
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);//错误,直接报错
			}
		}
		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
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;

		return max(Height(root->_left),Height(root->_right)) + 1;
	}
	//判断平衡因子函数
	bool _IsBalance(Node* root) //不能直接检查平衡因子,因为是我们自己更新的,无法保证全部更新正确,所以需要老老实实去求高度
	{
		if (root == nullptr) //空树也可以认为是平衡树
			return true;

		int leftHt = Height(root->_left);
		int rightHt = Height(root->_right);
		int diff = rightHt - leftHt;

		if (diff != root->_bf) //在判断是否是AVL树的同时,检查平衡因子是否有问题,防止蝴蝶效应
		{
			cout << root->_kv.first << "平衡因子错误" << endl;
			return false;
		}

		return abs(diff) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);//还需要递归去看子树
	}
private:
	//旋转的价值和意义
	// ①使子树保持平衡
	// ②使高度恢复到插入之前的样子
	
	//左旋转函数
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right; //结合图来看
		Node* subRL = subR->_left;

		parent->_right = subRL; 
		//subRL可能是空
		if (subRL) //维护subRL的parent
		{
			subRL->_parent = parent;
		}
		//记录一下要旋转的parent节点的_parent,用于当parent是子树根时的调整
		Node* ppNode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR; //维护原来parent的parent
		//parent是整棵树的根
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else//parent是子树的根
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
		//调整sunR和parent的平衡因子
		subR->_bf = parent->_bf = 0;
	}

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

		parent->_left = subLR;
		//subLR可能是空
		if (subLR)
		{
			subLR->_parent = parent;
		}
		//记录一下要旋转的parent节点的_parent,用于当parent是子树根时的调整
		Node* ppNode = parent->_parent;

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

		//parent是整颗树的根
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
		//调整sub和parent的平衡因子
		subL->_bf = 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 (bf == 1)//板书里的c处插入
		{
			parent->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)//从b处插入
		{
			/*parent->_bf = 0;
			subL->_bf = 1;*/

			parent->_bf = 1;
			subL->_bf = 0;
		}
		else if(bf ==0)//板书的第三种情况
		{
			parent->_bf = 0;
			subL->_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)//在c处插入
		{
			subR->_bf = 0;
			parent->_bf = -1;
			subRL->_bf = 0;
		}
		else if(bf == -1)
		{
			subR->_bf = 1;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
private:
	Node* _root = nullptr;
};

测试代码

#include"AVLTree.h"
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;

void TestAVLTree1()
{
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };//专门用来测试双旋平衡因子的测试用例
	//int a[] = { 16,3,7,11,9,26,8,14,15 };
	AVLTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
	}
	t1.InOrder();
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

void TestAVLTree2()//上随机值来当测试用例
{
	size_t N = 10000;
	srand(time(0));
	AVLTree<int, int> t1;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand();//产生随机值
		t1.Insert(make_pair(x, i));
		//关掉srand创造闭线条件,每次插入值都调用IsBalabce,找到哪个值插入时导致问题
		/*bool ret = t1.IsBalance();
		if (ret == false)
		{
			int u = 1;
		}
		else
		{
			cout << "Insert:" << x << "IsBalance:" << ret << endl;
		}*/
	}
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

//高度平衡二叉搜索树
int main()
{
	TestAVLTree2();
	return 0;
}

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

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

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

相关文章

  • C++&&数据结构——AVL树

    根据前面对二叉搜索树的学习我们可以了解到二叉搜索树可以提高查找的效率,但是如果数据本身有序,搜索树将退化成单支树,查找时相当于顺序表查找,效率低下,如下图: 为了解决上面的问题,来自俄罗斯的两位天才数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种方

    2024年01月19日
    浏览(66)
  • 数据结构进阶(一):AVL树

    所谓的AVL树也叫做高度平衡的二叉搜索树。 啥是高度平衡的二叉搜索树? 高度平衡的二叉搜索树: 意味着左右子树的高度最大不超过一 。 我们先来回顾一下二叉搜索树的概念: 二叉搜索树又称二叉排序树,它或者是一棵空树 ,或者是具有以下性质的二叉树: 若它的左子树

    2024年02月12日
    浏览(36)
  • 【1++的数据结构】之AVL树

    👍作者主页:进击的1++ 🤩 专栏链接:【1++的数据结构】 在说AVL树之前我们先来说说为什么会出现AVL树。在前面的文章中我们讲过二叉搜索树,虽然查找,插入效率比较高,但其有个缺陷:在某些情况下其可能会成为一颗单支树或其他高度较高的树,这时我们的效率就比较

    2024年02月11日
    浏览(35)
  • 数据结构与算法——18.avl树

    这篇文章我们来看一下avl树 目录 1.概述 2.AVL树的实现 我们前面讲了二叉搜索树,它是有一个key值,然后比父节点key值大的在左边,小的在右边。这样设计是为了便于查找。但是有一种极端的情况,就是所有的结点都在一边,那查找的时间复杂度和在链表的查找时间复杂度就

    2024年02月07日
    浏览(39)
  • 【数据结构】—AVL树(C++实现)

                                                            🎬慕斯主页 : 修仙—别有洞天                                                  💜 本文前置知识:  搜索二叉树                                                       ♈️ 今日夜电波

    2024年02月05日
    浏览(50)
  • 数据结构:AVL树讲解(C++)

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

    2024年02月04日
    浏览(42)
  • 【高阶数据结构】AVL树详解(图解+代码)

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

    2024年02月13日
    浏览(50)
  • 【数据结构】AVL树的插入与验证

    普通的二叉搜索树在极端情况下会 退化成类似链表 的形状,从而使 查找的效率降低至O(N) 。 在此基础上,苏联与以色列数学家 A delson- V elskii 与 苏联数学家 L andis,发明出了 AVL树或者说平衡二叉搜索树。 注:第一张——Adelson-Velskii(1922-2014) ,第二张——Landis(1921——

    2024年02月09日
    浏览(37)
  • 数据结构(C++) : AVL树 实现篇

    目录 1.AVL树引入   (1)二叉搜索树缺点   (2)AVL树简介     [1]问题的解决     [2]AVL树的性质 2.AVL树的插入旋转操作   (1)术语解释   (2)左单旋     [1]插入到右侧的左边     [2]插入到右侧的右边   (3)右单旋     [1]插入到左侧的左边     [2]插入到左侧的右边   (4)左右双旋    

    2024年02月05日
    浏览(35)
  • [数据结构 C++] AVL树的模拟实现

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

    2024年02月03日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包