本文共 2695 字，大约阅读时间需要 8 分钟。

当对一个数组[1,2,3,4,5,6,]创建排序二叉树的时候看起来更像是一个链表，这个时候就需要使用到平衡二叉树。

基本介绍

1. 平衡二叉树也叫平衡二叉搜索树(Self-balancing binarysearchtree)又被称为AVL树，可以保证查询效率较高。
2. 具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、 伸展树等。

二叉排序树和平衡二叉树的转化

进行左旋转.

1. 创建一个新的节点newNode (以4这个值创建)，创建一个新的节点，值等于当前根节点的值，把新节点的左子树设置成当前节点的左子树：newNode.left = left
2. 把新节点的右子树设置为当前节点的右子树的左子树：newNode.right =right，
3. 把当前节点的值换为右子节点的值：value=right.value;
4. 把当前节点的右子树设置成右子树的右子树：right=right.right ，
5. 把当前节点的左子树设置为新节点：left=newNode;

// 返回左子树的高度	public int leftHight() {
   		if (left == null) {
   			return 0;		}		return left.hight();	}	// 返回右子树的高度	public int rightHight() {
   		if (right == null) {
   			return 0;		}		return right.hight();	}	// 返回当前节点的高度,以该节点为根节点的这棵树的高度	public int hight() {
   		return Math.max(left == null ? 0 : left.hight(), right == null ? 0 : right.hight()) + 1;	}	// 左旋转	public void leftRotate() {
   		// 创建新节点,用当前的根节点		Node newnode = new Node(value);		// 把新节点的左子树设置成当前节点的左子树		newnode.left = left;		// 把新节点的右子树设置为当前节点的右子树的左子树		newnode.right = right.left;		// 把当前节点的值换为右子节点的值		value = right.value;		// 把当前节点的右子树设置成右子树的右子树：		right = right.right;		// 把当前节点的左子树设置为新节点		left = newnode;	}

以及在进行add添加节点的时候加上判断语句，表示判断是否进行左旋转

// 添加完一个节点之后,右子树的高度减左子树的高度大于一		if (rightHight() - leftHight() > 1) {
   			leftRotate();		}

最后进行测试：

public static void main(String[] args) {
   		int [] arr= {
   4,3,6,5,7,8};		AVL avl = new AVL();		// 添加节点		for (int i = 0; i < arr.length; i++) {
   			avl.add(new Node(arr[i]));		}		// 前序遍历		avl.DLR();		System.out.println("处理之后：");		System.out.println("树高 = " + avl.getRoot().hight());// 4 // 4		System.out.println("左子树高 = " + avl.getRoot().leftHight());// 1 //3		System.out.println("右子树高 = " + avl.getRoot().rightHight());// 3 //1		System.out.println("根节点 =" + avl.getRoot()); // 4 //6	}

查看结果：

进行右选择，当一棵树的左子树的高度 - 右子树的高度大于一的时候进行右旋转，原理与左旋转相同，

// 右旋转	public void rightRotate() {
   		// 创建新节点,用当前的根节点		Node newnode = new Node(value);		// 把新节点的右子树设置成当前节点的右子树		newnode.right = right;		newnode.left = left.right;		value = left.value;		left = left.left;		right = newnode;	}

在add添加节点方法当中添加判断是否进行右旋转：

if (leftHight() - rightHight() > 1) {
   			rightRotate();		}

使用一个新的数组进行测试：

进行双旋转.

1. 当符号右旋转的条件时
2. 如果它的左子树的右子树高度大于它的左子树的高度
3. 先对当前这个结点的左节点进行左旋转
4. 再对当前结点进行右旋转的操作即可

if (rightHight() - leftHight() > 1) {			if (right != null && right.rightHight() < right.leftHight()) {				right.rightRotate();			}			leftRotate();			return ;		}		if (leftHight() - rightHight() > 1) {			// 先左旋转，再右旋转			if (left != null && left.rightHight() > left.leftHight()) {				left.leftRotate();			}			rightRotate();		}

测试数组 int[] arr = { 10, 7, 15, 6, 8, 9 };这个数组生成的二叉排序树就是需要进行双旋转，旋转过后参照上图：

转载地址：http://sgmzi.baihongyu.com/