频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
数据结构与算法之平衡二叉树(AVL树)
2017-02-18 09:27:00           
收藏   我要投稿

数据结构与算法之平衡二叉树(AVL树):平衡二叉树(又称AVL树)是二叉查找树的一个进化体,由于二叉查找树不是严格的O(logN)。

所以引入一个具有平衡概念的二叉树,它的查找速度是O(logN)。所以在学习平衡二叉树之前,读者需要了解二叉查找树的实现,具体链接:二叉查找树

那么平衡是什么意思?我们要求对于一棵二叉查找树 ,它的每一个节点的左右子树高度之差不超过1。(对于树的高度的约定:空节点高度是0;叶子节点高度是1。)例如下图:

\

如果我们的二叉查找树是不平衡该怎么办?进行旋转。经过分析发现,出现不平衡无外乎四种情况,下面我们一一分析。不过在进行下面的内容前,我们先定义下树节点的代码:

 

typedef struct Node
{
	int m_key;
	int m_height;
	Node* m_lChild;
	Node* m_rChild;
	Node(int key)
	{
		m_key = key;
		m_height = 1;
		m_rChild = m_lChild = nullptr;
	}
}* PNode;

 

二:四种旋转算法

1.左左情况

\

节点3的左子树比右子树高2,左节点2的左子树比右子树高,这称为左左情况。

 

/* 左左情况 */
PNode LL_Rotate(PNode & p)
{
	cout << "LL\n";

	PNode top = p->m_lChild;
	p->m_lChild = top->m_rChild;
	top->m_rChild = p;

	p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
	top->m_height = max(Height(top->m_lChild), Height(top->m_rChild)) + 1;

	return top;
}

 

2.右右情况

\

节点3的右子树比左子树高2,右节点4的右子树比左子树高,这称为右右情况。

 

/* 右右情况 */
PNode RR_Rotate(PNode & p)
{
	cout << "RR\n";

	PNode top = p->m_rChild;
	p->m_rChild = top->m_lChild;
	top->m_lChild = p;

	p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
	top->m_height = max(Height(top->m_lChild), Height(top->m_rChild)) + 1;

	return top;
}

 

3.左右情况

\

节点5的左子树比右子树高2,左节点2的右子树比左子树高,这称为左右情况。

 

/* 左右情况 */
PNode LR_Rotate(PNode & p)
{
	cout << "LR\n";

	p->m_lChild = RR_Rotate(p->m_lChild);
	return LL_Rotate(p);
}

 

4.右左情况

\

节点15的右子树比左子树高2,右节点20的左子树比右子树高,这称为右左情况。

 

/* 右左情况 */
PNode RL_Rotate(PNode & p)
{
	cout << "RL\n";

	p->m_rChild = LL_Rotate(p->m_rChild);
	return RR_Rotate(p);
}

三:插入删除查找算法

 

在写之前,先看两个辅助函数:

 

/* 计算当前节点的高度 */
int Height(PNode & p)
{
	return (p == nullptr) ? 0 : p->m_height;
}

/* 找到该节点下的最小值节点,返回该最小值,注意参数不是引用传递 */
int FindMin(PNode  p)
{
	while (p->m_lChild)
		p = p->m_lChild;
	return p->m_key;
}

 

1.插入

利用递归,我们先将节点插入,插入成功即递归结束,在一层一层的结束时,然后判断经过的每个节点的左右子树高度差,进行调整。

 

/* 添加操作 */
bool Add(int key, PNode & p)
{
	if (p == nullptr)
	{
		p = new Node(key);
		return true;
	}
	else
	{
		if (key == p->m_key)//已存在,直接退出
			return false;

		if (key < p->m_key)//左子树
		{
			if (Add(key, p->m_lChild))//是否成功插入
			{
				if (Height(p->m_lChild) - Height(p->m_rChild) == 2)//高度差等于2,得旋转调整
				{
					if (key < p->m_lChild->m_key)
						p = LL_Rotate(p);//左左情况
					else
						p = LR_Rotate(p);//左右情况
				}
				p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;//更新高度
				return true;
			}
			else
				return false;
		}

		else //右子树
		{
			if (Add(key, p->m_rChild))
			{
				if (Height(p->m_lChild) - Height(p->m_rChild) == -2)
				{
					if (key > p->m_rChild->m_key)
						p = RR_Rotate(p);
					else
						p = RL_Rotate(p);
				}
				p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;//更新高度
				return true;
			}
			else
				return false;
		}
	}
}

2.删除

 

删除的节点一共三种类型:有左右孩子;没有左右孩子;只有一个孩子(左或者右)。

其中对于第一种情况,也就是该节点是有左右孩子的,这里用了一个巧妙的方法,利用转化的思想,具体看代码,把这种情况转化为第二种或第三种。

 

/* 删除操作 */
bool Delete(int key, PNode & p)
{
	if (p == nullptr)
		return false;
	else
	{
		if (key == p->m_key)//找到该点
		{
			if (p->m_lChild && p->m_rChild)//左右孩子都存在
			{
				p->m_key = FindMin(p->m_rChild);//找到该节点下的最小节点
				Delete(p->m_key, p->m_rChild);//转化为: 删除找到的这个最小节点
			}
			else if (!p->m_lChild && !p->m_rChild)//左右孩子都不存在
			{
				PNode t = p;//注意p是引用类型
				p = nullptr;
				delete t;
				return true;
			}
			else//左右孩子只存在一个
			{
				PNode t = p;
				p = (p->m_lChild == nullptr) ? p->m_rChild : p->m_lChild;
				delete t;
				return true;
			}
		}

		else if (key < p->m_key)//在左子树删除
		{
			if (Delete(key, p->m_lChild))
			{
				if (Height(p->m_lChild) - Height(p->m_rChild) == 2)
				{
					if (key < p->m_lChild->m_key)
						p = LL_Rotate(p);
					else
						p = LR_Rotate(p);
				}

				p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
				return true;
			}
			else
				return false;
		}
		else//在右子树删除
		{
			if (Delete(key, p->m_rChild))
			{
				if (Height(p->m_lChild) - Height(p->m_rChild) == -2)
				{
					if (key > p->m_rChild->m_key)
						p = RR_Rotate(p);
					else
						p = RL_Rotate(p);
				}
				p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
				return true;
			}
			else
				return false;
		}
	}
}

3.查找

 

 

/* 查找操作 */
bool Find(int key, PNode & p)
{
	if (p == nullptr)
		return false;
	else
	{
		if (key == p->m_key)
			return true;
		else if (key < p->m_key)
			return Find(key, p->m_lChild);
		else
			return Find(key, p->m_rChild);
	}
}

4.层次遍历

 

 

/* 层次遍历,和普通的层次遍历不一样,打印的结果模拟了树的形状 */
void PrintTheLevel(PNode & p, int level)
{
	if (p == nullptr || level <= 0)
		return;
	if (level == 1)
	{
		cout << p->m_key << "," << p->m_height << "  ";//输出节点及对应的高度
		return;
	}

	PrintTheLevel(p->m_lChild, level - 1);
	PrintTheLevel(p->m_rChild, level - 1);
}

void LevelOrder(PNode & p)
{
	int depth = Height(p);
	for (int i = 1; i <= depth; i++)
	{
		PrintTheLevel(p, i);//打印树的第i行
		cout << endl;
	}
}

四:完整代码

 

 

#define _CRT_SECURE_NO_DEPRECATE 
#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 

#include
#include
using namespace std;

typedef struct Node
{
	int m_key;
	int m_height;
	Node* m_lChild;
	Node* m_rChild;
	Node(int key)
	{
		m_key = key;
		m_height = 1;
		m_rChild = m_lChild = nullptr;
	}
}* PNode;

PNode pRoot = nullptr;//根节点


/* 计算当前节点的高度 */
int Height(PNode & p)
{
	return (p == nullptr) ? 0 : p->m_height;
}

/* 找到该节点下的最小值节点,返回该最小值,注意参数不是引用传递 */
int FindMin(PNode  p)
{
	while (p->m_lChild)
		p = p->m_lChild;
	return p->m_key;
}

/* 左左情况 */
PNode LL_Rotate(PNode & p)
{
	cout << "LL\n";

	PNode top = p->m_lChild;
	p->m_lChild = top->m_rChild;
	top->m_rChild = p;

	p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
	top->m_height = max(Height(top->m_lChild), Height(top->m_rChild)) + 1;

	return top;
}

/* 右右情况 */
PNode RR_Rotate(PNode & p)
{
	cout << "RR\n";

	PNode top = p->m_rChild;
	p->m_rChild = top->m_lChild;
	top->m_lChild = p;

	p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
	top->m_height = max(Height(top->m_lChild), Height(top->m_rChild)) + 1;

	return top;
}

/* 左右情况 */
PNode LR_Rotate(PNode & p)
{
	cout << "LR\n";

	p->m_lChild = RR_Rotate(p->m_lChild);
	return LL_Rotate(p);
}

/* 右左情况 */
PNode RL_Rotate(PNode & p)
{
	cout << "RL\n";

	p->m_rChild = LL_Rotate(p->m_rChild);
	return RR_Rotate(p);
}

/* 添加操作 */
bool Add(int key, PNode & p)
{
	if (p == nullptr)
	{
		p = new Node(key);
		return true;
	}
	else
	{
		if (key == p->m_key)//已存在,直接退出
			return false;

		if (key < p->m_key)//左子树
		{
			if (Add(key, p->m_lChild))//是否成功插入
			{
				if (Height(p->m_lChild) - Height(p->m_rChild) == 2)//高度差等于2,得旋转调整
				{
					if (key < p->m_lChild->m_key)
						p = LL_Rotate(p);//左左情况
					else
						p = LR_Rotate(p);//左右情况
				}
				p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;//更新高度
				return true;
			}
			else
				return false;
		}

		else //右子树
		{
			if (Add(key, p->m_rChild))
			{
				if (Height(p->m_lChild) - Height(p->m_rChild) == -2)
				{
					if (key > p->m_rChild->m_key)
						p = RR_Rotate(p);
					else
						p = RL_Rotate(p);
				}
				p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;//更新高度
				return true;
			}
			else
				return false;
		}
	}
}

/* 删除操作 */
bool Delete(int key, PNode & p)
{
	if (p == nullptr)
		return false;
	else
	{
		if (key == p->m_key)//找到该点
		{
			if (p->m_lChild && p->m_rChild)//左右孩子都存在
			{
				p->m_key = FindMin(p->m_rChild);//找到该节点下的最小节点
				Delete(p->m_key, p->m_rChild);//转化为: 删除找到的这个最小节点
			}
			else if (!p->m_lChild && !p->m_rChild)//左右孩子都不存在
			{
				PNode t = p;//注意p是引用类型
				p = nullptr;
				delete t;
				return true;
			}
			else//左右孩子只存在一个
			{
				PNode t = p;
				p = (p->m_lChild == nullptr) ? p->m_rChild : p->m_lChild;
				delete t;
				return true;
			}
		}

		else if (key < p->m_key)//在左子树删除
		{
			if (Delete(key, p->m_lChild))
			{
				if (Height(p->m_lChild) - Height(p->m_rChild) == 2)
				{
					if (key < p->m_lChild->m_key)
						p = LL_Rotate(p);
					else
						p = LR_Rotate(p);
				}

				p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
				return true;
			}
			else
				return false;
		}
		else//在右子树删除
		{
			if (Delete(key, p->m_rChild))
			{
				if (Height(p->m_lChild) - Height(p->m_rChild) == -2)
				{
					if (key > p->m_rChild->m_key)
						p = RR_Rotate(p);
					else
						p = RL_Rotate(p);
				}
				p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
				return true;
			}
			else
				return false;
		}
	}
}

/* 查找操作 */
bool Find(int key, PNode & p)
{
	if (p == nullptr)
		return false;
	else
	{
		if (key == p->m_key)
			return true;
		else if (key < p->m_key)
			return Find(key, p->m_lChild);
		else
			return Find(key, p->m_rChild);
	}
}

/* 层次遍历,和普通的层次遍历不一样,打印的结果模拟了树的形状 */
void PrintTheLevel(PNode & p, int level)
{
	if (p == nullptr || level <= 0)
		return;
	if (level == 1)
	{
		cout << p->m_key << "," << p->m_height << "  ";//输出节点及对应的高度
		return;
	}

	PrintTheLevel(p->m_lChild, level - 1);
	PrintTheLevel(p->m_rChild, level - 1);
}

void LevelOrder(PNode & p)
{
	int depth = Height(p);
	for (int i = 1; i <= depth; i++)
	{
		PrintTheLevel(p, i);
		cout << endl;
	}
}

int main()
{


	
	return 0;
}

 

 

点击复制链接 与好友分享!回本站首页
上一篇:里氏替换原则详解--七大面向对象设计原则(2)
下一篇:命令式编程vs声明式编程
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站