基于二分搜索树的集合的实现

基于二分搜索树的集合的实现

  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
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
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
package SetBasicsAndBSTSet;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
* @ Description: 二分搜索树的实现
* @ Date: Created in 08:59 20/07/2018
* @ Author: Anthony_Duan
*/
public class BST<E extends Comparable<E>> {
private class Node {
private E e;
public Node left, right;

public Node(E e) {
this.e = e;
left = null;
right = null;
}
}

private Node root;
private int size;


public BST() {
root = null;
size = 0;
}


public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}


/**
* 向以node为根的二分搜索树中插入元素e 递归算法
*
* @param node 当前要插入二分搜索树的根
* @param e 元素e
* @return 当前调用过程中的二分搜索树的根
*/
private Node add(Node node, E e) {

//递归的终止条件,如果当前要插入树为空则该节点就是要如节点的地方
if (node == null) {
size++;
return new Node(e);
}

//如果小于当前节点则把左子树传入递归方法
if (e.compareTo(node.e) < 0) {
//需要注意的是这里返回的node.left 每次add方法返回的都会有一个节点
//如果是终止条件返回的是插入元素的节点,如果是中间的递归程序返回的是 当前节点node 并不会改变当前节点node的地址
node.left = add(node.left, e);
} else if (e.compareTo(node.e) > 0) {
node.right = add(node.right, e);
}
//这里很重要
return node;
}

/**
* 用户调用这个方法
*
* @param e
*/
public void add(E e) {
root = add(root, e);
}

private boolean contains(Node node, E e) {
if (node == null) {
return false;
}
if (e.compareTo(node.e) == 0) {
return true;
} else if (e.compareTo(e) < 0) {
return contains(node.left, e);
} else {
return contains(node.right, e);
}
}

/**
* 用户调用这个方法
* 看二分搜索树中是否包含元素e
*
* @param e
* @return
*/
public boolean contains(E e) {
return contains(root, e);
}

/**
* 二分搜索树的前序遍历
*
* @param node
*/
private void preOrder(Node node) {
if (node == null) {
return;
}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}


/**
* 用栈完成二分搜索树的非递归前序遍历
*/
private void preOrderNR() {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node cur = stack.pop();
System.out.println(cur.e);

if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}

public void preOrder() {
preOrder(root);
}


/**
* 后序遍历
*
* @param node
*/
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}

public void postOrder() {
postOrder(root);
}

/**
* 中序遍历
*
* @param node
*/
private void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}

public void inOrder() {
inOrder(root);
}


//二分搜索树的层序遍历
public void levelOrder() {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node cur = queue.remove();
System.out.println(cur.e);
if (cur.left != null) {
queue.add(cur);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}

/**
* 寻找二分搜索树的最小元素
*
* @return
*/
public E minimum() {
if (size == 0) {
throw new IllegalArgumentException("BST is empty!");
}
return minimum(root).e;
}

/**
* 返回二分搜索树中最小值所在的节点
*
* @param node
* @return
*/
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}

/**
* 寻找二分搜索树中的最大元素
*
* @return
*/
public E maximum() {
if (size == 0) {
throw new IllegalArgumentException("BST is empty!");
}
return maximum(root).e;
}

/**
* 返回以node为根的二分搜索树的最大值所在的节点
*
* @param node
* @return
*/
private Node maximum(Node node) {
if (node.right == null) {
return node;
}
return maximum(node.right);
}

/**
* 从二分搜索树中删除最小值所在的节点,返回最小值
*
* @return
*/
public E removeMin() {
E ret = minimum();
root = removeMin(root);
return ret;
}

/**
* 删除掉以node为根的二分搜索树中的最小节点
* 返回删除节点后新的二分搜索树的根
*
* @param node
* @return
*/
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}

/**
* 删除二分搜索树中最大值所在的节点
*
* @return
*/
public E removeMax() {
E ret = maximum();
root = removeMax(root);
return ret;
}

/**
* 删除掉以node为根的二分搜索树中的最大节点
* 返回删除后的新二分搜索树的根
*
* @param node
* @return
*/
private Node removeMax(Node node) {
if (node.right == null) {
Node leftNode = node.left;
node.right = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}


/**
* 从二分搜索树中删除元素为e 的节点
*
* @param e
*/
public void remove(E e) {
root = remove(root, e);
}

/**
* 删除掉以node为根的二分搜索树中值为e 的节点 递归算法
* 返回删除节点后新的二分搜索树的根
*
* @param node
* @param e
* @return
*/
private Node remove(Node node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {//e.compareTo(node.e)==0

//如果左子树为空
if (node.left == null) {
Node righNode = node.right;
node.right = null;
size--;
return righNode;
}
//如果右子树为空
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}

/**
* 左右子树都不为空的情况下
* 首先找到比待删除节点大的最小的节点 即待删除节点右子树中的最小节点
* 用这个节点替代删除节点的位置
*/
Node successor = minimum(node.right);
successor.left = node.left;
//这里removeMax方法中已经有了size--,所以这里不需要再对size进行维护
successor.right = removeMax(node.right);

node.left = node.right = null;
return successor;


}
}


private void generaterString(Node node, int depth, StringBuilder res) {

if (node == null) {
res.append(generaterDepthString(depth) + "null\n");
return;
}


res.append(generaterDepthString(depth) + node.e + "\n");
generaterString(node.left, depth + 1, res);
generaterString(node.right, depth + 1, res);
}

private String generaterDepthString(int depth) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < depth; i++) {
res.append("--");
}
return res.toString();
}

@Override
public String toString() {
StringBuilder res = new StringBuilder();
generaterString(root, 0, res);
return res.toString();
}
}

集合接口类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package SetBasicsAndBSTSet;

/**
* @ Description: 集合接口
* @ Date: Created in 20:24 20/07/2018
* @ Author: Anthony_Duan
*/
public interface Set<E> {
void add(E e);

boolean contains(E e);

void remove(E e);

int getSize();

boolean isEmpty();
}

集合类

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
package SetBasicsAndBSTSet;

/**
* @ Description: 基于二分搜索树的集合的实现
* @ Date: Created in 20:25 20/07/2018
* @ Author: Anthony_Duan
*/
public class BSTSet<E extends Comparable<E>> implements Set<E> {

private BST<E> bst;

public BSTSet() {
bst = new BST<>();
}


@Override
public void add(E e) {
bst.add(e);
}

@Override
public boolean contains(E e) {
return bst.contains(e);
}

@Override
public void remove(E e) {
bst.remove(e);
}

@Override
public int getSize() {
return bst.size();
}

@Override
public boolean isEmpty() {
return bst.isEmpty();
}
}

  1. 基于链表实现集合
    思路与用二分搜索树一样。也是实现set接口即可
    链表实现类
    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
    package LinkedList;

    /**
    * @ Description: 带虚拟节点的链表
    * @ Date: Created in 13:23 12/07/2018
    * @ Author: Anthony_Duan
    */
    public class LinkedList<E> {

    private class Node {

    public E e;

    public Node next;

    public Node(E e, Node next) {
    this.e = e;
    this.next = next;
    }

    public Node() {
    this(null, null);
    }


    @Override
    public String toString() {
    return e.toString();
    }
    }


    private Node dummyHead;
    private int size;

    public LinkedList() {
    dummyHead = new Node();
    size = 0;
    }

    public int getSize() {
    return size;
    }

    public boolean isEmpty() {
    return size == 0;
    }

    public void add(int index, E e) {
    if (index < 0 || index > size) {
    throw new IllegalArgumentException("Add failed. Illegal index.");
    }
    Node prev = dummyHead;
    for (int i = 0; i < index; i++) {
    prev = prev.next;
    }
    prev.next = new Node(e, prev.next);
    size++;
    }

    public void addFirst(E e) {
    add(0, e);
    }

    public void addLast(E e) {
    add(size, e);
    }


    public E get(int index) {
    if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Get failed. Illegal index.");
    }
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
    cur = cur.next;
    }
    return cur.e;
    }

    public E getFirst() {
    return get(0);
    }

    public E getLast() {
    return get(size);
    }

    public void set(int index, E e) {
    if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Set failed. Illegal index.");
    }
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
    cur = cur.next;
    }
    cur.e = e;
    }


    public boolean contains(E e) {
    Node cur = dummyHead.next;
    while (cur != null) {
    if (cur.e.equals(e)) {
    return true;
    }
    cur = cur.next;
    }
    return false;
    }

    public E remove(int index) {
    if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Remove failed. Index is illegal.");
    }
    Node prev = dummyHead;
    for (int i = 0; i < index; i++) {
    prev = prev.next;
    }

    Node retNode = prev.next;
    prev.next = retNode.next;
    retNode.next = null;
    size--;
    return retNode.e;
    }


    public E removeFirst() {
    return remove(0);
    }

    public E removeLast() {
    return remove(size - 1);
    }

    public void removeElement(E e) {
    Node prev = dummyHead;
    while (prev.next != null) {
    if (prev.next.e.equals(e)) {
    break;
    }
    prev = prev.next;
    }

    if (prev.next != null) {
    Node delNode = prev.next;
    prev.next = delNode.next;
    delNode.next = null;
    size--;
    }


    }

    @Override
    public String toString() {
    StringBuilder res = new StringBuilder();

    Node cur = dummyHead.next;
    while (cur != null) {
    res.append(cur + "->");
    cur = cur.next;
    }
    res.append("NULL");

    return res.toString();
    }

    }

链表实现的集合类

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
package SetBasicsAndBSTSet;

import LinkedList.LinkedList;

import java.util.ArrayList;

/**
* @ Description:
* @ Date: Created in 21:19 20/07/2018
* @ Author: Anthony_Duan
*/
public class LinkedListSet<E> implements Set<E> {


private LinkedList<E> list;

public LinkedListSet() {
list = new LinkedList<E>();
}

//O(n)
@Override
public void add(E e) {
if (!list.contains(e)) {
list.addFirst(e);
}
}

//O(n)
@Override
public boolean contains(E e) {
return list.contains(e);
}

//O(n)
@Override
public void remove(E e) {
list.removeElement(e);
}

@Override
public int getSize() {
return list.getSize();
}

@Override
public boolean isEmpty() {
return list.isEmpty();
}


public static void main(String[] args) {

System.out.println("Pride and Prejudice");

ArrayList<String> words1 = new ArrayList<>();
if (FileOperation.readFile("/Users/duanjiaxing/IdeaProjects/Data-Structure/data-structure/src/SetBasicsAndBSTSet/pride-and-prejudice.txt", words1)) {
System.out.println("Total words: " + words1.size());

LinkedListSet<String> set1 = new LinkedListSet<>();
for (String word : words1)
set1.add(word);
System.out.println("Total different words: " + set1.getSize());
}

System.out.println();


System.out.println("A Tale of Two Cities");

ArrayList<String> words2 = new ArrayList<>();
if (FileOperation.readFile("/Users/duanjiaxing/IdeaProjects/Data-Structure/data-structure/src/SetBasicsAndBSTSet/a-tale-of-two-cities.txt", words2)) {
System.out.println("Total words: " + words2.size());

LinkedListSet<String> set2 = new LinkedListSet<>();
for (String word : words2)
set2.add(word);
System.out.println("Total different words: " + set2.getSize());
}
}
}

基于链表和二分搜索树实现集合的实现复杂度分析

操作 LinkedListSet BSTSet 平均
增(add) O(n) O(h) o(logn)
删(delete) O(n) O(h) o(logn)
查(contains) O(n) O(h) o(logn)
-------------End Of This ArticleThank You For Reading-------------