【数据结构】平衡二叉排序树BBST之AVL树

如果贷款利率下降至下限(floor rate)，利率底合约的提供者将向合约持有人补偿实际利率与利率下限的差额，从而保证合约持有人实际支付的净利率不会超过合约规定的下限。如禾嘉股份实际实方式补偿给禾嘉股份,补偿的金额的计算方式为:当期应补偿的金额=禾嘉股份当期归属于母公司股东的净利润四川禾嘉股份2014 年第一次临时股东大会文件预计数额下限-禾嘉股份当期实际实现的归属于母公司股东的净利润。因为这个新创建的region实例是要从aa树中的某个节点分出部分空间，因而首先要将aa树中的那个节点从树中移除，然后如果树中移除的节点的end值和新创建的region的end值一样，则直接移除就可以了，否则，要将树种移除的节点剩余部分的重新创建一个region插回树中。

适度平衡：保证树高在渐近意义上不超过O(lgn)适度平衡的树也称作平衡二叉树。

动态链表主要包含创建、插入、删除、遍历操作。虽然linux内核4.14.15是迄今为止最大的，其中包含104个文件改变，1514插入和447删除，linux 4.9.78 lts和4.4.113 lts内核是非常相同的，包括60个改变的文件525插入和删除167个，更改文件64个，分别有960个插入和139个删除。二叉排序树的插入与删除可能会破坏二叉排序树的性质，现在要求插入和删除操作保持其性质。

平衡二叉排序树包括：AVL树，红黑树，伸展树等

avl树的c语言实现：在计算机科学中，avl树是最先发明的自平衡二叉查找树。当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘4次，最多5次，而且文件越多，b树比平衡二叉树所用的磁盘io操作次数将越少，效率也越高。这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。

AVL定义适度平衡的标准：

定义平衡因子(BalanceFactor)：BF(node) = height(lchild(node)) - height(rchild(node))

对所有的节点node，有|BF(node)| <= 1

一系列的重平衡方法：旋转操作

基本的旋转操作如下图所示

根据不同的情形又分为四种情况

1.返回某个结点的高度height

我们设定当结点为null时的高度为-1，其余情况的高度由每个结点自己维护。

private int height(BinaryTreeNode node) {
		if (node == null) {
			return -1;
		} else {
			return node.height;
		}
	}

2.返回某个结点的平衡因子

平衡因子等于左子树高度减右子树高度

private int balance(BinaryTreeNode node) {
		if (node == null)
			return 0;
		return height(node.lchild) - height(node.rchild);
	}

3.左旋LL

按照图示顺序分三步，将tmp作为最终的根结点返回。

需要额外做的工作包括对父结点改变了的结点赋新的parent，更新高度，最终返回的结点的父亲节点一定要在调用处设置！！

// LL   将node结点左旋，node是最小不平衡子树的根
public BinaryTreeNode leftRotate(BinaryTreeNode node) {
		BinaryTreeNode tmp = node.lchild;
		tmp.parent = null;
		node.lchild = tmp.rchild;
		if (tmp.rchild != null)
			tmp.rchild.parent = node;
		tmp.rchild = node;
		node.parent = tmp;
		// 更新高度，包括是node和node.rchild
		node.height = Math.max(height(node.lchild), height(node.rchild)) + 1;
		tmp.height = Math.max(height(tmp.lchild), node.height) + 1;
		return tmp;
	}

4.双旋LR

分两步即可，先对结点的左子树进行左旋操作，再对该结点进行右旋操作，要注意保存第一次返回的结点的父亲结点！！

public BinaryTreeNode leftRightRotate(BinaryTreeNode node) {
		node.lchild = rightRotate(node.lchild);
		node.lchild.parent = node; // 父结点赋值！！
		return leftRotate(node);
	}

5.返回待旋转的结点的旋转类型

private RotateType rotateType(BinaryTreeNode node) {
		if (balance(node) < -1) {
			if (balance(node.rchild) > 0) {
				return RotateType.RL;
			} else {
				return RotateType.RR;
			}
		} else { // >1
			if (balance(node.lchild) < 0) {
				return RotateType.LR;
			} else {
				return RotateType.LL;
			}
		}
	}

6.用以node为顶点旋转过后的树来代替node这棵子树

区别之前用的replace函数void replace(BinaryTreeNode node1, BinaryTreeNode node2)

将结点A旋转后，A的父结点左右孩子都已经变了，因此要先将他的父结点保存下来以便将旋转后的子树往它后面挂，所以对该函数的调用不等于调用replace(node,leftRotate(node),type);

// 拼接旋转后的子树:用以node为定点旋转过后的树来代替node这棵子树
	private void replaceNode(BinaryTreeNode node, 
			RotateType type) {
		BinaryTreeNode tmpParent = node.parent;
		BinaryTreeNode rotateNode = null;
		switch (type) {
		case LL:
			rotateNode = leftRotate(node);
			break;
		case RR:
			rotateNode = rightRotate(node);
			break;
		case LR:
			rotateNode = leftRightRotate(node);
			break;
		case RL:
			rotateNode = rightLeftRotate(node);
			break;
		}
		if (tmpParent == null) {
			root = rotateNode;
			rotateNode.parent = null; //父结点赋值非常关键！！
		} else if (tmpParent.rchild == node) {
			tmpParent.rchild = rotateNode;
			rotateNode.parent = root; //父结点赋值非常关键！！
		} else {
			tmpParent.lchild = rotateNode;
			rotateNode.parent = root; //父结点赋值非常关键！！
		}
	}

有了上面一些基本的函数，就可以进行下面的两个重要操作：插入/删除结点

当插入一个结点可能会造成他的祖父结点失衡，进而曾祖父结点也会失衡等等一直往上延伸。这么看来插入操作乎很复杂？事实并不是这样，尽管这样，我们却不需要从下往上挨个调整结点至平衡。因为好消息是只要把从下往上的第一个失衡的结点所构成的子树重平衡就能保证其之上的所有结点平衡。二叉排序树+数据结构这里的第一个失衡的结点所构成的子树称为最小不平衡子树。二叉排序树+数据结构调整最小不平衡子树至重平衡，它的高度和插入结点之前相比未变，因此也不会影响到更上层的结点。这样只需要有限步操作即可重平衡，复杂度为O(1)。

这里每插入一个节点都要更新已存在的结点的高度！插入的实现和BST里面一样，只是要更新结点高度

private BinaryTreeNode insertRecurAVL(BinaryTreeNode root,BinaryTreeNode insertNode) {
		if (this.root == null) {
			this.root = root = insertNode;
		} else if (insertNode.data < root.data && root.lchild == null) {
			root.lchild = insertNode;
			insertNode.parent = root;
		} else if (insertNode.data >= root.data && root.rchild == null) {
			root.rchild = insertNode;
			insertNode.parent = root;
		} else {
			if (insertNode.data < root.data && root.lchild != null)
				insertRecurAVL(root.lchild, insertNode);
			if (insertNode.data >= root.data && root.rchild != null)
				insertRecurAVL(root.rchild, insertNode);
		}
		// 更新高度！
		root.height = Math.max(height(root.lchild), height(root.rchild)) + 1;// 放在这里的位置很重要
		return insertNode;
	}

于是插入节点后对其进行检查重平衡的代码如下，基本思路是将新的结点插入到对应的位置，然后从他开始往上走，直到遇到第一个不平衡的结点，也就是最小不平衡子树，

然后旋转这个结点让其恢复平衡后来替换该结点。

public void insertAVL(BinaryTreeNode insertNode) {
		BinaryTreeNode node = insertRecurAVL(root, insertNode);

		// 调整最小不平衡子树
		while (node != null && balance(node) > -2 && balance(node) < 2) {
			node = node.parent;
		} // 跳出循环时，node为null 或者node不平衡
		if (node != null) {
			// 确定何种类型的旋转
			RotateType type = rotateType(node);
			replaceNode(node, type);
		}
	}

从数组创建一棵BBST的过程也可以通过insert操作循环的插入即可。

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