Java数据结构与算法解析(八)——伸展树

伸展树简介

伸展树(Splay Tree)是特殊的二叉查找树。

它的特殊是指，它除了本身是棵二叉查找树之外，它还具备一个特点: 当某个节点被访问时，伸展树会通过旋转使该节点成为树根。这样做的好处是，下次要访问该节点时，能够迅速的访问到该节点。

特性

1. 和普通的二叉查找树相比，具有任何情况下、任何操作的平摊O(log2n)的复杂度，时间性能上更好
2. 和一般的平衡二叉树比如 红黑树、AVL树相比，维护更少的节点额外信息，空间性能更优，同时编程复杂度更低
3. 在很多情况下，对于查找操作，后面的查询和之前的查询有很大的相关性。这样每次查询操作将被查到的节点旋转到树的根节点位置，这样下次查询操作可以很快的完成
4. 可以完成对区间的查询、修改、删除等操作，可以实现线段树和树状数组的所有功能

旋转

伸展树实现O(log2n)量级的平摊复杂度依靠每次对伸展树进行查询、修改、删除操作之后，都进行旋转操作 Splay(x, root)，该操作将节点x旋转到树的根部。

伸展树的旋转有六种类型，如果去掉镜像的重复，则为三种：zig(zag)、zig-zig(zag-zag)、zig-zag(zag-zig)。

1 自底向上的方式进行旋转

1.1 zig旋转

如图所示，x节点的父节点为y，x为y的左子节点，且y节点为根。则只需要对x节点进行一次右旋(zig操作)，使之成为y的父节点，就可以使x成为伸展树的根节点。

1.2 zig-zig旋转

如上图所示，x节点的父节点y，y的父节点z，三者在一字型链上。此时，先对y节点和z节点进行zig旋转，然后再对x节点和y节点进行zig旋转，最后变为右图所示，x成为y和z的祖先节点。

1.3 zig-zag旋转

如上图所示，x节点的父节点y，y的父节点z，三者在之字型链上。此时，先对x节点和y节点进行zig旋转，然后再对x节点和y节点进行zag旋转，最后变为右图所示，x成为y和z的祖先节点。

2 自顶向下的方式进行旋转

这种方式不需要节点存储其父节点的引用。当我们沿着树向下搜索某个节点x时，将搜索路径上的节点及其子树移走。构建两棵临时的树——左树和右树。没有被移走的节点构成的树称为中树。

1. 当前节点x是中树的根
2. 左树L保存小于x的节点
3. 右树R保存大于x的节点

开始时候，x是树T的根，左树L和右树R都为空。三种旋转操作：

2.1 zig旋转

如图所示，x节点的子节点y就是我们要找的节点，则只需要对y节点进行一次右旋(zig操作)，使之成为x的父节点，就可以使y成为伸展树的根节点。将y作为中树的根，同时，x节点移动到右树R中，显然右树上的节点都大于所要查找的节点。

2.2 zig-zig旋转

如上图所示，x节点的左子节点y，y的左子节点z，三者在一字型链上，且要查找的节点位于z节点为根的子树中。此时，对x节点和y节点进行zig，然后对z和y进行zig，使z成为中树的根，同时将y及其子树挂载到右树R上。

2.3 zig-zag旋转

如上图所示，x节点的左子节点y，y的右子节点z，三者在之字型链上，且需要查找的元素位于以z为根的子树上。此时，先对x节点和y节点进行zig旋转，将x及其右子树挂载到右树R上，此时y成为中树的根节点;然后再对z节点和y节点进行zag旋转，使得z成为中树的根节点。

2.4 合并

最后，找到节点或者遇到空节点之后，需要对左、中、右树进行合并。如图所示，将左树挂载到中树的最左下方(满足遍历顺序要求)，将右树挂载到中树的最右下方(满足遍历顺序要求)。

伸展树的实现

1.节点

1. public class SplayTree<T extends Comparable<T>> { 
2.     private SplayTreeNode<T> mRoot;    // 根结点 
3.  
4.     public class SplayTreeNode<T extends Comparable<T>> { 
5.         T key;                // 关键字(键值) 
6.         SplayTreeNode<T> left;    // 左孩子 
7.         SplayTreeNode<T> right;    // 右孩子 
8.  
9.         public SplayTreeNode() { 
10.             this.left = null; 
11.             this.right = null; 
12.         } 
13.  
14.         public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) { 
15.             this.key = key; 
16.             this.left = left; 
17.             this.right = right; 
18.         } 
19.     } 
20. }  

SplayTree是伸展树，而SplayTreeNode是伸展树节点。在此，我将SplayTreeNode定义为SplayTree的内部类。在伸展树SplayTree中包含了伸展树的根节点mRoot。SplayTreeNode包括的几个组成元素:

1. key – 是关键字，是用来对伸展树的节点进行排序的。
2. left – 是左孩子。
3. right – 是右孩子。

2.旋转

1. /* 
2. * 旋转key对应的节点为根节点，并返回根节点。 
3. * 
4. * 注意： 
5. *   (a)：伸展树中存在"键值为key的节点"。 
6. *          将"键值为key的节点"旋转为根节点。 
7. *   (b)：伸展树中不存在"键值为key的节点"，并且key < tree.key。 
8. *      b-1 "键值为key的节点"的前驱节点存在的话，将"键值为key的节点"的前驱节点旋转为根节点。 
9. *      b-2 "键值为key的节点"的前驱节点存在的话，则意味着，key比树中任何键值都小，那么此时，将最小节点旋转为根节点。 
10. *   (c)：伸展树中不存在"键值为key的节点"，并且key > tree.key。 
11. *      c-1 "键值为key的节点"的后继节点存在的话，将"键值为key的节点"的后继节点旋转为根节点。 
12. *      c-2 "键值为key的节点"的后继节点不存在的话，则意味着，key比树中任何键值都大，那么此时，将最大节点旋转为根节点。 
13. */ 
14.    private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) { 
15.        if (tree == null) 
16.            return tree; 
17.  
18.        SplayTreeNode<T> N = new SplayTreeNode<T>(); 
19.        SplayTreeNode<T> l = N; 
20.        SplayTreeNode<T> r = N; 
21.        SplayTreeNode<T> c; 
22.  
23.        for (; ; ) { 
24.            int cmp = key.compareTo(tree.key); 
25.            if (cmp < 0) { 
26.                if (key.compareTo(tree.left.key) < 0) { 
27.                    c = tree.left;                           /* rotate right */ 
28.                    tree.left = c.right; 
29.                    c.right = tree; 
30.                    tree = c; 
31.                    if (tree.left == null) 
32.                        break; 
33.                } 
34.                r.left = tree;                               /* link right */ 
35.                r = tree; 
36.                tree = tree.left; 
37.            } else if (cmp > 0) { 
38.  
39.                if (tree.right == null) 
40.                    break; 
41.  
42.                if (key.compareTo(tree.right.key) > 0) { 
43.                    c = tree.right;                          /* rotate left */ 
44.                    tree.right = c.left; 
45.                    c.left = tree; 
46.                    tree = c; 
47.                    if (tree.right == null) 
48.                        break; 
49.                } 
50.  
51.                l.right = tree;                              /* link left */ 
52.                l = tree; 
53.                tree = tree.right; 
54.            } else { 
55.                break; 
56.            } 
57.        } 
58.        l.right = tree.left;                                /* assemble */ 
59.        r.left = tree.right; 
60.        tree.left = N.right; 
61.        tree.right = N.left; 
62.  
63.        return tree; 
64.    } 
65.  
66.    public void splay(T key) { 
67.        mRoot = splay(mRoot, key); 
68.    }  

上面的代码的作用：将”键值为key的节点”旋转为根节点，并返回根节点。它的处理情况共包括：

(a)：伸展树中存在”键值为key的节点”。

将”键值为key的节点”旋转为根节点。

(b)：伸展树中不存在”键值为key的节点”，并且key < tree->key。

b-1) “键值为key的节点”的前驱节点存在的话，将”键值为key的节点”的前驱节点旋转为根节点。

b-2) “键值为key的节点”的前驱节点存在的话，则意味着，key比树中任何键值都小，那么此时，将最小节点旋转为根节点。

(c)：伸展树中不存在”键值为key的节点”，并且key > tree->key。

c-1) “键值为key的节点”的后继节点存在的话，将”键值为key的节点”的后继节点旋转为根节点。

c-2) “键值为key的节点”的后继节点不存在的话，则意味着，key比树中任何键值都大，那么此时，将最大节点旋转为根节点。

下面列举个例子分别对a进行说明。

在下面的伸展树中查找10，，共包括”右旋” –> “右链接” –> “组合”这3步。

01, 右旋

对应代码中的”rotate right”部分

02, 右链接

对应代码中的”link right”部分

03.组合

对应代码中的”assemble”部分

提示：如果在上面的伸展树中查找”70”，则正好与”示例1”对称，而对应的操作则分别是”rotate left”, “link left”和”assemble”。

其它的情况，例如”查找15是b-1的情况，查找5是b-2的情况”等等，这些都比较简单，大家可以自己分析。

3.插入

1. /** 
2.      * 将结点插入到伸展树中，并返回根节点 
3.      * @param tree 伸展树的根节点 
4.      * @param z 插入的结点 
5.      * @return 
6.      */ 
7.     private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) { 
8.         int cmp; 
9.         SplayTreeNode<T> y = null; 
10.         SplayTreeNode<T> x = tree; 
11.  
12.         // 查找z的插入位置 
13.         while (x != null) { 
14.             y = x; 
15.             cmp = z.key.compareTo(x.key); 
16.             if (cmp < 0) 
17.                 x = x.left; 
18.             else if (cmp > 0) 
19.                 x = x.right; 
20.             else { 
21.                 System.out.printf("不允许插入相同节点(%d)!\n", z.key); 
22.                 z = null; 
23.                 return tree; 
24.             } 
25.         } 
26.  
27.         if (y == null) 
28.             tree = z; 
29.         else { 
30.             cmp = z.key.compareTo(y.key); 
31.             if (cmp < 0) 
32.                 y.left = z; 
33.             else 
34.                 y.right = z; 
35.         } 
36.  
37.         return tree; 
38.     } 
39.  
40.     public void insert(T key) { 
41.         SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null); 
42.  
43.         // 如果新建结点失败，则返回。 
44.         if ((z = new SplayTreeNode<T>(key, null, null)) == null) 
45.             return; 
46.  
47.         // 插入节点 
48.         mRoot = insert(mRoot, z); 
49.         // 将节点(key)旋转为根节点 
50.         mRoot = splay(mRoot, key); 
51.     }  

insert(key)是提供给外部的接口，它的作用是新建节点(节点的键值为key)，并将节点插入到伸展树中;然后，将该节点旋转为根节点。

insert(tree, z)是内部接口，它的作用是将节点z插入到tree中。insert(tree, z)在将z插入到tree中时，仅仅只将tree当作是一棵二叉查找树，而且不允许插入相同节点。

4.删除

1. /** 
2.      *  
3.      * @param tree 伸展树 
4.      * @param key 删除的结点 
5.      * @return 
6.      */ 
7.     private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) { 
8.         SplayTreeNode<T> x; 
9.  
10.         if (tree == null) 
11.             return null; 
12.  
13.         // 查找键值为key的节点，找不到的话直接返回。 
14.         if (search(tree, key) == null) 
15.             return tree; 
16.  
17.         // 将key对应的节点旋转为根节点。 
18.         tree = splay(tree, key); 
19.  
20.         if (tree.left != null) { 
21.             // 将"tree的前驱节点"旋转为根节点 
22.             x = splay(tree.left, key); 
23.             // 移除tree节点 
24.             x.right = tree.right; 
25.         } 
26.         else 
27.             x = tree.right; 
28.  
29.         tree = null; 
30.  
31.         return x; 
32.     } 
33.  
34.     public void remove(T key) { 
35.         mRoot = remove(mRoot, key); 
36.     }  

remove(key)是外部接口，remove(tree, key)是内部接口。

remove(tree, key)的作用是：删除伸展树中键值为key的节点。

它会先在伸展树中查找键值为key的节点。若没有找到的话，则直接返回。若找到的话，则将该节点旋转为根节点，然后再删除该节点。

伸展树实现完整代码

1. public class SplayTree<T extends Comparable<T>> {     
2. private SplayTreeNode<T> mRoot;    // 根结点 
3.  
4.     public class SplayTreeNode<T extends Comparable<T>> { 
5.         T key;                // 关键字(键值) 
6.         SplayTreeNode<T> left;    // 左孩子 
7.         SplayTreeNode<T> right;    // 右孩子 
8.  
9.         public SplayTreeNode() { 
10.             this.left = null; 
11.             this.right = null; 
12.         } 
13.  
14.         public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) { 
15.             this.key = key; 
16.             this.left = left; 
17.             this.right = right; 
18.         } 
19.     } 
20.  
21.     /* 
22.  * 旋转key对应的节点为根节点，并返回根节点。 
23.  * 
24.  * 注意： 
25.  *   (a)：伸展树中存在"键值为key的节点"。 
26.  *          将"键值为key的节点"旋转为根节点。 
27.  *   (b)：伸展树中不存在"键值为key的节点"，并且key < tree.key。 
28.  *      b-1 "键值为key的节点"的前驱节点存在的话，将"键值为key的节点"的前驱节点旋转为根节点。 
29.  *      b-2 "键值为key的节点"的前驱节点存在的话，则意味着，key比树中任何键值都小，那么此时，将最小节点旋转为根节点。 
30.  *   (c)：伸展树中不存在"键值为key的节点"，并且key > tree.key。 
31.  *      c-1 "键值为key的节点"的后继节点存在的话，将"键值为key的节点"的后继节点旋转为根节点。 
32.  *      c-2 "键值为key的节点"的后继节点不存在的话，则意味着，key比树中任何键值都大，那么此时，将最大节点旋转为根节点。 
33.  */ 
34.     private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) { 
35.         if (tree == null) 
36.             return tree; 
37.  
38.         SplayTreeNode<T> N = new SplayTreeNode<T>(); 
39.         SplayTreeNode<T> l = N; 
40.         SplayTreeNode<T> r = N; 
41.         SplayTreeNode<T> c; 
42.  
43.         for (; ; ) { 
44.             int cmp = key.compareTo(tree.key); 
45.             if (cmp < 0) { 
46.                 if (key.compareTo(tree.left.key) < 0) { 
47.                     c = tree.left;                           /* rotate right */ 
48.                     tree.left = c.right; 
49.                     c.right = tree; 
50.                     tree = c; 
51.                     if (tree.left == null) 
52.                         break; 
53.                 } 
54.                 r.left = tree;                               /* link right */ 
55.                 r = tree; 
56.                 tree = tree.left; 
57.             } else if (cmp > 0) { 
58.  
59.                 if (tree.right == null) 
60.                     break; 
61.  
62.                 if (key.compareTo(tree.right.key) > 0) { 
63.                     c = tree.right;                          /* rotate left */ 
64.                     tree.right = c.left; 
65.                     c.left = tree; 
66.                     tree = c; 
67.                     if (tree.right == null) 
68.                         break; 
69.                 } 
70.  
71.                 l.right = tree;                              /* link left */ 
72.                 l = tree; 
73.                 tree = tree.right; 
74.             } else { 
75.                 break; 
76.             } 
77.         } 
78.         l.right = tree.left;                                /* assemble */ 
79.         r.left = tree.right; 
80.         tree.left = N.right; 
81.         tree.right = N.left; 
82.  
83.         return tree; 
84.     } 
85.  
86.     public void splay(T key) { 
87.         mRoot = splay(mRoot, key); 
88.     } 
89.  
90.  
91.  
92.     /** 
93.      * 将结点插入到伸展树中，并返回根节点 
94.      * @param tree 伸展树的根节点 
95.      * @param z 插入的结点 
96.      * @return 
97.      */ 
98.     private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) { 
99.         int cmp; 
100.         SplayTreeNode<T> y = null; 
101.         SplayTreeNode<T> x = tree; 
102.  
103.         // 查找z的插入位置 
104.         while (x != null) { 
105.             y = x; 
106.             cmp = z.key.compareTo(x.key); 
107.             if (cmp < 0) 
108.                 x = x.left; 
109.             else if (cmp > 0) 
110.                 x = x.right; 
111.             else { 
112.                 System.out.printf("不允许插入相同节点(%d)!\n", z.key); 
113.                 z = null; 
114.                 return tree; 
115.             } 
116.         } 
117.  
118.         if (y == null) 
119.             tree = z; 
120.         else { 
121.             cmp = z.key.compareTo(y.key); 
122.             if (cmp < 0) 
123.                 y.left = z; 
124.             else 
125.                 y.right = z; 
126.         } 
127.  
128.         return tree; 
129.     } 
130.  
131.     public void insert(T key) { 
132.         SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null); 
133.  
134.         // 如果新建结点失败，则返回。 
135.         if ((z = new SplayTreeNode<T>(key, null, null)) == null) 
136.             return; 
137.  
138.         // 插入节点 
139.         mRoot = insert(mRoot, z); 
140.         // 将节点(key)旋转为根节点 
141.         mRoot = splay(mRoot, key); 
142.     } 
143.  
144.     /* 
145.  * 删除结点(z)，并返回被删除的结点 
146.  * 
147.  * 参数说明： 
148.  *     bst 伸展树 
149.  *     z 删除的结点 
150.  */ 
151.  
152.     /** 
153.      * 
154.      * @param tree 伸展树 
155.      * @param key 删除的结点 
156.      * @return 
157.      */ 
158.     private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) { 
159.         SplayTreeNode<T> x; 
160.  
161.         if (tree == null) 
162.             return null; 
163.  
164.         // 查找键值为key的节点，找不到的话直接返回。 
165.         if (search(tree, key) == null) 
166.             return tree; 
167.  
168.         // 将key对应的节点旋转为根节点。 
169.         tree = splay(tree, key); 
170.  
171.         if (tree.left != null) { 
172.             // 将"tree的前驱节点"旋转为根节点 
173.             x = splay(tree.left, key); 
174.             // 移除tree节点 
175.             x.right = tree.right; 
176.         } 
177.         else 
178.             x = tree.right; 
179.  
180.         tree = null; 
181.  
182.         return x; 
183.     } 
184.  
185.     public void remove(T key) { 
186.         mRoot = remove(mRoot, key); 
187.     } 
188.  
189.     /* 
190.     * (递归实现)查找"伸展树x"中键值为key的节点 
191.     */ 
192.     private SplayTreeNode<T> search(SplayTreeNode<T> x, T key) { 
193.         if (x==null) 
194.             return x; 
195.  
196.         int cmp = key.compareTo(x.key); 
197.         if (cmp < 0) 
198.             return search(x.left, key); 
199.         else if (cmp > 0) 
200.             return search(x.right, key); 
201.         else 
202.             return x; 
203.     } 
204.  
205.     public SplayTreeNode<T> search(T key) { 
206.         return search(mRoot, key); 
207.     } 
208.  
209.     /* 
210.    * 查找最小结点：返回tree为根结点的伸展树的最小结点。 
211.    */ 
212.     private SplayTreeNode<T> minimum(SplayTreeNode<T> tree) { 
213.         if (tree == null) 
214.             return null; 
215.  
216.         while(tree.left != null) 
217.             tree = tree.left; 
218.         return tree; 
219.     } 
220.  
221.     public T minimum() { 
222.         SplayTreeNode<T> p = minimum(mRoot); 
223.         if (p != null) 
224.             return p.key; 
225.  
226.         return null; 
227.     } 
228.  
229.     /* 
230.      * 查找最大结点：返回tree为根结点的伸展树的最大结点。 
231.      */ 
232.     private SplayTreeNode<T> maximum(SplayTreeNode<T> tree) { 
233.         if (tree == null) 
234.             return null; 
235.  
236.         while(tree.right != null) 
237.             tree = tree.right; 
238.         return tree; 
239.     } 
240.  
241.     public T maximum() { 
242.         SplayTreeNode<T> p = maximum(mRoot); 
243.         if (p != null) 
244.             return p.key; 
245.  
246.         return null; 
247.     }  

本文作者：佚名

来源：51CTO