AVl树
发布日期:2021-09-19 03:18:22 浏览次数:1 分类:技术文章

本文共 5297 字,大约阅读时间需要 17 分钟。

AVL树是高度平衡的二叉搜索树

特征:

1.左右子数的高度差不超过1(因为可能有4个节点)

2.树中每个左子树,右子树都是AVL树

3.每个节点都有一个平衡因子,(每个节点的平衡因子等于右子树的高度减去左子树的高度),每个节点的平衡因子为1/0/-1

效率:

AVL树的高度为N,其高度可以保持在log2^N ,插入,删除,查找等时间复杂度也都是log2^N

因为AVL是高度平衡的二叉搜索树,插入以后就可能会导致它不平衡,所以要进行旋转

1左旋:

void RotateL(Node* parent)	{		Node* SubR = parent->_right;		Node* SubRL = SubR->_left;		parent->_right = SubRL;		if (SubRL)		{			SubRL->_parent = parent;		}		SubR->_left = parent;		Node* ppNode = parent->_parent;		parent->_parent = SubR;		if (ppNode == NULL)		{			_root = SubR;			SubR->_parent = NULL;		}		else		{			if (ppNode->_left == parent)			{				ppNode->_left = SubR;			}			else			{				ppNode->_right = SubR;			}			SubR->_parent = ppNode;		}		SubR->_bf = parent->_bf =0	}

2.右旋

void RotateR(Node* parent)	{		Node* subL = parent->_left;		Node* subLR = subL->_right;		parent->_left = subLR;		if (subLR)			subLR->_parent = parent;		subL->_right = parent;		Node* ppNode = parent->_parent;		parent->_parent = subL;		if (ppNode == NULL)		{			_root = subL;			subL->_parent = NULL:		}		else		{			if (ppNode->_right = _root)			{				ppNode->_right = subL;			}			else				ppNode->_left = subL;			subL->_parent = ppNode;		}		subL->_bf = parent->_bf = 0;	}

3.左右双旋

void RotateLR(Node* parent)	{		Node* subL = parent->_left;		Node* subLR = parent->_right;		int bf = subLR->_bf;		RotateL(parent->_left);		RotateR(parent);		if (bf == 1)		{			subL->_bf = -1;			parent->_bf = 0		}		if (bf == -1)		{			subL->_bf = 0;			parent->_bf = 1;		}		else		{			subL->_bf = parent->_bf = 0;		}			subLR->bf = 0;	}

4.右左双旋

void RotateRL(Node* parent)	{		Node* subR = parent->_right;		Node* subRL = subR->_left;		int bf = subR->_bf;		RotateR(parent->_right);		RotateL(parent);		if (bf == 1)		{			parent->_bf = -1;			subRL->_bf = 0;		}		if (bf == -1)		{			parent->_bf = 0;			subRL->_bf = 1;		}		else		{			subR->_bf = parent->_bf = 0;		}		subRL->_bf = 0;	}

整体实现:

#include
using namespace std;template
struct AVLTreeNode{ K _key; V _value; AVLTreeNode
* _left; AVLTreeNode
* _right; AVLTreeNode
* _parent; int _bf; AVLTreeNode(const K& k, const V& v) : _key(key) , _value(value) , _left(NULL) , _right(NULL) , _parent(NULL) , _bf(0) {}};template
class AVLTree{ typedef AVLTreeNode
* Node;public: AVLTree()//构造函数 :_root(NULL) {}
bool Insert(const K& key, const V& value)//插入	{		if (_root == NULL)		{			_root = new Node(key, value);			return true;		}		Node* cur = _root;		Node* parent = NULL;		while (cur)                //二叉搜索树的特性,若key大于cur->_key则为右,小于则为左		{			if (cur->_key < key)			{				parent = cur;				cur = cur->_right;			}			if (cur->_key > key)			{				parent = cur;				cur = cur->_left;			}			else			{				return false;			}		}		cur = new Node(key, value);		if (parent->_key < key)		{			parent->_right = cur;			cur->_parent = parent;		}		else		{			parent->_left = cur;			cur->_parent = parent;		}
//插入后更新bf		while (parent)		{			if (cur == parent->_left)			{				parent->_bf--;			}			else			{				parent->_bf++			}			if (parent->_bf == 0)//若bf=0,则平衡
break;			if (parent->_bf == 1 || parent->_bf == -1)//等于1的话继续向上调整			{				cur = parent;				cur=parent->_parent;			}			else			{				if (parent->_bf == 2)				{					if (cur->_bf == 1)					{						RotateL(parent);//左旋					}					else      //cur->_bf==-1					{						RotateRL(parent);//右左双旋					}				}				else              //parent->_bf = -2				{					if (cur->_bf == -1)					{						RotateR(parent);//右旋					}					else					{						RotateLR(parent);//左右双旋					}				}				break;			}		}		return true;	}	void RotateL(Node* parent)//左	{		Node* SubR = parent->_right;		Node* SubRL = SubR->_left;		parent->_right = SubRL;		if (SubRL)		{			SubRL->_parent = parent;		}		SubR->_left = parent;		Node* ppNode = parent->_parent;		parent->_parent = SubR;		if (ppNode == NULL)		{			_root = SubR;			SubR->_parent = NULL;		}		else		{			if (ppNode->_left == parent)			{				ppNode->_left = SubR;			}			else			{				ppNode->_right = SubR;			}			SubR->_parent = ppNode;		}		SubR->_bf = parent->_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* ppNode = parent->_parent;		parent->_parent = subL;		if (ppNode == NULL)		{			_root = subL;			subL->_parent = NULL:		}		else		{			if (ppNode->_right = _root)			{				ppNode->_right = subL;			}			else				ppNode->_left = subL;			subL->_parent = ppNode;		}		subL->_bf = parent->_bf = 0;	}	void RotateLR(Node* parent)	{		Node* subL = parent->_left;		Node* subLR = parent->_right;		int bf = subLR->_bf;		RotateL(parent->_left);		RotateR(parent);		if (bf == 1)		{			subL->_bf = -1;			parent->_bf = 0		}		if (bf == -1)		{			subL->_bf = 0;			parent->_bf = 1;		}		else		{			subL->_bf = parent->_bf = 0;		}			subLR->bf = 0;	}	void RotateRL(Node* parent)	{		Node* subR = parent->_right;		Node* subRL = subR->_left;		int bf = subR->_bf;		RotateR(parent->_right);		RotateL(parent);		if (bf == 1)		{			parent->_bf = -1;			subRL->_bf = 0;		}		if (bf == -1)		{			parent->_bf = 0;			subRL->_bf = 1;		}		else		{			subR->_bf = parent->_bf = 0;		}		subRL->_bf = 0;	}protected:	void _Inorder(Node* root)	{		if (root = NULL)		{			return;		}		_Inorder(root->_left);		cout << root->_key << ;		_Inorder(root->right);	}private:	Node* _root;};

转载地址:https://blog.csdn.net/audience_fzn/article/details/78432936 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:STL--Vector
下一篇:类和对象2-默认成员函数(构造析构)

发表评论

最新留言

不错!
[***.144.177.141]2024年03月24日 15时48分00秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

chmod 赋权所有_chmod 权限 命令详细用法 2019-04-21
html代码翻译_[译]您知道 HTML 的键盘标签吗? 2019-04-21
html抽奖代码_JavaScript高手之路:封装抽奖效果 2019-04-21
hadoop 3.3 一直停留在running wordcount_蛋价持续下跌,今日跌破3.3元大关!深秋季节价格还能反弹吗?... 2019-04-21
的流程图做完后如何保存_2019超火的半永久眉是哪款?做完后我们如何护理?... 2019-04-21
去除logo 高德地图api_深圳品牌logo升级如何保持原型的同时更具创新? 2019-04-21
二重积分转换成极坐标_二重积分转换极坐标r的范围如何确定? 2019-04-21
python中倒背如流_八字基础知识--倒背如流篇 2019-04-21
以太坊地址和公钥_以太坊地址是什么 2019-04-21
linux查看wifi信号命令_linux – 获取WIFI信号强度 – 寻求最佳方式(IOCTL,iwlist(iw)等)... 2019-04-21
npm 不重启 全局安装后_解决修复npm安装全局模块权限的问题 2019-04-21
vs格式化json 不生效_vs code 格式化 json 配置 2019-04-21
go 字符串反序列化成对象数组_Fastjson 1.2.24反序列化漏洞深度分析 2019-04-21
onmessage websocket 收不到信息_WebSocket断开重连解决方案,心跳重连实践 2019-04-21
hibernate mysql 缓存_hibernate和mysql的缓存问题,没辙了! 2019-04-21
abp框架 mysql_ABP框架使用Mysql数据库 2019-04-21
mysql树形递归删除_使用递归删除树形结构的所有子节点(java和mysql实现) 2019-04-21
linux mysql 不能连接远程_linux mysql 远程连接 2019-04-21
mysql $lt_mongodb中比较级查询条件:($lt $lte $gt $gte)(大于、小于)、查找条件... 2019-04-21
install python_Install python on AIX 7 2019-04-21