数据结构——二叉搜索树(BinarySearchTree)的实现

发表于   |   分类于 ，   |     |   阅读次数

二叉搜索树是二叉树的一种扩展。树中的元素可以看作是有序的。由于特殊的结构，它非常适合进行二分查找操作，且查找的平均时间复杂度为O(logN)。不过其也可能退化为一个链表，此时查找的最坏时间复杂度变为O(N)。

特点

  对于树中的任意节点X，它大于它的左子树中的所有节点值，且小于它的右子树中的所有节点值。（假设树中的元素都是互异的，不存在相等的元素值）

BinarySearchTree

  本次实现中对于树中存储的元素并没有要求必须要实现Comparable接口。而是同时结合了Comparator和Comparable接口。使用者可以在构造二叉搜索树时传入一个自定义的比较器，或者不使用比较器而是在存储的元素中实现Comparable接口（此时Comparable接口必须实现）。

成员变量

  1. private BinaryNode root; //二叉搜索树的根节点
  2. private Comparator cmp; //元素的自定义比较器

构造器

  有两个构造器，其中一个是含参的构造器，可以传入一个自定义的比较器。在构造器中主要是初始化树根节点。

1
2
3
4
5
6
7
public BinarySearchTree(){
	this(null);
}
public BinarySearchTree(Comparator<T> cmp){
	this.cmp = null;
}

函数

1
2
3
4
5
6
7
8
9
10
11
public void setComparator(Comparator<T> cmp){
	this.cmp = cmp;
}
public boolean isEmpty(){
	return root == null;
}
public void clearTree(){
	root = null;
}

  内部比较方法，比较两个数的大小并返回结果。在方法中会判断是否有自定义比较器，有则用自定义比较器比较两个数大小，否则使用Comparable接口的comparaTo函数进行比较。

1
2
3
4
5
6
7
@SuppressWarnings("unchecked")
private int innerCompareTo(T lhs, T rhs){
	if(cmp != null)
		return cmp.compare(lhs, rhs);
	else
		return ((Comparable<T>)lhs).compareTo(rhs);
}

  contains()：查找树中是否包含某个元素，用递归的方法进行二分搜索。二分搜索法：用待查找的值x与当前结点比较，如果比节点值小，则在其左子树继续搜索；如果x比当前节点值大，则在其右子树中搜索。重复以上操作直到根节点位置，如果还没有搜索到匹配值则树中不包含x值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean contains(T x){
	return contains(x, root);
}
private boolean contains(T x, BinaryNode<T> tree){
	if(tree == null)
		return false;
	/* 通过比较x和节点的值,来决定在左子树还是右子树中继续递归查找 */
	int result = innerCompareTo(x, tree.element);
	if(result < 0)
		return contains(x, tree.left);
	else if(result > 0)
		return contains(x, tree.right);
	/* result = 0,说明已经查找到匹配的元素 */
	else
		return true;
}

  insert()：插入元素。每个元素都是作为树的新的叶子节点插入树中的。插入操作的平均时间复杂度为O(logN)，但是如果是有序的元素进行插入操作的话则会是最坏情况，时间复杂度为O(logN),且会得到一棵退化的二叉搜索树(变成链表)，这时候无论是删除还是查找操作时间复杂度就都变成了O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void insert(T x){
	root = insert(x, root);
}
private BinaryNode<T> insert(T x, BinaryNode<T> tree){
	/*是否插入第一个元素,或者是在叶子节点处插入元素*/
	if(tree == null)
		return new BinaryNode<T>(x);
	
	int result = innerCompareTo(x, tree.element);
	if(result < 0)
		tree.left = insert(x, tree.left);
	else if(result > 0)
		tree.right = insert(x, tree.right);
	else{
		//存在相同的元素，这里不做任何处理
	}
	return tree;
}

  remove()：删除元素x。二叉搜索树的删除操作还是相对比较简单的。待删除的节点主要为以下几种情况：

  1. 不存在该节点，删除失败；
  2. 待删除节点为叶子结点，则直接删除该节点；
  3. 待删除节点有一个孩子，只要删除该节点，将其孩子节点返回给其父节点即可；
  4. 待删除节点有两个孩子，这种情况下相对复杂一点点。通常的解决方法是用它的右子树中最小值替换节点值，然后删除右子树中的最小值即可（因为此时其右子树的最小值节点必没有左孩子，则变为2，3情况了）。但是这种删除元素的方法在若干次操作后可能会导致树失衡，即右子树高度普遍较低。所以我们可以采取随机删除右子树最小值或删除左子树最大值的方式。
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
public void remove(T x){
	root = remove(x, root);
}
private BinaryNode<T> remove(T x, BinaryNode<T> tree){
	/* 空树或者没找相应的元素 */
	if(tree == null)
		return null;
	
	int result = innerCompareTo(x, tree.element);
	/* 在左子树中删除元素 */
	if(result < 0)
		tree.left = remove(x, tree.left);
	/* 在右子树中删除元素 */
	else if(result > 0)
		tree.right = remove(x, tree.right);
	/* 1.找到匹配元素的节点,且该节点有左,右子节点 
	 * 这种情况一般用其右子树中的最小元素来替代这个节点值
	 * 然后再删除右子树中最小元素的那个节点(因为右子树最小节点没有左子树,则变为下面的情况之一（见2）)
	 */
	else if(tree.left != null && tree.right != null){
		tree.element = findMax();
	}
	/* 2.找到匹配元素,该元素为叶子结点或者只包含一个孩子节点
	 * - 如果是叶子节点则直接删除
	 * - 如果包含一个子节点，则将改子节点上提
	 */
	else{
		tree = (tree.left != null) ? tree.left : tree.right; 
	}
	return tree;
}

  findMin()：查询最小值。树中最小值为左子树中最小元素。采用递归实现。
  findMax()：查询最大值。树中最大值为右子树中最大元素。采用非递归实现。

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
	public T findMin(){
		return findMin(root);
	}
	private T findMin(BinaryNode<T> tree){
		/* 判断是不是空树 */
		if(tree == null)
			return null;
		/* 如果没有到达最左边的元素，则递归查找左子树的最小值 */
		else if(tree.left != null)
			return findMin(tree.left);
		/* 查找到最小值 */
		else
			return tree.element;
	}
	
	public T findMax(){
		return findMax(root);
	}
	private T findMax(BinaryNode<T> tree){
		/* 不是空树 */
		if(tree != null)
			/* 循环遍历直到右子树的最大值节点处,
			 * ps:此处的tree是一个拷贝引用,故不会影响原来树的结构.
			 * 这点在处理非递归时候需要时刻注意,不要改变原来的值！
			 * 例如 tree.right = tree.left这种操作是会破坏原来的树的结构的.
			 */
			while(tree.right != null)
				tree = tree.right;
		return tree.element;
	}
>print()：顺序输出树中的元素值。采用的中序遍历的方式实现。
	public void print(){
		print(root);
	}
	private void print(BinaryNode<T> tree){
		if(tree == null)
			return;
		print(tree.left);
		System.out.println(tree.element + " l:" + tree.left + " r:" + tree.right);
		print(tree.right);
	}
>height()：采用后序遍历的方式递归的求树的高度。
	public int height(){
		return height(root);
	}
	private int height(BinaryNode<T> tree){
		if(tree == null)
			return -1;
		/* 先计算左子树和右子树的高度,求出最大值,然后高度加一 */	
		else
			return 1 + Math.max(height(tree.left), height(tree.right));
	}

内部类

  内部类实现二叉搜索树的节点。节点主要维护了数据和左、右孩子节点的引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static class BinaryNode<T>{
	public T element;
	public BinaryNode<T> left;
	public BinaryNode<T> right;
	
	public BinaryNode(T ele){
		this(ele, null, null);
	}
	
	public BinaryNode(T ele, BinaryNode<T> l, BinaryNode<T> r){
		element = ele;
		left = l;
		right = r;
	}
}

源代码

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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
import java.util.Comparator;
/**
 * 二叉搜索树
 * @author Bingo
 *
 * @param <T> 泛型对象需要实现Comparable接口，或者可传入一个比较器
 */
public class BinarySearchTree <T>{
	/**
	 * 树的根节点
	 */
	private BinaryNode<T> root;
	
	/**
	 * 元素T的比较器
	 */
	private Comparator<T> cmp;
	
	/**
	 * 默认不带比较器的构造器
	 */
	public BinarySearchTree(){
		this(null);
	}
	
	/**
	 * 带比较器的构造器
	 * @param cmp 比较器
	 */
	public BinarySearchTree(Comparator<T> cmp){
		this.cmp = null;
	}
	
	/**
	 * 设置新的比较器
	 * @param cmp
	 */
	public void setComparator(Comparator<T> cmp){
		this.cmp = cmp;
	}
	
	public boolean isEmpty(){
		return root == null;
	}
	
	public void clearTree(){
		root = null;
	}
	
	public int height(){
		return height(root);
	}
	
	/**
	 * 查询树中是否包含元素x
	 * @param x 查询的元素
	 * @return 有匹配的元素返回true，否则返回false
	 */
	public boolean contains(T x){
		return contains(x, root);
	}
	
	/**
	 * 查找树中最小元素值
	 * @return
	 */
	public T findMin(){
		return findMin(root);
	}
	
	/**
	 * 查找树中最大元素值
	 * @return
	 */
	public T findMax(){
		return findMax(root);
	}
	
	/**
	 * 插入一个元素x
	 * @param x
	 */
	public void insert(T x){
		root = insert(x, root);
	}
	
	/**
	 * 移除元素x
	 * @param x
	 */
	public void remove(T x){
		root = remove(x, root);
	}
	
	/**
	 * 打印数的的内容
	 */
	public void print(){
		print(root);
	}
	/**
	 * 二分搜索的方法查询元素(递归版本)
	 * @param x
	 * @param tree
	 * @return
	 */
	private boolean contains(T x, BinaryNode<T> tree){
		if(tree == null)
			return false;
		/* 通过比较x和节点的值,来决定在左子树还是右子树中继续递归查找 */
		int result = innerCompareTo(x, tree.element);
		if(result < 0)
			return contains(x, tree.left);
		else if(result > 0)
			return contains(x, tree.right);
		/* result = 0,说明已经查找到匹配的元素 */
		else
			return true;
	}
	
	/**
	 * 采用递归的方式查找树中最小值.
	 * 根据二叉搜索树定义我们可以知道树中最小值就是左子树中最小值.
	 * @param tree
	 * @return
	 */
	private T findMin(BinaryNode<T> tree){
		/* 判断是不是空树 */
		if(tree == null)
			return null;
		/* 如果没有到达最左边的元素，则递归查找左子树的最小值 */
		else if(tree.left != null)
			return findMin(tree.left);
		/* 查找到最小值 */
		else
			return tree.element;
	}
	
	/**
	 * 采用非递归方式查找树中最大值
	 * 根据二叉搜索树定义我们可以知道树中最大值就是右子树中最大值.
	 * @param tree
	 * @return
	 */
	private T findMax(BinaryNode<T> tree){
		/* 不是空树 */
		if(tree != null)
			/* 循环遍历直到右子树的最大值节点处,
			 * ps:此处的tree是一个拷贝引用,故不会影响原来树的结构.
			 * 这点在处理非递归时候需要时刻注意,不要改变原来的值！
			 * 例如 tree.right = tree.left这种操作是会破坏原来的树的结构的.
			 */
			while(tree.right != null)
				tree = tree.right;
		return tree.element;
	}
	
	/**
	 * 插入一个新的元素x，如果该元素已经存在，则不做任何改变
	 * @param x 插入的元素
	 * @param tree
	 * @return
	 */
	private BinaryNode<T> insert(T x, BinaryNode<T> tree){
		/*是否插入第一个元素,或者是在叶子节点处插入元素*/
		if(tree == null)
			return new BinaryNode<T>(x);
		
		int result = innerCompareTo(x, tree.element);
		if(result < 0)
			tree.left = insert(x, tree.left);
		else if(result > 0)
			tree.right = insert(x, tree.right);
		else{
			//存在相同的元素，这里不做任何处理
		}
		return tree;
	}
	
	/**
	 * 移除元素x的节点
	 * @param x
	 * @param tree
	 * @return
	 */
	private BinaryNode<T> remove(T x, BinaryNode<T> tree){
		/* 空树或者没找相应的元素 */
		if(tree == null)
			return null;
		
		int result = innerCompareTo(x, tree.element);
		/* 在左子树中删除元素 */
		if(result < 0)
			tree.left = remove(x, tree.left);
		/* 在右子树中删除元素 */
		else if(result > 0)
			tree.right = remove(x, tree.right);
		/* 1.找到匹配元素的节点,且该节点有左,右子节点 
		 * 这种情况一般用其右子树中的最小元素来替代这个节点值
		 * 然后再删除右子树中最小元素的那个节点(因为右子树最小节点没有左子树,则变为下面的情况之一（见2）)
		 */
		else if(tree.left != null && tree.right != null){
			tree.element = findMax();
		}
		/* 2.找到匹配元素,该元素为叶子结点或者只包含一个孩子节点
		 * - 如果是叶子节点则直接删除
		 * - 如果包含一个子节点，则将改子节点上提
		 */
		else{
			tree = (tree.left != null) ? tree.left : tree.right; 
		}
		return tree;
	}
	
	/**
	 * 中序遍历输出的方式,吧树中元素按从小到大输出
	 * @param tree
	 */
	private void print(BinaryNode<T> tree){
		if(tree == null)
			return;
		print(tree.left);
		System.out.println(tree.element + " l:" + tree.left + " r:" + tree.right);
		print(tree.right);
	}
	
	/**
	 * 内部方法,利用后序遍历计算树的高度
	 */
	private int height(BinaryNode<T> tree){
		if(tree == null)
			return -1;
		/* 先计算左子树和右子树的高度,求出最大值,然后高度加一 */	
		else
			return 1 + Math.max(height(tree.left), height(tree.right));
	}
	
	/**
	 * 内部比较方法
	 * @param lhs
	 * @param rhs
	 * @return
	 */
	@SuppressWarnings("unchecked")
	private int innerCompareTo(T lhs, T rhs){
		if(cmp != null)
			return cmp.compare(lhs, rhs);
		else
			return ((Comparable<T>)lhs).compareTo(rhs);
	}
	
	/**
	 * 私有类，二叉搜索树中的节点类
	 * @author Bingo
	 *
	 * @param <T>
	 */
	private static class BinaryNode<T>{
		public T element;
		public BinaryNode<T> left;
		public BinaryNode<T> right;
		
		public BinaryNode(T ele){
			this(ele, null, null);
		}
		
		public BinaryNode(T ele, BinaryNode<T> l, BinaryNode<T> r){
			element = ele;
			left = l;
			right = r;
		}
	}
}