思想：
二叉树是数据结构中非常经典的一种形式，在二叉树中，每个结点只能有一个父结点（根结点除外），而且每个结点都只有两个结点，分别指向自己的左子节点和右子节点。而二叉查找树（BST）则是每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。
代码：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
191public class BST<Key extends Comparable<Key>,Value> {
private Node root;
private class Node{
private Key key;
private Value val;
private Node left,right;
private int N;
public Node(Key key,Value val,int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
public int size(){
return size(root);
}
private int size(Node x){
if(x==null)
return 0;
else
return x.N;
}
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.left,key);
else if(cmp>0)
return get(x.right,key);
else
return x.val;
}
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.left = put(x.left,key,val);
else if(cmp>0)
x.right = put(x.right,key,val);
else
x.val = val;
x.N = size(x.left)+size(x.right)+1;
return x;
}
public Key min(){
return min(root).key;
}
private Node min(Node x){
if(x.left==null)
return x;
return min(x.left);
}
public Key max(){
return max(root).key;
}
private Node max(Node x){
if(x.right==null)
return x;
return max(x.right);
}
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;
if(cmp<0)
return floor(x.left,key);
Node t = floor(x.right,key);
if(t!=null)
return t;
else
return x;
}
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 select(x.left,k);
else if(t<k)
return select(x.right,k-t-1);
else
return x;
}
public int rank(Key key){
return rank(key,root);
}
private int rank(Key key,Node x){
if(x==null)
return 0;
int cmp = key.compareTo(x.key);
if(cmp<0)
return rank(key,x.left);
else if(cmp>0)
return 1+size(x.left)+rank(key,x.right);
else
return size(x.left);
}
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;
}
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)
x.left = delete(x.left,key);
else if(cmp>0)
x.right = delete(x.right,key);
else{
if(x.right==null)
return x.left;
if(x.left==null)
return x.right;
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(){
return keys(min(),max());
}
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)
keys(x.left,queue,lo,hi);
if(cmplo<=0&&cmphi>=0)
queue.enqueue(x.key);
if(cmphi>0)
keys(x.right,queue,lo,hi);
}
}
分析：
在BST这个数据模型中主要对以下的方法进行讲解。
deleteMin
这个方法就是不断深入左子树，直到遇见一个空链接，然后将指向该结点的链接指向该结点的右子树。
delete
针对二叉查找树中删除拥有两个子结点的结点的问题，我们假设需要删除的元素为x，则可以采用以下策略。由于x有一个右子节点，因此它的后继结点就是其右子树中的最小结点。
1、 将指向即将被删除的结点的链接保存为t
2、 将x指向它的后继结点min(t.right)
3、 将x的右链接(原本指向一颗所有结点都大于x.key的二叉查找树)指向deleteMin(t.right)，也就是在删除后所有结点仍然都大于x.key的子二叉查找树
4、 将x的左链接(本为空)设为t.left(其下所有的键都小于被删除的结点和它的后继结点)