java实现常见查找算法(6)

第8章 查找结构：符号表，二叉查找树，二叉查找树的查找、插入和删除操作，avl树，高度平衡，avl树的插入算法，avl树的时间复杂性分析，m叉查找树，m叉查找树的查找，b树的定义和性质，b树的插入操作，b树的删除操作，静态散列，散列表，散列函数，溢出处理。8 查找结构：符号表，二叉查找树，二叉查找树的查找、插入和删除操作，avl树，高度平衡，ll, lr, rr, rl 旋转, 插入算法，时间复杂性分析，b树，m叉查找树，m叉查找树的查找，b树的定义和性质，b树的插入操作，b树的删除操作，静态散列，散列表，散列函数，溢出处理，开放寻址，链接。以上代码实现了单链表的创建，但是链表的常用操作还有查找、插入、删除等没有讲解，删除操作与插入操作类似，就不在这里一一讲解了，在此我们以查找和插入为例进行讲解，但是读者在编写删除操作的时候别忘了把删除的结点释放掉。

昨天看了一下关于树中的面试题，发现二叉树中的面试题比较常见的题型大概有下面几个：创建一颗二叉树（先序，中序，后序）、遍历一颗二叉树（先序，中序，后序和层次遍历）、求二叉树中叶子节点的个数、求二叉树的高度、求二叉树中两个节点的最近公共祖先、打印和为某一值。第4章 树：树和森林的概念及其表示，二叉树，二叉树性质，二叉树表示，二叉树遍历与树游标， lvr, lrv, vlr，中序游标，按层次遍历，线索二叉树，线索，中序遍历线索二叉树，将结点插入线索二叉树，选择树，胜者树，败者树，森林的二叉树表示及遍历。子数组,排好序,个子数组,数组中,元素个数,数组元素,升序子,int,array,数组,row,index,console,right,pointssymbol,,c#实现归并排序（递归，非递归，自然归并） c#实现归并排序（递归，非递归，自然归并） c#实现归并排序（递归，非递归，自然归并）,实现,归并,排序,递归,自然 c#实现归并排序（递归，非递归，自然归并）,实现,归并,排序,递归,自然,int[] merge = new int[array。

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为[log2n]+1，那么查找的时间复杂也就为O(logn)，近似于折半查找，事实上，上左图也不够平衡，明显的左重右轻。不平衡的最坏情况就是像上右图的斜树，查找时间复杂度为O(n)，这等同于顺序查找。

因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。这样我们就引申出另一个问题，如何让二叉排序树平衡的问题。

平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

从平衡二叉的英文名字(AVL树)，你也可以体会到，它是一种高度平衡的二叉排序树。

那什么叫做高度平衡呢?意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor) ，那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。如下图，当新插入结点37时，距离它最近的平衡因子绝对值超过1的结点是58(即它的左子树深度2减去右子树深度0)，所以从58开始以下的子树为最小不平衡子树。

对红黑树的插入删除大体分为两个阶段: 寻找插入位置, 再作着色和旋转操作以保持红黑结构. 为了维护顺序统计数的附加信息, 在第一阶段, 对从根到插入位置路径上的每一个结点, 将size加1, 而新结点的size置1. 对第二阶段, 着色并不影响树型结构, 只有旋转影响局部结构, 只需要在旋转操作的基础上加上以下代码:。平衡二叉树的构建思想：每当插入一个新结点时，先检查是否破坏了树的平衡性，若有，找出最小不平衡子树。具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子结点则分别在位置4、5、6和7，以此类推。

首先是需要改进二叉排序树的结点结构，增加一个bf用来存储平衡因子。

/**
 * 二叉树的二叉树链表结构定义
 */
private static class BinTree {
	int data;// 结点数据
	int bf;// 结点的平衡因子
	BinTree lchild, rchild;// 左右孩子引用
	@Override
	public String toString() {
		return "[结点值:" + data + ", 平衡因子:" + bf + ", 左孩子:" + lchild + ", 右孩子:" + rchild + "]";
	}
}

然后，对于右旋操作，我们的代码如下。

/** 右旋 */
static BinTree rRotate(BinTree bt) {
	BinTree l;
	l = bt.lchild;//l指向bt的左子树的根节点
	bt.lchild = l.rchild;//l的右子树指向bt的左子树
	l.rchild = bt;//bt指向l的右子树
	bt = l;//l指向新的根节点
	return bt;
}

供选择的答案： a：①是特殊的树②不是树的特殊形式③是两棵树的总称④是只有二个根结点的树形结构 b：①左子结点②右子结点③左子结点或者没有右子结点 ④兄弟 c～d： ①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟e：①o(n)②o(n)③o(log2n)④o(log2n) 15、每一棵树都能唯一地转换为它所对应的二叉树，树的这种二叉树表示对树的运算带来很大的好是 n在原树里对应结点的__a__,而 n 的右子女是原树里对应结点的__b__。由树转换成的二叉树里，一个结点n的左子女是n在原树里对应结点的＿c＿，而n的右子女是它在原树里对应结点的＿d＿。

左旋操作代码如下。

/** 左旋 */
static BinTree lRotate(BinTree bt) {
	BinTree r;
	r = bt.rchild;
	bt.rchild = r.lchild;
	r.lchild = bt;
	bt = r;
	return bt;
}

这段代码与右旋代码是对称的。

现在我们来看左平衡旋转处理的函数代码。

static final int LH = 1;// 左高
static final int EH = 0;// 等高
static final int RH = -1;// 右高
/** 用于存放各个方法中返回的临时树结点 */
static BinTree temp = new BinTree();
/**
 * 处理完成后返回平衡二叉树bt
 * @param bt 待处理的左重右轻的二叉树
 * @return
 */
static BinTree leftBalance(BinTree bt) {
	BinTree l, lr;
	l = bt.lchild;// l指向bt的左子树根节点
	switch (l.bf) {
	// 检查左子树的平衡度，并作相应平衡处理
	case LH:/* 新结点插在bt左孩子的左子树上，需要进行右旋处理 */
		bt.bf = l.bf = EH;
		temp = rRotate(bt);
		bt = temp;
		break;
	case RH:/* 新结点插在bt的左孩子的右子树上，需要作双旋处理 */
		lr = l.rchild;/* lr指向bt左孩子的右子树根 */
		switch (lr.bf) {/* 修改bt及其左孩子的平衡因子 */
		case LH:
			bt.bf = LH;
			l.bf = EH;
			break;
		case EH:
			bt.bf = l.bf = EH;
			break;
		case RH:
			bt.bf = EH;
			l.bf = LH;
			break;
		}
		lr.bf = EH;
		temp = lRotate(bt.lchild);/* 对bt的左孩子作左旋平衡处理 */
		rRotate(temp);/* 对bt作右旋平衡处理 */
		bt = temp;
	}
	return bt;
}

同样的，右平衡旋转处理的函数代码非常类似。

/**
 * 处理完成后返回平衡二叉树 
 * @param bt 左轻右重的平衡二叉树
 * @return
 */
static BinTree rightBalance(BinTree bt) {
	BinTree r, rr;
	r = bt.rchild;// r指向bt的右子树根节点
	switch (r.bf) {
	// 检查右子树的平衡度，并作相应平衡处理
	case RH:/* 新结点插在bt右孩子的右子树上，需要进行左旋处理 */
		bt.bf = r.bf = EH;
		temp = lRotate(bt);
		bt = temp;
		break;
	case LH:/* 新结点输入在bt的右孩子的左子树上，需要作双旋处理 */
		rr = r.lchild;/* rr指向bt右孩子的左子树根 */
		switch (rr.bf) {/* 修改bt及其左孩子的平衡因子 */
		case LH:
			bt.bf = RH;
			r.bf = EH;
			break;
		case EH:
			bt.bf = r.bf = EH;
			break;
		case RH:
			bt.bf = LH;
			r.bf = EH;
			break;
		}
		rr.bf = EH;
		temp = rRotate(bt.rchild);/* 对bt的右孩子作右旋平衡处理 */
		bt.rchild = temp;
		temp = lRotate(bt);/* 对bt作左旋平衡处理 */
		bt = temp;
	}
	return bt;
}

有了这些准备，我们的主函数才算是正式登场了。

/** 全局变量,用于标识树是否增高 */
static boolean taller = false;
/**
 * 在平衡二叉树t中若不存在与e有相同关键字的结点则插入t中并返回
 * t，若插入e后使得t失去平衡则需要作平衡处理
 * @param t 平衡二叉排序树
 * @param e 待插入元素
 * @return
 */
static BinTree insertAVL(BinTree t, int e) {
	if (null == t) {
		// 插入新结点。树长高，taller为true
		t = new BinTree();
		t.data = e;
		t.lchild = t.rchild = null;
		t.bf = EH;
		taller = true;
	} else {
		if (e == t.data) {
			// 树中已存在和e有相同关键字的结点则不再插入
			taller = false;
			return t;
		} else if (e < t.data) {
			// 当e小于根结点或子根节点则应继续在t的左子树中进行搜索
			BinTree lchild = insertAVL(t.lchild, e);
			t.lchild = lchild;
			if (!taller)
				return t;
			if (taller) {// 已插入到t的左子树中且左子树"长高"
				switch (t.bf) {// 检查t的平衡度
				case LH:// 原本左子树比右子树高，需要作左平衡处理
					temp = leftBalance(t);
					t = temp;
					taller = false;
					break;
				case EH:// 原本左右子树等高，现因左子树增高而树增高
					t.bf = LH;
					taller = true;
					break;
				case RH:// 原本右子树比左子树高，现左右子树等高
					t.bf = EH;
					taller = false;
					break;
				}
			}
		} else {// 应继续在t的右子树中进行搜索.
			BinTree rchild = insertAVL(t.rchild, e);
			t.rchild = rchild;
			if (!taller)
				return t;
			if (taller) {// 已插入到 t的右子树中且右子树"长高"
				switch (t.bf) {// 检查t的平衡度
				case LH:// 原本左子树比右子树高，现左右子树等高
					t.bf = EH;
					taller = false;
					break;
				case EH:// 原本左右子树等高，现因右子树增高而树增高
					t.bf = RH;
					taller = true;
					break;
				case RH:// 原本右子树比左子树高，需要作右平衡处理
					temp = rightBalance(t);
					t = temp;
					taller = false;
					break;
				}
			}
		}
	}
	return t;
}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-106859-6.html