Java算法-查找(二叉搜索树)

二叉查找树是一棵二叉树,每个节点的键都大于左子树的任意节点的键,小于右子树的任意节点的键

二叉树的遍历方式分为先序,中序,后序,如下:

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 class Traversal<Key extends Comparable<Key>,Value> {
private Node root;
public class Node{
private Key key;
private Value val;
private Node left;
private Node right;
private int N;
public Node(Key key,Value val,int N){
this.key=key;
this.val=val;
this.N=N;
}
}
//先序遍历(根节点->左子树->右子树)
public void PreOrderTraversal(){
PreOrderTraversal(root);
}
//递归实现
private void PreOrderTraversal(Node x) {
if(x!=null){
System.out.println(x.key+"--->"+x.val);
PreOrderTraversal(x.left);
PreOrderTraversal(x.right);
}
}
/* //非递归实现
private void PreOrderTraversal(Node x){
}*/
//中序遍历(左子树->根节点->右子树)
//递归实现
private void InOrderTraversal(Node x) {
if(x!=null){
PreOrderTraversal(x.left);
System.out.println(x.key+"--->"+x.val);
PreOrderTraversal(x.right);
}
}
//后序遍历(左子树->右子树->根节点 )
//递归实现
private void PostOrderTraversal(Node x) {
if(x!=null){
PreOrderTraversal(x.left);
PreOrderTraversal(x.right);
System.out.println(x.key+"--->"+x.val);
}
}
}

基本操作算法:

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 BST<Key extends Comparable<Key>,Value> {
private Node root;
public class Node{
private Key key;
private Value val;
private Node left;
private Node right;
private int N;
public Node(Key key,Value val,int N){
this.key=key;
this.val=val;
this.N=N;
}
}
public int size(Node x){
if(x==null){
return 0;
}else{
return x.N;
}
}
public void put(Key key,Value val){
root=put(root,key,val);
}
private Node put(Node x,Key key,Value val){
if(x==null){
return new Node(key,val,1);
}
int cmp=key.compareTo(x.key);
if(cmp>0){
x.right=put(x.right,key,val);
}else if(cmp<0){
x.left=put(x.left,key,val);
}else{
x.val=val;
}
x.N=size(x.left)+size(x.right)+1;
return x;
}
public Value get(Key key){
return get(root,key);
}
private Value get(Node x,Key key){
if(x==null){
return null;
}
int cmp=key.compareTo(x.key);
if(cmp>0){
return get(x.right,key);
}else if(cmp<0){
return get(x.left,key);
}else{
return x.val;
}
}
public Key min(){
return min(root).key;
}
private Node min(Node x){
if(x.left==null){
return x;
}
return min(x.left);
}
/* //非递归实现
private Key min(Node x){
if(x!=null){
while(x.left!=null){
x=x.left;
}
}
return x;
}*/
//max()同理
public Key floor(Key key){
Node x=floor(root,key);
if(x==null){
return null;
}
return x.key;
}
private Node floor(Node x,Key key){
if(x==null){
return null;
}
int cmp=key.compareTo(x.key);
if(cmp==0){
return x;
}else if(cmp<0){
return floor(x.left,key);
}else{
//注意在右侧查找时可能找不到,这是应返回根节点,而不是在右侧直接返回
Node t=floor(x.right,key);
if(t==null){
return x;
}else{
return t;
}
}
}
//ceiling同理
public Key select(int k){
return select(root,k).key;
}
private Node select(Node x,int k){
if(x==null){
return null;
}
int t=size(x.left);
if(t==k){
return x;
}else if(t>k){
return select(x.left,k);
}else{
//注意右子树查找的数量 k-t-1
return select(x.right,k-t-1);
}
}
public int rank(Key key){
return rank(root,key);
}
private int rank(Node x,Key key){
if(x==null){
return 0;
}
int cmp=key.compareTo(x.key);
if(cmp==0){
return size(x.left);
}else if(cmp<0){
return rank(x.left,key);
}else{
//注意在右侧查找后返回的元素包括根节点和左子树元素
return rank(x.right,key)+size(x.left)+1;
}
}
public void deleteMin(){
root=deleteMin(root);
}
private Node deleteMin(Node x){
if(x.left==null){
return x.right;
}
x.left=deleteMin(x.left);
x.N=size(x.left)+size(x.right)+1;
return x;
}
//deleteMax()同理
//删除操作,删除一个元素时用这个节点右子树的最小值或者左子树的最大值代替
public void delete(Key key){
root=delete(root,key);
}
private Node delete(Node x,Key key){
if(x==null){
return null;
}
int cmp=key.compareTo(x.key);
if(cmp<0){
delete(x.left,key);
}else if(cmp>0){
delete(x.right,key);
}else{
if(x.left==null){
return x.right;
}
if(x.right==null){
return x.left;
}
Node t=x;
x=min(t.right);
x.right=deleteMin(t.right);
x.left=t.left;
}
x.N=size(x.left)+size(x.right)+1;
return x;
}
//范围查找
public Iterable<Key> keys(Key lo,Key hi){
Queue<Key> queue=new Queue<Key>();
keys(root,queue,lo,hi);
return queue;
}
private void keys(Node x,Queue<Key> queue,Key lo,Key hi){
if(x==null){
return;
}
int cmplo=lo.compareTo(x.key);
int cmphi=hi.compareTo(x.key);
if(cmplo<=0 && cmphi>=0){
queue.enqueue(x.key);
}
if(cmphi>0){
keys(x.right,queue,lo,hi);
}
if(cmplo<0){
keys(x.left,queue,lo,hi);
}
}
}

二叉查找树实现的符号表的时间复杂度是lgN,最坏情况下为N