手撕AVL树

欢迎查看Eetal的第十五篇博客–手撕AVL树

BST

BINARY SEARCH TREE二叉查找树，代表树中节点为有序存储
所有节点都相同满足以下条件之一
1.左子节点值大于等于根节点值且右子节点值小于根节点值
2.左子节点值小于等于根节点值且右子节点值大于根节点值
的二叉树即位二叉查找树
AVL average BST 是一棵平衡的二叉查找树，通过平衡使得单次查找的时间复杂度不会超过logn

AVL Tree

平衡树的特点是，任意一个节点，其左子树的高度与右子树的高度差保持在1以内（包括1）
当出现高度差超过1的子树则进行旋转来调整，旋转时不破坏有序

旋转

右旋转

假设左边过高（一般这种过高表现为高度差为2，因为我们应在每次进行插入和删除时旋转进行维护，所以不会出现高度差为3的情况）
普通右旋
这时我们通过这种右旋转可以把左边过高子树的一个节点提上来，使得左子树节点高度-1，右子树节点高度+1
伪代码就是
parent = 要旋转的节点
将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树
将parent从他父亲断开，将parent作为他原来的左子节点（被断开的左子节点）的右子树
最后将parent原来的父亲作为此时parent新的父节点（原来的左子节点）的父亲（就是交换位置）

代码实现

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
public Node rightTransformAndReturn(Node node) {
	System.out.println("right transform");
	Node left = node.leftChild;
	Node leftRightChild = left.rightChild;
	if(leftRightChild!=null) {
		leftRightChild.parent = node;
		leftRightChild.status = LEFTSTATUS;
	}
	node.leftChild = leftRightChild;
	left.rightChild = node;
	left.parent = node.parent;
	node.parent = left;
	left.status = node.status;
	if(node.status == LEFTSTATUS) {
		left.parent.leftChild = left;
	}
	else if(node.status == RIGHTSTATUS){
		left.parent.rightChild = left;
	}
	else {
		root = left;
	}
	node.status = RIGHTSTATUS;
	while(node!=null) {
		node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);
		node = node.parent;
	}
	node = left;
	return node;
}

上面只分析了第一种情况，有时左子树会是这样
特殊右旋
这时如果按照第一种的做法，此时最终结果会使得右子树高于左子树导致不平衡
原因是第一步里有 这一步

将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树

这一步是为了保证其有序不被破坏，所以从断开的是其左节点的右子树，也就是这颗右子树高度是不变的
而后右子树又会链接到parent，如果导致树高的不平衡是这颗右子树造成，则旋转后其仍是不平衡的（因为左边减少的高度1实际是左子树的高度）

于是我们得想办法把他变回第一种情况，做法就是，先使用左旋转其parent的左子树，将其变为下图
特殊右旋
这时就可以使用第一种情况的方法来应对了
至于为什么只要一次右旋转因为一开始我们就讲过，高度差不会超过2，那平衡的子树的左右结点高度差就不会超过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
26
27
28
29
30
public Node leftTransformAndReturn(Node node) {
	System.out.println("left transform");
	Node right = node.rightChild;
	Node rightLeftChild = right.leftChild;
	if(rightLeftChild!=null) {
		rightLeftChild.parent = node;
		rightLeftChild.status = RIGHTSTATUS;
	}
	node.rightChild = rightLeftChild;
	right.leftChild = node;
	right.parent = node.parent;
	node.parent = right;
	right.status = node.status;
	if(node.status == LEFTSTATUS) {
		right.parent.leftChild = right;
	}
	else if(node.status == RIGHTSTATUS){
		right.parent.rightChild = right;
	}
	else {
		root = right;
	}
	node.status = LEFTSTATUS;
	while(node!=null) {
		node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);
		node = node.parent;
	}
	node = right;
	return node;
}

最终代码

我们将上方阐述的特殊情况（左旋转的可以联想都是对应的）总结，把对于两种情况的处理都封装
使用递归实现

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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

public class AVLTree {

	Node root;
	static final int LEFTSTATUS = 0;
	static final int RIGHTSTATUS = 1;

	static class Node{
		int num;
		Node leftChild;
		Node rightChild;
		Node parent;
		int height = 0;
		int status = -1;//root
		@Override
		public String toString() {
			return num+",height["+height+"]->left["+(leftChild==null?"null":leftChild.num)+"],->right["+(rightChild==null?"null":rightChild.num)+"]";
		}
		
	}
	public void printTree(Node parent) {
		if(parent!=null) {
			System.out.println(parent);
			printTree(parent.leftChild);
			printTree(parent.rightChild);
		}
	}
	//注意，左旋右旋会改变原来的父节点位置的节点(包括root)
	public Node leftTransformAndReturn(Node node) {
		System.out.println("left transform");
		Node right = node.rightChild;
		//双旋转
		if(getHeight(right.leftChild)>getHeight(right.rightChild)) {
			rightTransformAndReturn(right);
		}
		Node rightLeftChild = right.leftChild;
		if(rightLeftChild!=null) {
			rightLeftChild.parent = node;
			rightLeftChild.status = RIGHTSTATUS;
		}
		node.rightChild = rightLeftChild;
		right.leftChild = node;
		right.parent = node.parent;
		node.parent = right;
		right.status = node.status;
		if(node.status == LEFTSTATUS) {
			right.parent.leftChild = right;
		}
		else if(node.status == RIGHTSTATUS){
			right.parent.rightChild = right;
		}
		else {
			root = right;
		}
		node.status = LEFTSTATUS;
		while(node!=null) {
			node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);
			node = node.parent;
		}
		node = right;
		return node;
	}
	public Node rightTransformAndReturn(Node node) {
		System.out.println("right transform");
		Node left = node.leftChild;
		//双旋转
		if(getHeight(left.rightChild)>getHeight(left.leftChild)) {
			leftTransformAndReturn(left);
		}
		Node leftRightChild = left.rightChild;
		if(leftRightChild!=null) {
			leftRightChild.parent = node;
			leftRightChild.status = LEFTSTATUS;
		}
		node.leftChild = leftRightChild;
		left.rightChild = node;
		left.parent = node.parent;
		node.parent = left;
		left.status = node.status;
		if(node.status == LEFTSTATUS) {
			left.parent.leftChild = left;
		}
		else if(node.status == RIGHTSTATUS){
			left.parent.rightChild = left;
		}
		else {
			root = left;
		}
		node.status = RIGHTSTATUS;
		while(node!=null) {
			node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);
			node = node.parent;
		}
		node = left;
		return node;
	}

	public int getHeight(Node node) {
		//获得树高，null为-1
		return node == null ? -1 : node.height;
	}
	public int getBF(Node node) {
		//获得平衡因子---左子树高-右子树高
		return  getHeight(node.leftChild)- getHeight(node.rightChild);
	}
	public void avl(Node parent) {
		if(parent == null) {
			return;
		}
		else {
			Node left = parent.leftChild;
			Node right = parent.rightChild;
			if(getHeight(right)>getHeight(left)+1) {
				leftTransformAndReturn(parent);
			}
			else if(getHeight(left)>getHeight(right)+1) {
				rightTransformAndReturn(parent);
			}
			else {
				avl(parent.parent);
			}
		}
	}
	public Node addAndReturnParent(Node node,Node parent) {
		if(parent == null) {
			root = parent = node;
		}
		else {
			if(parent.num>node.num) {
				//right add
				Node right = parent.rightChild;
				if(right == null) {
					node.parent = parent;
					node.status = RIGHTSTATUS;
					parent.rightChild = node;
					if(parent.leftChild == null) {
						Node temp = parent;
						temp.height++;
						boolean flag = true;
						while((temp=temp.parent)!=null && flag) {
							int oldHeight = temp.height;
							temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);
							flag = (oldHeight != temp.height);
						}
						avl(parent);
					}
				}
				else {
					addAndReturnParent(node,right);
				}
			}
			else {
				//left add
				Node left = parent.leftChild;
				if(left == null) {
					node.parent = parent;
					parent.leftChild = node;
					node.status = LEFTSTATUS;
					if(parent.rightChild == null) {
						Node temp = parent;
						temp.height++;
						boolean flag = true;
						while((temp=temp.parent)!=null && flag) {
							int oldHeight = temp.height;
							temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);
							flag = (oldHeight != temp.height);
						}
						avl(parent);
					}
				}
				else {
					addAndReturnParent(node,left);
				}
			}
		}
		return parent;
	}
	public Node addNum(int num) {
		Node node = new Node();
		node.num = num;
		addAndReturnParent(node, root);
		return node;
	}
	
	public Node findNum(int num) {
		Node node = root;
		while(node!=null) {
			if(node.num == num)
				break;
			else if(node.num<num)
				node = node.leftChild;
			else
				node = node.rightChild;
		}
		return node;
	}

}

节点删除

如果要删除节点，此时第一考虑树高，
1.如果是叶子节点我们可以直接删除，并调整树
2.不是叶子节点，找出一个作为替代的叶子节点，顶替其位置（只需要交换值），把问题变为第一种情况

具体的顶替查找就是，如果其左子树为空则左旋一次，变为叶子节点
如果右子树为空则右旋一次，变为叶子结点
如果都不为空，根据左右子树高度判断，
从高度大的一方查找替代后能保持有序的叶子节点（此处判断主要是为了优化减少旋转的次数，不判断选择一边也不影响，因为最终都会调整）
最后删除叶子节点后递归调整树

代码实现

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
public Node deleteNode(Node node) {
		System.out.println("delete Node...:"+node);
		if(node == null)
			return node;
		if(getHeight(node)==0) {
			Node parent = node.parent;
			node.parent = null;
			if(node == root) {
				root = null;
			}
			else if(node.status == LEFTSTATUS) {
				parent.leftChild = null;
				Node temp = parent;
				boolean flag = true;
				while((temp=temp.parent)!=null && flag) {
					int oldHeight = temp.height;
					temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);
					flag = (oldHeight != temp.height);
				}
				avl(parent);

			}
			else {
				parent.rightChild = null;
				Node temp = parent;
				boolean flag = true;
				while((temp=temp.parent)!=null && flag) {
					int oldHeight = temp.height;
					temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);
					flag = (oldHeight != temp.height);
				}
				avl(parent);
			}
			
		}
		else {
			if(node.leftChild == null) {
				leftTransformAndReturn(node);
				deleteNode(node);
			}
			else if(node.rightChild == null) {
				rightTransformAndReturn(node);
				deleteNode(node);
			}
			else if(getHeight(node.leftChild)>getHeight(node.rightChild)) {
				Node leftSmall = node.leftChild;
				while(leftSmall.rightChild!=null) {
					leftSmall = leftSmall.rightChild;
				}
				node.num ^= leftSmall.num;
				leftSmall.num ^= node.num;
				node.num ^= leftSmall.num;
				deleteNode(leftSmall);
			}
			else {
				Node rightBig = node.rightChild;
				while(rightBig.leftChild!=null) {
					rightBig = rightBig.leftChild;
				}
				node.num ^= rightBig.num;
				rightBig.num ^= node.num;
				node.num ^= rightBig.num;
				deleteNode(rightBig);
			}
		}
		return node;
	}
	public Node deleteNum(int num) {
		Node node = findNum(num);
		return deleteNode(node);
	}

请移步

个人主页: yangyitao.top