伸展树(三)之 Java的实现(四)
*
166 * 注意：
167 * (a)：伸展树中存在"键值为key的节点"。
168 * 将"键值为key的节点"旋转为根节点。
169 * (b)：伸展树中不存在"键值为key的节点"，并且key < tree.key。
170 * b-1 "键值为key的节点"的前驱节点存在的话，将"键值为key的节点"的前驱节点旋转为根节点。
171 * b-2 "键值为key的节点"的前驱节点存在的话，则意味着，key比树中任何键值都小，那么此时，将最小节点旋转为根节点。
172 * (c)：伸展树中不存在"键值为key的节点"，并且key > tree.key。
173 * c-1 "键值为key的节点"的后继节点存在的话，将"键值为key的节点"的后继节点旋转为根节点。
174 * c-2 "键值为key的节点"的后继节点不存在的话，则意味着，key比树中任何键值都大，那么此时，将最大节点旋转为根节点。
175 */
176 private SplayTreeNode splay(SplayTreeNode tree, T key) {
177 if (tree == null)
178 return tree;
179
180 SplayTreeNode N = new SplayTreeNode();
181 SplayTreeNode l = N;
182 SplayTreeNode r = N;
183 SplayTreeNode c;
184
185 for (;;) {
186
187 int cmp = key.compareTo(tree.key);
188 if (cmp < 0) {
189
190 if (tree.left == null)
191 break;
192
193 if (key.compareTo(tree.left.key) < 0) {
194 c = tree.left; /* rotate right */
195 tree.left = c.right;
196 c.right = tree;
197 tree = c;
198 if (tree.left == null)
199 break;
200 }
201 r.left = tree; /* link right */
202 r = tree;
203 tree = tree.left;
204 } else if (cmp > 0) {
205
206 if (tree.right == null)
207 break;
208
209 if (key.compareTo(tree.right.key) > 0) {
210 c = tree.right; /* rotate left */
211 tree.right = c.left;
212 c.left = tree;
213 tree = c;
214 if (tree.right == null)
215 break;
216 }
217
218 l.right = tree; /* link left */
219 l = tree;
220 tree = tree.right;
221 } else {
222 break;
223 }
224 }
225
226 l.right = tree.left; /* assemble */
227 r.left = tree.right;
228 tree.left = N.right;
229 tree.right = N.left;
230
231 return tree;
232 }
233
234 public void splay(T key) {
235 mRoot = splay(mRoot, key);
236 }
237
238 /*
239 * 将结点插入到伸展树中，并返回根节点
240 *
241 * 参数说明：
242 * tree 伸展树的
243 * z 插入的结点
244 */
245 private SplayTreeNode insert(SplayTreeNode tree, SplayTreeNode z) {
246 int cmp;
247 SplayTreeNode y = null;
248 SplayTreeNode x = tree;
249
250 // 查找z的插入位置
251 while (x != null) {
252 y = x;
253 cmp = z.key.compareTo(x.key);
254 if (cmp < 0)
255 x = x.left;
256 else if (cmp > 0)
257 x = x.right;
258 else {
259 System.out.printf("不允许插入相同节点(%d)!\n", z.key);
260 z=null;
261 return tree;
262 }
263 }
264
265 if (y==null)
266 tree = z;
267 else {
268 cmp = z.key.compareTo(y.key);
269 if (cmp < 0)
270 y.left = z;
271 else
272 y.right = z;
273 }
274
275 return tree;
276 }
277
278 public void insert(T key) {
279 SplayTreeNode z=new SplayTreeNode(key,null,null);
280
281 // 如果新建结点失败，则返回。
282 if ((z=new SplayTre