文档章节

动态查找---->平衡二叉树(AVL树)

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 2754
阅读 5
收藏 0
点赞 0
评论 0

平衡二叉树(AVL)

一、 平衡二叉树

在二叉查找树T中,若所有结点的平衡因子的绝对值均不超过1,则称T为一棵AVL树。

平衡二叉树又称AVL树,它是具有如下性质的二叉树:

• 左、右子树是平衡二叉树;

• 所有结点的左、右子树深度之差的绝对值≤ 1

为了方便起见,给每个结点附加一个数字,给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子balance。这样,可以得到AVL树的其它性质:

• 任一结点的平衡因子只能取:-1、0或 1;如果树中任意一个结点的平衡因子的绝对值大于1,则这棵二叉树就失去平衡,不再是AVL树;

对于一棵有n个结点的AVL树,其高度保持在O(log2n)数量级,ASL也保持在O(log2n)量级

二、  平衡调整----旋转

如果在一棵AVL树中插入一个新结点,就有可能造成失衡,此时必须重新调整树的结构,使之恢复平衡。我们称调整平衡过程为平衡旋转。无论是右旋还是左旋,都不改变二叉树的中序遍历结果。

1. 右旋(顺时针方向旋转)

结点v 是结点p 的左孩子,X和Y分别是v 的左、右子树,Z为p的右子树。所谓围绕结点p 的右旋操作,就是重新调整这些结点位置,将p作为v 的右孩子,将X 作为v 的左子树,将Y和Z分别作为p的左、右子树。围绕p右旋的结果。

                           

2. 左旋(逆时针方向旋转)

结点v 是结点p 的右孩子,Y 和Z 分别是v的左、右子树,X 为p 的左子树。所谓围绕结点p 的左旋操作,就是将p 作为v 的左孩子,将Z 作为v 的右子树,将X 和Y 分别作为p 的左、右子树。围绕p左旋的结果如图所示。

三、   插入操作

一般的,若在插入新的结点x 之后AVL 树T失去平衡,则失去平衡的结点只可能是x的祖先,且层次数小于等于x 的祖父的结点;也就是说失去平衡的结点是从x 的祖父到根的路径上的结点,但这些结点并不都是失去平衡的结点,有些结点仍然可能是平衡的。为了修正失衡的现象,可以从结点x 出发逆行向上,依次检查x 祖先的平衡因子,找到第一个失衡的祖先结点g。在从x 到g 的路径上,假设p 为g 的孩子结点,v 为p 的孩子结点。有结点p、v 必不为空,p 至少是x 的父亲,v 至少是x 本身。结点g、p、v 之间的父子关系共有4 种不同的组合,以下根据这4 种不同的组合,通过对结点g、p的旋转,使这一局部恢复平衡。

平衡旋转可以归纳为四类:

  1.   LL平衡旋转
  2.   RR平衡旋转
  3.   LR平衡旋转
  4.   RL平衡旋转

1)LL平衡旋转: p 是g的左孩子,且v是p的左孩子;

在这种情况下,必定是由于在v 的后代中插入了新结点x 而使得g不再平衡。针对这种情况,可以简单的通过结点g 的单向右旋,即可使得以g为根的子树得到平衡

 

2)RR平衡旋转: p是g的右孩子,且v 是p的右孩子;

与第一种情况对称,此时,失衡是由于在g 的右孩子的右子树中插入结点x造成的。在这种情况下需要通过结点g 的单向左旋来完成局部的平衡。

3)LR平衡旋转: p是g的左孩子,且v是p的右孩子;

如果是在p 的左孩子的右子树中插入一个结点,则对应为第三种情况。在这种情况中,要使得局部的失衡重新平衡,那么需要先后进行先左后右的双向旋转:第一次是结点p的左旋,第二次是结点g 的右旋。

4)RL平衡旋转:

p是g的右孩子,且v是p的左孩子;第四种情况与第三种情况对称,其平衡调整过程也与第三种情况对称,可以通过先右后左的双向旋转来完成,其中第一次是结点p 的右旋,第二次是结点g的左旋。

四、  删除节点

按照通常的二叉查找树删除结点的方法在AVL树中删除结点x之后,如果发生失衡现象,为了重新平衡,同样从x出发逆行向上找到第一个失衡的结点g,通过旋转操作实现AVL树的重新平衡。使得结点g失衡的原因可以看成四种:

1. 失衡是由于 g 的左孩子的左子树过高造成的;

2. 失衡是由于 g 的右孩子的右子树过高造成的;

3. 失衡是由于 g 的左孩子的右子树过高造成的;

4. 失衡是由于 g 的右孩子的左子树过高造成的。

这四种情况与插入结点导致失衡的四种情况进行平衡化的旋转方法相同。但是需要注意两个特殊情况:失衡可能是由于左(右)孩子的左、右子树同时过高造成的,

五、   旋转操作的统一实现方法

前面介绍的4 种平衡旋转操作,需要根据结点g、p、v(p是g的孩子,v是p的孩子)之间的相互关系来判断应该使用的旋转方法。为此,在这里引入一种统一的算法,这种实现简洁、直观,容易实现。

在插入或删除结点x 之后,从x出发逆行向上,找到第一个失衡的结点g,然后根据g失衡的原因,设置p和v的指向,p 和v都是其父结点较高子树的根。此时,在这一局部,以p的兄弟为根有一棵子树,即g 较矮的子树;以v的兄弟为根有一棵子树,即p较矮的子树;v有两棵子树;一共有4棵子树。注意,在这4棵子树中可能有空树。显然,以失衡结点g 为根的局部平衡是在这3 个结点和4棵子树间完成的。

在确定了这3 个结点和4棵子树之后,接着为它们重命名。具体的命名方法是,从左到右将4 棵子树命名为T0、T1、T2、T3;按照中序顺序将结点g、p、v 分别命名为a、b、c。

四种不同旋转情况的命名见图所示。

一旦完成重命名,无论对于那种情况,我们都能以相同的方法将这3 个结点和4棵子树重新组合起来,以达到旋转平衡的目的。如图(e)所示,以结点b作为局部子树的根,结点a 和c 分别是b 的左孩子和右孩子,结点a 的左右子树分别是T0、T1,结点c的左右子树分别是T2、T3。

算法rotate

输入:失衡的结点z

输出:平衡后子树的根结点

private BinTreeNode rotate(BinTreeNode z) {
		BinTreeNode y = higherSubT(z); // 取y为z更高的孩子
		BinTreeNode x = higherSubT(y); // 取x为y更高的孩子
		boolean isLeft = z.isLChild(); // 记录:z是否左孩子
		BinTreeNode p = z.getParent(); // p为z的父亲
		BinTreeNode a, b, c; // 自左向右,三个节点
		BinTreeNode t0, t1, t2, t3; // 自左向右,四棵子树
		// 以下分四种情况
		if (y.isLChild()) { // 若y是左孩子,则
			c = z;
			t3 = z.getRChild();
			if (x.isLChild()) { // 若x是左孩子(左左失衡)
				b = y;
				t2 = y.getRChild();
				a = x;
				t1 = x.getRChild();
				t0 = x.getLChild();
			} else { // 若x是右孩子(左右失衡)
				a = y;
				t0 = y.getLChild();
				b = x;
				t1 = x.getLChild();
				t2 = x.getRChild();
			}
		} else { // 若y是右孩子,则
			a = z;
			t0 = z.getLChild();
			if (x.isRChild()) { // 若x是右孩子(右右失衡)
				b = y;
				t1 = y.getLChild();
				c = x;
				t2 = x.getLChild();
				t3 = x.getRChild();
			} else { // 若x是左孩子(右左失衡)
				c = y;
				t3 = y.getRChild();
				b = x;
				t1 = x.getLChild();
				t2 = x.getRChild();
			}
		}

		// 摘下三个节点
		z.sever();
		y.sever();
		x.sever();

		// 摘下四棵子树
		if (t0 != null)
			t0.sever();
		if (t1 != null)
			t1.sever();
		if (t2 != null)
			t2.sever();
		if (t3 != null)
			t3.sever();

		// 重新链接
		a.setLChild(t0);
		a.setRChild(t1);
		c.setLChild(t2);
		c.setRChild(t3);
		b.setLChild(a);
		b.setRChild(c);

		// 子树重新接入原树
		if (p != null)
			if (isLeft)
				p.setLChild(b);
			else
				p.setRChild(b);

		return b;// 返回新的子树根
	}

AVL 树也是一棵二叉查找树,则AVL 树的实现可以通过继承二叉查找树来实现。AVL树与一般二叉查找树不同的是,在插入和删除结点之后需要重新进行平衡。因此,只需要重写insert 和remove 方法即可。

 

 

                                                                                                          

附:整个的avl树的代码 

package dsa.adt;

import dsa.strategy.Strategy;

public class AVLTree extends BSTree {

	public AVLTree() {
		super();
	}

	public AVLTree(Strategy strategy) {
		super(strategy);
	}

	private boolean isBalance(BinTreeNode v) {
		if (v == null)
			return true;
		int lH = (v.hasLChild()) ? v.getLChild().getHeight() : -1;
		int rH = (v.hasRChild()) ? v.getRChild().getHeight() : -1;
		return (Math.abs(lH - rH) <= 1);
	}

	private BinTreeNode higherSubT(BinTreeNode v) {
		if (v == null)
			return null;
		int lH = (v.hasLChild()) ? v.getLChild().getHeight() : -1;
		int rH = (v.hasRChild()) ? v.getRChild().getHeight() : -1;
		if (lH > rH)
			return v.getLChild();
		if (lH < rH)
			return v.getRChild();
		if (v.isLChild())
			return v.getLChild();
		else
			return v.getRChild();
	}

	private BinTreeNode rotate(BinTreeNode z) {
		BinTreeNode y = higherSubT(z); // 取y为z更高的孩子
		BinTreeNode x = higherSubT(y); // 取x为y更高的孩子
		boolean isLeft = z.isLChild(); // 记录:z是否左孩子
		BinTreeNode p = z.getParent(); // p为z的父亲
		BinTreeNode a, b, c; // 自左向右,三个节点
		BinTreeNode t0, t1, t2, t3; // 自左向右,四棵子树
		// 以下分四种情况
		if (y.isLChild()) { // 若y是左孩子,则
			c = z;
			t3 = z.getRChild();
			if (x.isLChild()) { // 若x是左孩子(左左失衡)
				b = y;
				t2 = y.getRChild();
				a = x;
				t1 = x.getRChild();
				t0 = x.getLChild();
			} else { // 若x是右孩子(左右失衡)
				a = y;
				t0 = y.getLChild();
				b = x;
				t1 = x.getLChild();
				t2 = x.getRChild();
			}
		} else { // 若y是右孩子,则
			a = z;
			t0 = z.getLChild();
			if (x.isRChild()) { // 若x是右孩子(右右失衡)
				b = y;
				t1 = y.getLChild();
				c = x;
				t2 = x.getLChild();
				t3 = x.getRChild();
			} else { // 若x是左孩子(右左失衡)
				c = y;
				t3 = y.getRChild();
				b = x;
				t1 = x.getLChild();
				t2 = x.getRChild();
			}
		}

		// 摘下三个节点
		z.sever();
		y.sever();
		x.sever();

		// 摘下四棵子树
		if (t0 != null)
			t0.sever();
		if (t1 != null)
			t1.sever();
		if (t2 != null)
			t2.sever();
		if (t3 != null)
			t3.sever();

		// 重新链接
		a.setLChild(t0);
		a.setRChild(t1);
		c.setLChild(t2);
		c.setRChild(t3);
		b.setLChild(a);
		b.setRChild(c);

		// 子树重新接入原树
		if (p != null)
			if (isLeft)
				p.setLChild(b);
			else
				p.setRChild(b);

		return b;// 返回新的子树根
	}

	private BinTreeNode reBalance(BinTreeNode v) {
		if (v == null)
			return root;
		BinTreeNode c = v;
		while (v != null) { // 从v开始,向上逐一检查z的祖先
			if (!isBalance(v))
				v = rotate(v); // 若v失衡,则旋转使之重新平衡
			c = v;
			v = v.getParent(); // 继续检查其父亲
		}// while
		return c;
	}

	// 按关键字插入元素ele
	public void insert(Object ele) {
		super.insert(ele);
		root = reBalance(startBN);
	}

	// 若查找表中存在与元素ele关键字相同元素,则删除一个并返回;否则,返回null
	public Object remove(Object ele) {
		Object obj = super.remove(ele);
		root = reBalance(startBN);
		return obj;
	}
}

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2012/12/28/5637131.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
05/08
0
0
《算法导论》学习笔记之Chapter13红黑树

第13章 红黑树 红黑树是一种平衡搜索树中的一种,他可以保证在最坏情况下基本动态集合操作时间复杂度为O(logn)。所以,在学习红黑树之前,我需要先去调研一下平衡树; 先看一下平衡树的定义:...

u010483897
2017/12/13
0
0
花时间分别实现了AVL,SBT,Treap,RBT,还是有些收获的

发现AVL(平衡二叉树)和SBT(据说是国内某天才少年创造的宽度平衡二叉树),在数学上和树的构成上是完全等价的,SBT完全可以说是AVL的变种,创新之处在于使用统计(宽度)代替了高度,因此可...

刘地
2012/10/12
503
4
数据结构与算法之10(AVL自平衡二叉树与RB红黑树)

本节继续总结二叉树的变种,上节里的哈夫曼树是一种独特的二叉树,用于编解码会比较有效。这里的两种树都是BST二叉搜索树的加强版。 》BST二叉搜索树的弱点 我们之前也提到了,当插入序列是有...

kkae8643150
2017/12/01
0
0
堆,AVL树,红黑树以及优先级队列

声明:本文完全没有定量分析,需要定量分析的,请随便查阅一本数据结构的书籍或网页。 二叉堆:拥有删除最大(小)权值节点以及插入任意节点操作,是一颗完全二叉树,其完全性由插入和删除动...

晨曦之光
2012/04/10
505
0
Java Balanced Binary Tree

Java Balanced Binary Tree 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树,所以...

秋风醉了
2015/06/30
0
0
数据结构之Tree

数据结构和数据的关系,就如同水和盛水的器皿一样, 比如: 消防员会选择用消防水栓装水,原因是他需要处理高压大量的水,解救火灾;茶馆的伙计会用茶壶, 茶壶受热均匀,煮出的茶才韵味无穷...

晨曦之光
2012/03/09
154
0
java集合框架(四):TreeMap

TreeMap的数据结构与HashMap、LinkedHashMap不同,其整个结构就是一颗红黑树,所以我们要研究TreeMap就得先从红黑树开始。对于红黑树的算法,我在本文章不详细展开,有兴趣的同学可以点击这里...

chenzanjin
2017/11/07
0
1
平衡二叉树、完全二叉树、满二叉树、二叉搜索(查找 / 排序)树、平衡二叉搜索树、二叉堆

查了一些博客、百科整理出以下关于树的定义以及易混点: 平衡二叉树:一棵空树或左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是平衡二叉树。(注意:实际应用中很少有不是二叉搜...

BeerBread134
2017/06/03
0
0
JDK TreeMap Red-Black Tree

介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和 Robert Sedgewi...

zuoer
2011/12/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Mybatis收集配置

一、Mybatis取Clob数据 1、Mapper.xml配置 <resultMap type="com.test.User" id="user"> <result column="id" property="id"/> <result column="json_data" property="jsonData" ......

星痕2018
19分钟前
0
0
centos7设置以多用户模式启动

1、旧版本linux系统修改inittab文件,在新版本执行vi /etc/inittab 会有以下提示 # inittab is no longer used when using systemd. # # ADDING CONFIGURATION HERE WILL HAVE NO EFFECT ON......

haha360
50分钟前
0
0
OSChina 周日乱弹 —— 局长:怕你不爱我

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ andonny :分享周二珂的单曲《孤独她呀》 《孤独她呀》- 周二珂 手机党少年们想听歌,请使劲儿戳(这里) @孤星闵月 :没事干,看一遍红楼梦...

小小编辑
55分钟前
127
8
Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式 Factory工厂模式 Singleton单例模式 Delegate委派模式 Strategy策略模式 Prototype原型模式 Template模板模式 Spring5 beans 接口实例化 代理Bean操作 ...

小致dad
今天
0
0
SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
10
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
17
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
245
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部