平衡二叉树

基本介绍

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

一棵AVL树有如下必要条件：

  1. 条件一：它必须是二叉排序树。
  2. 条件二：每个节点的左子树和右子树的高度差至多为1。

AVL树的平衡调整

左旋转：

问题：当插入8 时，rightHeight() - leftHeight() > 1 成立，此时，不再是一颗avl树了.

怎么处理–进行左旋转：

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

右旋转：

问题：当插入6 时，leftHeight() - rightHeight() > 1 成立，此时，不再是一颗avl树了.

怎么处理–进行右旋转

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

双旋转：

问题: 当插入9 时，leftHeight() - rightHeight() > 1 ，此时右旋转进行平衡，发现右旋转后还不是一颗avl树

在满足右旋转条件时，要判断：

  1. 如果左子树的右子树高度大于左子树的左子树高度时
  2. 就对当前根节点的左子树，先进行左旋转
  3. 然后再对当前根节点进行右旋转即可
  4. 否则，直接对当前节点（根节点）进行右旋转即可.

同理，在满足左旋转条件时，要判断：

  1. 如果右子树的左子树高度大于右子树的右子树高度时
  2. 就对当前根节点的右子树，先进行右旋转
  3. 然后再对当前根节点进行左旋转即可
  4. 否则，直接对当前节点（根节点）进行左旋转即可.

判断树的高度的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 返回左子树的高度
public int leftHeight() {
	if (left == null) {
		return 0;
	}
	return left.height();
}

// 返回右子树的高度
public int rightHeight() {
	if (right == null) {
		return 0;
	}
	return right.height();
}

// 返回以该结点为根结点的树的高度
public int height() {
	return Math.max(this.left == null ? 0 : left.height(), this.right == null ? 0 : right.height()) + 1;
}

左旋转和右旋转的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 左旋转方法
private void leftRotate() {
	// 创建新的结点，以当前根结点的值
	Node newNode = new Node(value);
	// 把新的结点的左子树设置成当前结点的左子树
	newNode.left = left;
	// 把新的结点的右子树设置成当前结点的右子树的左子树
	newNode.right = right.left;
	// 把当前结点的值替换成右子结点的值
	value = right.value;
	// 把当前结点的右子树设置成当前结点右子树的右子树
	right = right.right;
	// 把当前结点的左子树(左子结点)设置成新的结点
	left = newNode;
}

// 右旋转方法
private void rightRotate() {
	Node newNode = new Node(value);
	newNode.right = right;
	newNode.left = left.right;
	value = left.value;
	left = left.left;
	right = newNode;
}

添加节点时的平衡代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public void add(Node node) {
		if (node == null) {
			return;
		}
		if (node.value < this.value) {
			if (this.left == null) {
				this.left = node;
			} else {
				this.left.add(node);
			}
		} else {
			if (this.right == null) {
				this.right = node;
			} else {
				this.right.add(node);
			}
		}

		// 当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
		if (rightHeight() - leftHeight() > 1) {
			// 如果它的右子树的左子树的高度大于它的右子树的右子树的高度
			if (right != null && right.leftHeight() > right.rightHeight()) {
				// 先对右子结点进行右旋转
				right.rightRotate();
				// 然后在对当前结点进行左旋转
				leftRotate(); // 左旋转..
			} else {
				// 直接进行左旋转即可
				leftRotate();
			}
			return; // 必须要!!!
			//这个return我也不知道要干嘛，可能为了不进行下面的判断提高效率
		}

		// 当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
		if (leftHeight() - rightHeight() > 1) {
			// 如果它的左子树的右子树高度大于它的左子树的左子树的高度
			if (left != null && left.rightHeight() > left.leftHeight()) {
				// 先对当前结点的左结点(左子树)->左旋转
				left.leftRotate();
				// 再对当前结点进行右旋转
				rightRotate();
			} else {
				// 直接进行右旋转即可
				rightRotate();
			}
		}
	}