数据结构浅析——AVL Tree

程序员文章站 2022-05-26 11:33:26

...

数据结构浅析——AVL Tree

今天我对AVL Tree的插入方式进行了研究，废话不多说直接进入正题。

AVL Tree是高度平衡的二叉搜索树，保留了搜索树中序遍历有序的特点，同时在每一个节点中加入了一个平衡因子，保证了树的高度平衡，搜索时的复杂度为O（log n）。

在插入时，每次插入都要更新相关的平衡因子并且检查相关节点的平衡因子是否异常（大于1或者小于-1），当平衡因子异常时就进行旋转操作来使得平衡恢复。

一、平衡因子

平衡因子是当前节点的右左子树的高度差，它的存在保证了每一个节点的左右子树的高度差值小于二，即这棵树最长分支和最短分支的差值小于2。

二、旋转

旋转就是平衡搜索树能够平衡的根本所在，旋转的方式保证了子树高度改变的同时，其中储存的数据依旧有序。

旋转主要有两种方式：左旋和右旋。

右旋：

数据结构浅析——AVL Tree

左旋：

数据结构浅析——AVL Tree

AVL Tree左右旋转方式高度对称，大家看见我甚至把图片反转一下就可以继续使用了，所以在就此书写代码时也十分方便，写完左旋照着左旋写右旋就好了。

那么光是左右旋转一下是不是这棵树就可以了呢？不是的，根据情况的不同有的树要进行两次旋转才能从新平衡起来，而有的树则需要反复旋转三次。

以下我均以左侧举例，右侧出现类似情况解决方式和左侧相同只是翻转过来而已。所以左侧较长时旋转有三种情况

数据结构浅析——AVL Tree

三、平衡因子在旋转后的改变。

在左旋时，旋转中心节点的平衡因子值只会出现0或1或-1，而父亲节点的值为2或1。

当父节点平衡因子等于2，子节点无论为何值时，或者父节点平衡因子等于一，而子节点等于0时，有如下公式：

父节点 -= 子结点的绝对值 + 1；

子节点--；

当父节点平衡银子等于1，且子节点等于1时，有如下公式：

父节点 -= 子结点的绝对值 + 1；

子节点 -= 2；

在右旋时类似。

照此就可以成功的构造出一个AVL Tree了，但是该树删除节点时也同样复杂，望诸君共勉。

以下为代码：

template<class K, class V>
struct node
{
	typedef node<K, V> nodetyp;
	K _key;
	V _val;
	nodetyp* _parent;
	nodetyp* _lefch;
	nodetyp* _rghch;
	int _equfac;		//左减右加   左边小右边大
	node(K k, V v = 0, nodetyp* p = NULL, nodetyp* l = NULL, nodetyp* r = NULL, int e = 0) :_key(k), _val(v), _lefch(l), _rghch(r), _parent(p), _equfac(e){}
};




//ST必须提供两个接口key()  and  val()
template<class K, class V, class ST>  
class AVL
{
public:
	typedef node<K, V> nodetyp;
	AVL() :_head(NULL){}
	AVL(const AVL& s);
	AVL(ST const* arr, size_t si);
	~AVL(){ clear(); }


	void clear(nodetyp* p = NULL)
	{
		if (p == NULL)
			p = _head;
		if (p == NULL)
			return;
		if (p->_lefch)
			clear(p->_lefch);
		if (p->_rghch)
			clear(p->_rghch);
		delete p;
	}
	size_t size(){ return thesize; }


	void push(const K& key, const V& val = 0)
	{
		if (_head == NULL)
		{
			_head = new nodetyp(key,val);
			thesize++;
			return;
		}
		nodetyp* tem = _head;
		while (tem)
		{
			if (key > tem->_key)
			{
				if (tem->_rghch == NULL)
				{
					tem->_rghch = new nodetyp(key, val, tem);
					for (nodetyp* i = tem->_rghch; i->_parent != NULL; i = i->_parent)
					{
						if (i->_parent->_lefch && i->_key == i->_parent->_lefch->_key)
							i->_parent->_equfac--;
						else if (i->_parent->_rghch && i->_key == i->_parent->_rghch->_key)
							i->_parent->_equfac++;
						if (i->_parent->_equfac == 0)
							break;
					}
					for (nodetyp* i = tem; i != NULL; i = i->_parent)
					{
						if (i->_equfac < -1 || i->_equfac > 1)
							rotates(i);
					}
					return;
				}
				else
				{
					tem = tem->_rghch;
				}
			}
			else if (key < tem->_key)
			{
				if (tem->_lefch == NULL)
				{
					tem->_lefch = new nodetyp(key, val, tem);
					for (nodetyp* i = tem->_lefch; i->_parent != NULL; i = i->_parent)
					{
						if (i->_parent->_lefch && i->_key == i->_parent->_lefch->_key)
							i->_parent->_equfac--;
						else if (i->_parent->_rghch && i->_key == i->_parent->_rghch->_key)
							i->_parent->_equfac++;
						if (i->_parent->_equfac == 0)
							break;
					}
					for (nodetyp* i = tem; i != NULL; i = i->_parent)
					{
						if (i->_equfac < -1 || i->_equfac > 1)
							rotates(i);
					}
					thesize++;
					return;
				}
				else
				{
					tem = tem->_lefch;
				}
			}
			else
				return;
		}
	}
	void push(const ST& nodeval)
	{
		if (_head == NULL)
		{
			_head = new nodetyp(nodeval.key(), nodeval.val());
			thesize++;
			return;
		}
		nodetyp* tem = _head;
		while (tem)
		{
			if (nodeval.key() > tem->_key)
			{
				if (tem->_rghch == NULL)
				{
					tem->_rghch = new nodetyp(nodeval.key(), nodeval.val(), tem);
					for (nodetyp* i = tem->_rghch; i->_parent != NULL; i = i->_parent)
					{
						if (i->_parent->_lefch && i->_key == i->_parent->_lefch->_key)
							i->_parent->_equfac--;
						else if (i->_parent->_rghch && i->_key == i->_parent->_rghch->_key)
							i->_parent->_equfac++;
						if (i->_parent->_equfac == 0)
							break;
					}
					for (nodetyp* i = tem; i != NULL; i = i->_parent)
					{
						if (i->_equfac < -1 || i->_equfac > 1)
							rotates(i);
					}
					
					thesize++;
					return;
				}
				else
				{
					tem = tem->_rghch;
				}
			}
			else if (nodeval.key() < tem->_key)
			{
				if (tem->_lefch == NULL)
				{
					tem->_lefch = new nodetyp(nodeval.key(), nodeval.val(), tem);
					for (nodetyp* i = tem->_lefch; i->_parent != NULL; i = i->_parent)
					{
						if (i->_parent->_lefch && i->_key == i->_parent->_lefch->_key)
							i->_parent->_equfac--;
						else if (i->_parent->_rghch && i->_key == i->_parent->_rghch->_key)
							i->_parent->_equfac++;
						if (i->_parent->_equfac == 0)
							break;
					}
					for (nodetyp* i = tem; i != NULL; i = i->_parent)
					{
						if (i->_equfac < -1 || i->_equfac > 1)
							rotates(i);
					}
					thesize++;
					return;
				}
				else
				{
					tem = tem->_lefch;
				}
			}
			else
				return;
		}
	}
	//void erase(const K& key);
	//void erase(const ST& nodeval);
	nodetyp* find(const K& key)
	{
		nodetyp* tem = _head;
		while (tem)
		{
			if (tem->_key == key)
				return tem;
			else if (key > tem->_key)
				tem = tem->_rghch;
			else
				tem = tem->_lefch;
		}
		return NULL;
	}


protected:
	nodetyp* _head;
	size_t thesize;


	void rotates(nodetyp* unequ)
	{
		if (unequ->_equfac < -1)
		{
			if (unequ->_lefch->_equfac < 1)
			{
				rghrot(unequ->_lefch);
			}
			else if (unequ->_lefch->_equfac == 1 && unequ->_lefch->_rghch->_equfac == -1)
			{
				rghrot(unequ->_lefch->_rghch->_lefch);
				lefrot(unequ->_lefch->_rghch);
				rghrot(unequ->_lefch);
			}
			else
			{
				lefrot(unequ->_lefch->_rghch);
				rghrot(unequ->_lefch);
			}
		}
		else if (unequ->_equfac > 1)
		{
			if (unequ->_rghch->_equfac > -1)
			{
				lefrot(unequ->_rghch);
			}
			else if (unequ->_rghch->_lefch->_equfac == 1)
			{
				lefrot(unequ->_rghch->_lefch->_rghch);
				rghrot(unequ->_rghch->_lefch);
				lefrot(unequ->_rghch);
			}
			else
			{
				rghrot(unequ->_rghch->_lefch);
				lefrot(unequ->_rghch);
			}
		}
	}
	void rghrot(nodetyp* n)
	{
		if (n->_parent == _head)
			_head = n;
		nodetyp* gref = n->_parent->_parent;
		nodetyp* fath = n->_parent;
		if (gref)
		{
			if (gref->_rghch == fath)
				gref->_rghch = n;
			else
				gref->_lefch = n;
		}
		n->_parent = gref;
		if (n->_rghch)
			n->_rghch->_parent = fath;
		fath->_lefch = n->_rghch;
		n->_rghch = fath;
		fath->_parent = n;
		if (fath->_equfac == -2 || (fath->_equfac == -1 && n->_equfac == 0))
		{
			fath->_equfac += (-(n->_equfac) + 1);
			n->_equfac++;
		}
		else
		{
			fath->_equfac += (-(n->_equfac) + 1);
			n->_equfac += 2;
		}
	}
	void lefrot(nodetyp* n)
	{
		if (n->_parent == _head)
			_head = n;
		int i = 0;
		if (n->_parent == _head)
			_head = n;
		nodetyp* gref = n->_parent->_parent;
		nodetyp* fath = n->_parent;
		if (gref)
		{
			if (gref->_rghch == fath)
				gref->_rghch = n;
			else
				gref->_lefch = n;
		}
			
		n->_parent = gref;
		if (n->_lefch)
			n->_lefch->_parent = fath;
		fath->_rghch = n->_lefch;
		fath->_parent = n;
		n->_lefch = fath;
		if (fath->_equfac == 2 || (fath->_equfac == 1 && n->_equfac == 0))
		{
			fath->_equfac -= ((n->_equfac) + 1);
			n->_equfac--;
		}
		else
		{
			fath->_equfac -= ((n->_equfac) + 1);
			n->_equfac -= 2;
		}
	}
};

上一篇：栈实现中缀表达式转换成后缀表达式并计算

下一篇：【数据结构基础笔记】第二章线性表之顺序表

数据结构浅析——AVL Tree

数据结构与算法AVL树的Python实现

图解数据结构树之AVL树

数据结构与算法AVL树的Python实现

[一]class 文件浅析 .class文件格式详解字段方法属性常量池字段 class文件属性表数据类型数据结构

浅析go中的map数据结构字典

图解数据结构树之AVL树

Python嵌套式数据结构实例浅析

数据结构之---C语言实现平衡二叉树（AVL树）

数据结构学习-AVL平衡树

扁平数据结构转Tree

数据结构浅析——AVL Tree

数据结构与算法AVL树的Python实现

图解数据结构树之AVL树

数据结构与算法AVL树的Python实现

[一]class 文件浅析 .class文件格式详解 字段方法属性常量池字段 class文件属性表 数据类型 数据结构

浅析go中的map数据结构字典

图解数据结构树之AVL树

Python嵌套式数据结构实例浅析

数据结构之---C语言实现平衡二叉树（AVL树）

数据结构学习-AVL平衡树

扁平数据结构转Tree

[一]class 文件浅析 .class文件格式详解字段方法属性常量池字段 class文件属性表数据类型数据结构