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

删除某个节点只可能导致他的父亲节点失衡，因为，如果我们删除最深的那条子树，那么不会失衡，所以产生失衡只可能是由于删除了短的子树上的结点，这样对外界来说，该结点的父亲所在的子树的高度未变，于是上面的结点的平衡性也不会改变。那么删除操作只需要重平衡它的父结点吗？事实上，删除一个结点他的父亲如果发生了失衡，那么当让其父亲节点重平衡后，局部子树的高度减少了，因此失衡的情况可能继续往上传递，最差情况下一直传递到根，于是删除的复杂度为O(lgn)。其实也就是因为这个原因，AVL树用的不多，SGI的STL中都未实AVL树，仅仅实现了红黑树

// 删除AVL树中的结点
public void deleteAVL(BinaryTreeNode node) {
		System.out.println(node.toString());
		BinaryTreeNode predecessorOfnode = null;
        if (node.lchild == null) { // 左子树为空，只需要移植右子树  
            replace(node, node.rchild);  
        } else if (node.rchild == null) {  
            replace(node, node.lchild);  
        } else {   
            predecessorOfnode = predecessor(node);  
            replace(node, node.lchild);  
            predecessorOfnode.rchild = node.rchild;  
            node.rchild.parent = predecessorOfnode;
            predecessorOfnode.height = Math.max(height(predecessorOfnode.lchild), height(node.rchild)) + 1;
        }
		// 调整平衡
		// 只需要从删除的结点的前驱开始依次向上判断
		BinaryTreeNode nodetmp = predecessorOfnode;
		while (nodetmp != null) {
			BinaryTreeNode tmp = nodetmp.parent; // 下面的旋转操作会改变nodetmp的父结点，所以提前保存下来！！
			if (balance(nodetmp) < -1 || balance(nodetmp) > 1) {
				// 不平衡
				RotateType type = rotateType(nodetmp);
				replaceNode(nodetmp, type);
			} 
			nodetmp = tmp;
		}
	}

/* 正确完成操作，返回1 */ 实例关键点分析 int remove int id， struct std ** res /* 根据id找到该学生的信息结点 */ /* 将该结点从链表上取下 */ /* 使用res保存该节点 */ /* 释放该结点所占用的内存 */ return 1。在构造哈夫曼树时，可以设置一个结构数组huffnode 保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n 个叶子结点的哈夫曼树共有2n－1 个结点，所以数组huffnode 的大小设置为2n－1，数组元素的结构形式如下：其中，weight 域保存结点的权值，lchild 和rchild 域分别保存该结点的左、右孩子结点在数组huffnode 中的序号，从而建立起结点之间的关系。在存储时对每个节点增设一个域来保存当前节点与父节点的相对关系，在获取节点信息时需要同时根据该域来确定当前节点与“根”的相对关系属性，并在路径压缩时同时对相对关系进行压缩[ 具体处理方法请参见源程序。

public class AVLTree extends BinarySearchTree {
	public enum RotateType {
		LL, RR, LR, RL
	};

	@Override
	public void createTree(int[] array) {
		// 从一个数组创建二叉搜索树
		for (int i : array) {
			insertAVL(new BinaryTreeNode(i));
		}
	}

	// 删除AVL树中的结点
	public void deleteAVL(BinaryTreeNode node) {
		BinaryTreeNode predecessorOfnode = null;
		if (node.lchild == null) { // 左子树为空，只需要移植右子树
			replace(node, node.rchild);
		} else if (node.rchild == null) {
			replace(node, node.lchild);
		} else {
			predecessorOfnode = predecessor(node);
			replace(node, node.lchild);
			predecessorOfnode.rchild = node.rchild;
			node.rchild.parent = predecessorOfnode;
			predecessorOfnode.height = Math.max(
					height(predecessorOfnode.lchild), height(node.rchild)) + 1;
		}
		// 调整平衡
		// 只需要从删除的结点的前驱开始依次向上判断
		BinaryTreeNode nodetmp = predecessorOfnode;
		while (nodetmp != null) {
			BinaryTreeNode tmp = nodetmp.parent; // 下面的旋转操作会改变nodetmp的父结点，所以提前保存下来！！
			if (balance(nodetmp) < -1 || balance(nodetmp) > 1) {
				// 不平衡
				RotateType type = rotateType(nodetmp);
				replaceNode(nodetmp, type);
			}
			nodetmp = tmp;
		}
	}

	// 插入节点 并处理可能的不平衡结点
	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);
		}
	}

	// 递归的插入结点，同时更新每个结点的高度
	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;
	}

	// 拼接旋转后的子树:用以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; // 父结点赋值非常关键！！
		}
	}

	// 获取待旋转结点的旋转类型
	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;
			}
		}
	}

	// 返回结点的平衡因子 返回值为-2 -1 0 1 2
	private int balance(BinaryTreeNode node) {
		if (node == null)
			return 0;
		return height(node.lchild) - height(node.rchild);
	}

	// 返货某个节点的高度
	private int height(BinaryTreeNode node) {
		if (node == null) {
			return -1;
		} else {
			return node.height;
		}
	}

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

	// 将node结点左旋，node是最小不平衡子树的根
	// LL
	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;
	}

	// LR
	public BinaryTreeNode leftRightRotate(BinaryTreeNode node) {
		node.lchild = rightRotate(node.lchild);
		node.lchild.parent = node;
		return leftRotate(node);
	}

	// RL
	public BinaryTreeNode rightLeftRotate(BinaryTreeNode node) {
		node.rchild = leftRotate(node.rchild);
		node.rchild.parent = node;
		return rightRotate(node);
	}

}

public class foreachransack { public static void main(string[] args) { int array[][][] = new int[][][]{ //创建并初始化数组 { { 1, 2, 3 }, { 4, 5, 6 } }, { { 7, 8, 9 }, { 10, 11, 12 } }, { { 13, 14, 15 }, { 16, 17, 18 } } }。preg_grep ( string $pattern , array $input [, int $flags = 0 ] ) //返回给定数组input中与模式pattern匹配的元素组成的数组.。js中的数组可以使用array()来创建:var arr1 = new array(1,2,"3")，也可以使用数组直接量来创建var arr = [1,2,"3"],所以本质上这两个是一样的。

public static void main(String[] args) {
		AVLTree avl = new AVLTree();
		int[] array = { 1, 9, 2, 7, 4, 5, 3, 6, 8 };
		avl.createTree(array);
		System.out.println("层序打印结点和其高度");
		avl.levelOrderH();
		System.out.println("删除结点7得到的层序遍历");
		avl.deleteAVL(avl.search(avl.root, 7));
		avl.levelOrderH();
	}

输出

层序打印结点和其高度
4  
2  7  
1  3  5  9  
6  8  

删除结点7得到的层序遍历
4  
2  8  
1  3  5  9  
6 

可以发现，前面将该数组创建成BST，树高非常高，现在将其创建成AVL树，发现非常的平衡，树高比之前低多了。并且在动态插入和删除过程中始终能维护树的平衡性。

分析该数组的创建和删除结点的过程

上述的代码在通过该数组创建AVL树的过程如下

删除结点7的过程如下图

可能最后的代码才200行左右，但是编些难度不小，比起写个应用分分钟上千行代码难多了，改bug改了一个晚上。由于我在这里每个节点保存父结点，所以好几次忘记给父结点赋，旋转的时候，由于指针变化也会产生好多问题，编写代码的过程中遇到导致错误的地方都标注在代码中。

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