平衡搜索树之AVLTree

今天我想要在这里写下个人觉得比较难的数据结构---AVL树的一些些心得。

一。了解一种新的数据结构,首先要搞懂它的定义

AVL树又称为高度平衡的二叉搜索树,是1962年有俄罗斯的数学家G.M.Adel'son-Vel'skii和E.M.Landis提出来的。它能保持二叉树的高度
平衡,尽量降低二叉树的高度,减少树的平均搜索长度。所以严格点来说,对于一棵搜索二叉树,能达到O(logn)的只是AVL树,因为他对于二叉树的深度控制的最为严格
,那么这是为什么呢?让我们来看看AVL树的性质

  1. 左子树和右子树的高度之差的绝对值不超过1
  2.  树中的每个左子树和右子树都是AVL树
  3.  每个节点都有一个平衡因子(balance factor--bf),任一节点的平衡因子是-1,0,1。(每个节点的平衡因子等于右子树的高度减去左子树的高度 )

整棵二叉树的每个节点都要满足这三个条件才算是一棵AVL树。其中第三个条件是核心,可以说AVL树是围绕平衡因子建树的。

在这里要说一说AVL树的优点

我们先来看看二叉搜索树吧(因为AVL树本质上是一棵二叉搜索树),假设有这么一种极端的情况:二叉搜索树的结点为0 1、2、3、4,也就是:


   聪明的你是不是发现什么了呢?显而易见——这棵二叉搜索树其实等同于一个链表了,也就是说,它在查找上的优势已经全无了——在这种情况下,查找一个结点的时间复杂度是O(N)!

好,那么假如是AVL树(别忘了AVL树还是二叉搜索树),则会是:


可以看出,AVL树的查找平均时间复杂度要比二叉搜索树低——它是O(logN)。也就是说,在大量的随机数据中AVL树的表现要好得多。


二。AVL实现

     话不多说,开始分析AVL的插入操作,在此只分析插入操作,其他删除,查找等操作与插入类似。

(一)结点结构

<span>template<class K,class V>
struct AVLNode
{
	K _key;
	V _value;
	int _bf;//平衡因子
	AVLNode<K, V>* _parent;
	AVLNode<K, V>* _left;
	AVLNode<K, V>* _right;
	AVLNode(const K& key,const V& value)
		:_key(key)
		, _value(value)
		, _bf(0)
		, _parent(NULL)
		, _left(NULL)
		, _right(NULL)
	{}
};</span>

  AVL树的结点可以看作是一个三叉链,方便我们调整数的平衡。节点内有key和value,使用key建树。

(二)插入操作

<span>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)
		{
			parent = cur;
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			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;
		}
		//更新平衡因子
		while (parent)
		{
			//插入结点后影响父结点的平衡因子改变
			if (parent->_left == cur)
				--parent->_bf;
			else
				++parent->_bf;

			//0 / 1 || -1 /2 || -2

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = cur->_parent;
			}
			else//parent->_bf == 2 || parent->_bf == -2
			{
				if (parent->_bf == -2)
				{
					if (cur->_bf == -1)
					{
						RotateR(parent);
					}
					else//cur->_bf == 1
					{
						RotateLR(parent);
					}
				}
				else //parent->_bf == 2
				{
					if (cur->_bf == 1)
					{
						RotateL(parent);
					}
					else//cur->_bf == -1
					{
						RotateRL(parent);
					}
				}
				break;
			}
		}
		return true;
	}</span>
插入一个结点,步骤如下:

    (1)像世界上所有排序二叉树一样,把新的结点的平衡因子设置为0,然后插入当前保持AVL性质的二叉树T中。(千万注意不要插到哨兵后面去……)    

    (2).从插入的结点开始,递归向上回溯(记得判断是否到树根),过程如下:

  • 判断当前结点是父结点的左孩子还是右孩子:如果是左孩子则给父结点平衡因子+1,否则对平衡因子-1,代表当前插入结点对所在子树平衡性的影响
  •  如果父亲结点的平衡因子为0,说明插入节点后以父节点为根的子树高度没有发生变化且该子树没有失衡,直接结束处理;如果父亲结点的平衡因子在[-1,1]中,说明当前子树仍然保持平衡,但子树高度发生变化,递归向上处理父结点;否则此时以此父结点为根的子树失去平衡,需要平衡处理
  •  此过程直到遇到根直接返回原树T或者遇到失衡子树返回调整后的树T‘!之所以调平最小失衡子树后平衡调整过程就可以结束,是因为在调整失衡子树后整棵子树的高度恢复到了插入结点之前的高度,不再影响其他部分。

左单旋处理:


<span>void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		//旋转
		parent->_right = subRL;
		subR->_left = parent;

		if (subRL)
			subRL->_parent = 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;
	}</span>
右单旋处理:



<pre name="code" class="cpp">
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;


//旋转
parent->_left = subLR;
subL->_right = parent;


if (subLR)
subLR->_parent = parent;


//链接父节点
Node* ppNode = parent->_parent;
parent->_parent = subL;
if (ppNode == NULL)
{
_root = subL;
subL->_parent = NULL;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
subL->_parent = ppNode;
}
//更新平衡因子
subL->_bf = parent->_bf = 0;
}

左右双旋:



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

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

		//LR/1:L=1;-1:P=1;
		if (bf == 1)
		{
			//parent->_bf = 0;
			subL->_bf = 1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			//subL->_bf = 0;
		}
		else
		{
		}
		//subLR->_bf = 0;
	}</span>
右左双旋:




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

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

		//RL/1:P=-1;-1:R=1;
		if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else
		{
		}
		subRL->_bf = 0;
	}</span>

最后我们来看插入一个序列完整的旋转过程:




本页内容版权归属为原作者,如有侵犯您的权益,请通知我们删除。

linux基础知识 - 2016-07-24 14:07:48

1:基本知识 微内核:是一种提供必要服务的操作系统内核,大部分内核都作为单独的进程在特权模式先运行,他们通过消息传递进行通讯 单内核:单内核是个很大的进程,他的内部又悲愤为若干个模块,是个单独的二进制但印象,其模块间的通讯是通过直接调用其他模块中的函数实现的,而不是消息传递。 linux分几种应用程序级别 Ring 0 特权模式 一般是系统底层运行级别 Ring3 应用程序级别 一般的级别 有时候应用进程为了调用系统底层的模块,可能会在用户空间和内核空间之间进行来回的切换,这是很耗时间的,平时工作中应注意
1. 概述 嵌入式系统由硬件环境、嵌入式操作系统和应用程序组成,硬件环境是操作系统和应用程序运行的硬件平台,它随应用的不同而有不同的要求。硬件平台的多样性是嵌入式系统的主要特点,如何使嵌入式操作系统在不同的硬件平台上有效地运行,是嵌入式系统开发中需要解决的关键问题。解决的方法是在硬件平台和操作系统之间提供硬件相关层来屏蔽这些硬件的差异,给操作系统提供统一的运行环境,这种硬件相关层就是嵌入式系统中的板级支持包BSP(Board Support Package,简称BSP)。 2. BSP及其作用 BSP是嵌
一.什么是装箱?什么是拆箱? 在前面的文章中提到,Java为每种基本数据类型都提供了对应的包装器类型,至于为什么会为每种基本数据类型提供包装器类型在此不进行阐述,有兴趣的朋友可以查阅相关资料。在Java SE5之前,如果要生成一个数值为10的Integer对象,必须这样进行:   1 Integer i = new   Integer( 10 ); 而在从Java SE5开始就提供了自动装箱的特性,如果要生成一个数值为10的Integer对象,只需要这样就可以了:   1 Integer i = 10 ;

Redis与Java - 数据结构 - 2016-07-24 14:07:41

Redis与Java 标签 : Java与NoSQL Redis( REmote DIctionary Server ) is an open source (BSD licensed), in-memory data structure store, used as database , cache and message broker . It supports data structures such as strings , hashes , lists , sets , sorted sets
0x00 实验背景 Server:选用腾讯云的云主机  Ubuntu Server 14.04.1 LTS 64位 Client-1:Acer笔记本 Win7 x64系统 Client-2:安卓机小米4  Android 6.0系统(MIUI8)   0x01  OpenVPN的背景知识 **** **** 以下内容摘自维基百科**** **** OpenVPN是一个用于创建虚拟专用网络加密通道的软件包,最早由James Yonan编写。OpenVPN允许创建的VPN使用公开密钥、电子证书、或者用户名/密

逐步深入TCP/IP协议栈 - 2016-07-24 14:07:36

一、关于应用层用户数据的历程,见下图:                                                                             TCP/IP数据包的封装 过程: 应用层将数据通过协议栈逐层向下传递,其下的每层接到来自上层的数据时,根据每层的协议都要在其数据 的前端添加首部信息进行封装。不同的协议层对数据包有不同 的称谓,在传输层叫做数据段,在网络层叫做数据报, 在链路层叫做数据帧。在经过链路层时,数据已经封装成帧并递交给物理层的传输介质上,到

Java事务--JTA原理 - 2016-07-23 19:07:54

        上一篇文章介绍了JDBC事务,JDBC可以处理单数据源的事务,满足大部分事务处理的需求,但是JDBC事务不能解决多数据源和分布式事务问题,Java平台给我们提供了解决方案--JTA。本文将探讨JTA的一些细节。          一 分布式事务          通常把一个数据库内部的事务处理,如对多个表的操作,作为本地事务看待。数据库和JDBC的事务处理对象是本地事务,而分布式事务处理的对象是全局事务。          所谓全局事务,是指分布式事务处理环境中,多个数据库可能需要共同完成
LINUX下SVN安装,配置,web目录同步 注: 各服务器运行环境可能有所不同,操作过程中可能出现其他问题,自行查阅资料解决 SVN的具体使用方法很多,本文档只是使用了SVN最简单的用法,感兴趣的同学可以查阅相关资料。 一、 安装subversion 首先输入rpm -qa | grep subversion 查看SVN是否已经安装过 如果输出类似如下结果,则说明已经安装:subversion-1.6.11-7.el6.x86_64 执行 yum -y install subversion 安装SVN
一、目录结构 首先是目录结构如图: 二、pom.xml文件 project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd" modelVersion4.0.0/modelVe

Linux内核之进程管理 - 2016-07-23 19:07:13

进程: 进程就是处于执行期的程序以及它包含的资源总和。 线程是进程中的活动对象,每个线程拥有一个独立的程序计数器、进程栈和一组进程寄存器。 内核调度的是线程,而不是进程。 进程描述符: 内核的进程描述符为 task_struct 结构体,定义在linux/sched.h,进程描述符包含了一个进程的所有信息。包括:进程标识符、进程当前状态、栈地址空间、内存地址空间、文件系统、打开的文件、信号量等。 内核把进程的列表存放在叫做 任务列表(task list) 的双向循环链表,链表中每一项都是类型为task_s