平衡二叉树的基本原理和实现方法（Java）_二叉树基本原理方法

平衡二叉树（AVL树）的来源：

看一个案例(说明二叉排序树可能的问题)
给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在.
BST 存在的问题分析:
1）、左子树全部为空，从形式上看，更像一个单链表.
2）、插入速度没有影响
3)、查询速度明显降低(因为需要依次比较), 不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
解决方案-平衡二叉树(AVL)

平衡二叉树（AVL树）的基本介绍：

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

案例分析：

要求: 给你一个数列，创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}==>左旋转
要求: 给你一个数列，创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}==>右旋转

思路分析：

左旋转：

1、 创建一个新的节点 newNode (以4这个值创建),创建一个新的节点，值等于当前 根节点的值
Node newNode = new Node(value);
2、把新节点的左子树设置了当前节点的左子树
newNode.left = left
3、把新节点的右子树设置为当前节点的右子树的左子树
newNode.right =right.left;
4、把当前节点的值换为右子节点的值
value=right.value;
5、把当前节点的右子树设置成右子树的右子树
right=right.right;
6、把当前节点的左子树设置为新节点
left=newLeft;
（左旋转后的二叉树的示意图如下：）
右旋转：
1、 创建一个新的结点，值等于当前子节点的值
Node newNode = new Node(value);
2、 把新结点的右子树设置为当前结点的右子树
newNode.right = right;
3、 把新结点的左子树设置为当前结点的左子树的右子树
newNode.left = left.right;
4、把当前节点的值换为左子节点的值
newNode.value = left.value;
5、 把当前节点的左子树设置成左子树的左子树
left = left.left;
6、把当前节点的右子树设置为新节点
right = newNode;
（右旋转后二叉树的示意图如下：）

注意：

当int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL树，此时的二叉树转换成了如图所示的非平衡二叉树

解决方法：

1. 1).当符号右旋转的条件时：

   如果它的左子树的右子树高度大于它的左子树的高度
   2. 先对当前这个结点的左节点进行左旋转
   3. 在对当前结点进行右旋转的操作即可

2. 2).当符号左旋转的条件时：

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

详细代码：

package Tree.avl;

public class AVLTreeDemo {

	public static void main(String[] args) {
//		int[] arr = { 4, 3, 6, 5, 7, 8 };
//		int[] arr = { 10, 12, 8, 9, 7, 6 };
		int[] arr = { 10, 11, 7, 6, 8, 9 };  
		AVLTree avlTree = new AVLTree();
		for (int i = 0; i < arr.length; i++) {
			avlTree.add(new Node(arr[i]));
		}
		System.out.println("中序遍历");
		avlTree.infixOrder();
		System.out.println("平衡处理：");
		System.out.println("树的高度：" + avlTree.getRoot().height());
		System.out.println("左子树的高度" + avlTree.getRoot().left.height());
		System.out.println("右子树的高度" + avlTree.getRoot().right.height());
	}

}

//创建二叉树
class AVLTree {
	private Node root;

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}

	// 向二叉树中添加元素
	public void add(Node node) {
		if (root == null) {
			root = node;
		} else {
			root.add(node);
		}
	}

	// 中序遍历二叉树
	public void infixOrder() {
		if (root == null) {
			System.out.println("树为空");
		} else {
			root.infixOrder();
		}
	}
}

//创建二叉树的结点类
class Node {
	int value;
	Node left;
	Node right;

	public Node(int value) {
		this.value = value;
	}

	// 返回左子树的高度
	public int leftHeight() {
		if (left == null) {
			return 0;
		} else {
			return left.height();
		}
	}

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

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

	// 左旋转方法
	private void leftRotate() {
		// 创建一个新的结点，值等于当前根节点的值
		Node newNode = new Node(value);
		// 把新节点的左子树设置成当前结点的左子树
		newNode.left = left;
		// 把新节点的右子树设置成当前结点的右子树的左子树
		newNode.right = right.left;
		// 把当前结点的值替换为右子结点的值
		newNode.value = right.value;
		// 把当前结点的右子树设置成右子树的右子树
		right = right.right;
		// 把当前结点的左子树设置成新节点
		left = newNode;

	}

	// 右旋转方法
	private void rightRotate() {
		// 创建一个新的结点，值等于当前子节点的值
		Node newNode = new Node(value);
		// 把新结点的右子树设置为当前结点的右子树
		newNode.right = right;
		// 把新结点的左子树设置为当前结点的左子树的右子树
		newNode.left = left.right;
		// 把当前节点的值换为左子节点的值
		newNode.value = left.value;
		// 把当前节点的左子树设置成左子树的左子树
		left = left.left;
		// 把当前节点的右子树设置为新节点
		right = newNode;

	}

	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}

	public void add(Node node) {
		if (node == null) {
			return;
		}
		if (this.value > node.value) {// 要添加的node的值小于当前树的根节点的值
			if (this.left == null) {// 判断this的左节点是否为空
				this.left = node;// 为空就直接赋给左节点
			} else {
				// 开始从当前结点的左节点递归
				this.left.add(node);
			}
		} else {// 如果node大与this
			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;
		}
		// 当添加完一个结点后，（左子树的高度-右子树的高度）>1
		if (leftHeight() - rightHeight() > 1) {
			// .如果它的左子树的右子树高度大于它的左子树的高度
			if (left != null && left.rightHeight() > left.leftHeight()) {
				// 先对当前结点的左节点进行左旋转
				left.leftRotate();
				rightRotate();
			} else {
				rightRotate();// 右旋转
			}
		}
	}

	// 中序遍历二叉树
	public void infixOrder() {
		if (this.left != null) {
			this.left.infixOrder();
		}
		System.out.println(this);
		if (this.right != null) {
			this.right.infixOrder();
		}
	}
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180