数据结构-伸展树

时间：2014-08-08 01:32:25 阅读：473 评论：0 收藏：0 [点我收藏+]

声明：本文是对某高中生的竞赛论文学习的文章

介绍：

　　二叉查找树能够支持多种动态集合操作。对于一个含有n个结点的完全二叉树，这些操作的最还情况运行时间是O(lgn)，但如果树是含有n个结点的线性链，则这些操作的最坏情况运行时间为O(n)。而像红黑树、AVL树这种二叉查找树的变形在最坏情况下，仍能保持较好性能。

　　本文将要介绍的伸展树也是二叉查找树的变形，它对空间要求及编程难度的要求相对不高。

伸展树:

　　伸展树与二叉查找树一样，具有有序性。即伸展树的每一个结点x满足：该结点的左子树中的每个元素都小于x,而其右子树的每一个元素都大于x。与二叉查找树不同的是，伸展树可以自我调整，也就是伸展操作(Splay)。

　　伸展操作Splay(x,S)

　　　　伸展操作是在保持伸展树有序的前提下，通过一系列旋转将伸展树T中的元素x调整至树的根部。在调整的过程中，分以下三种情况处理：

　　　　　　1、结点x的父节点y是根节点。

　　　　　　　　这时，如果x是y的左孩子，我们进行一次Zig(右旋)操作；

　　　　　　　　　　　如果x是y的右孩子，我们进行一次Zag(左旋)操作；

　　　　　　　　　　 bubuko.com,布布扣

　　　　　　2、结点x的父节点y不是根节点，y的父节点为z。

　　　　　　　　且x与y同时是各自父节点的左孩子，这时我们进行Zig-Zig操作；

　　　　　　　　或者是同时是各自父节点的右孩子，这时我们进行一次Zag-Zag操作。

　　　　　　　　　　 bubuko.com,布布扣

　　　　　　3、结点x的父节点y不是根节点，y的父节点为z。

　　　　　　　　且x与y分别是其父节点的左孩子和右孩子，这时我们进行一次Zig-Zag操作。

　　　　　　　或者是x与y分别是其父节点的右孩子和左孩子，这时我们进行一次Zag-Zig操作。

　　　　　　　　　　 bubuko.com,布布扣

　　　　如下图所示，执行Splay(1,T)，将元素1调整的树根的位置，执行Splay(2)将元素2调整到树根的位置。从直观上看，树比原来“平衡”多了，而伸展操作的过　　　　程并不复杂，只需要左旋和右旋。

　　　　　　　　　　 bubuko.com,布布扣

　　基本操作：

　　　　　　利用Splay可以在伸展树上T上作如下操作，　　

　　　　　　查找：判断元素x是否在伸展树T表示的有序集中；

　　　　　　　　　跟二叉查找树的查找操作一样，在伸展树中查找x，如果x在伸展树中，则再执行Splay(x,T)调整伸展树。

　　　　　　插入：将元素x插入到伸展树T表示的有序集中；

　　　　　　　　　跟二叉查找树的插入操作一样，将元素x插入到伸展树的相应位置，在执行Splay(x,T)调整伸展树。

　　　　　　删除：将元素x从伸展树T表示的有序集中删除；

　　　　　　　　首先，查找的元素x所在的位置，如果x没有孩子或者只有一个孩子，直接删除掉x，再对x的父节点执行Splay，将x的父节点调整到根位置。否　　　　　　　　　　则，查找x的后继y，用y代替x的位置，然后执行Splay(y,T)，将y调整到根节点位子。

　　　　　　合并：将两个伸展树T1、T2合并成一个伸展树。其中S1中的所有元素都小于T2中的元素。

　　　　　　　　　　首先，找到T1中最大的元素x，在执行Splay(x,T1)将x调整到T1的根位置，然后将T2作为x的右子树就得到新的伸展树T。

　　　　　　　　　　　　 bubuko.com,布布扣

　　　　　　划分：以元素x为边界，将伸展树T划分成两个伸展树T1和T2，其中，T1中的元素都小于x，T2中的元素都大于x。

　　　　　　　　　首先，执行查找操作，将元素x调整为根位置，x的左子树为T1，右子树为T2。

　　　　　　　　　　 bubuko.com,布布扣

　　　　　除了上述操作外，伸展树还可以有其他的操作。

时间复杂度：

　　　　　　所有的操作其平摊复杂度为O(lgn)。

程序实现：

  1 package datastructure;  4 import java.util.List;
  5 import java.util.ArrayList;
  6 
 10 public class SplayTree {
 11     class TreeNode{
 12         private int key;
 13         private String data;
 14         private TreeNode left;
 15         private TreeNode right;
 16         private TreeNode parent;
 17         
 18         public TreeNode(int key,String data,TreeNode left,TreeNode right,TreeNode parent) {
 19             this.key = key;
 20             this.data = data;
 21             this.left = left;
 22             this.right = right;
 23             this.parent = parent;
 24         }
 25         public int getKey() {
 26             return key;            
 27         }
 28         public String toString(){
 29             String leftKey = (left == null ? " " : String.valueOf(left.key));
 30             String rightKey = (right == null ? " " : String.valueOf(right.key));
 31             return "(" + leftKey +"," +  key + "," + rightKey + ")";
 32         }
 33     }
 34     private TreeNode root = null;
 35     public boolean IsEmpty() 
 36     {
 37          if(root == null)
 38             {
 39                 return true;
 40             }
 41             else
 42             {
 43                 return false;
 44             }
 45     }
 46     public TreeNode Insert(int key) {
 47         TreeNode parentNode = null;
 48         TreeNode newNode = new TreeNode(key, "v", null, null, null);
 49         TreeNode pNode = root;
 50         if(pNode == null)
 51         {
 52             root = newNode;
 53             return root ;
 54         }
 55         while(pNode != null)
 56         {
 57             parentNode = pNode;
 58             if(key < pNode.key)
 59             {
 60                 pNode = pNode.left;
 61             }
 62             else if(key > pNode.key)
 63             {
 64                 pNode = pNode.right;                  
 65             }
 66             else
 67             {
 68                 return pNode;//树中已存在与新结点的关键字相同的结点
 69             }
 70         }
 71         newNode.parent = parentNode;
 72         if(newNode.key < parentNode.key)
 73         {
 74             parentNode.left = newNode; 
 75             return parentNode.left;
 76         }
 77         else
 78         {
 79               parentNode.right = newNode;
 80               return parentNode.right;
 81         } 
 82        
 83         
 84     }
 85     private List<TreeNode> nodeList = new ArrayList<TreeNode>();
 86     
 87     public List<TreeNode> getNodeList() {
 88         return nodeList;
 89     }
 90     
 91     //获取中序列表
 92     public List<TreeNode> Inorder_SplayTree_WalkList()
 93     {
 94         if(nodeList != null)
 95         {
 96             nodeList.clear();
 97         }
 98         Inorder_SplayTree_Walk(root);
 99         return nodeList;
100     }
101     //中序遍历树
102     private void Inorder_SplayTree_Walk(TreeNode root)
103     {
104         if(root != null)
105         {
106             Inorder_SplayTree_Walk(root.left);
107             nodeList.add(root);
108             Inorder_SplayTree_Walk(root.right);
109         }
110     }
111     //给定关键字key,查找到该结点
112     private TreeNode Search(int key)
113     {
114         TreeNode pNode = root;
115         while(pNode != null && pNode.key != key)
116         {
117             if(key<pNode.key)
118             {
119                 pNode = pNode.left;
120             }
121             else {
122                 pNode = pNode.right;
123             }
124         }
125         return pNode;
126     }
127     //左旋转:x的右孩子y不空,以x与y之间的链为之架
128     private void leftRotate(TreeNode pNode)
129     {
130         TreeNode xNode = pNode;
131         TreeNode yNode = xNode.right;
132         xNode.right = yNode.left;
133         if(yNode.left != null)
134         {
135             yNode.left.parent = xNode;
136         }
137         yNode.parent = xNode.parent;
138         if(xNode.parent == null)
139         {
140             root = yNode;
141         }
142         else if(xNode.parent.left == xNode)
143         {
144             xNode.parent.left = yNode;
145         }else {
146             xNode.parent.right = yNode;
147         }
148         yNode.left = xNode;
149         xNode.parent = yNode;
150     }
151     //右旋转：x的左孩子y不空，以x与y之间的链为支架右旋转
152     private void rightRotate(TreeNode pNode)
153     {
154         TreeNode xNode = pNode;
155         TreeNode yNode = xNode.left;
156         xNode.left = yNode.right;
157         if(yNode.right != null)
158         {
159             yNode.right.parent = xNode;
160         }
161         yNode.parent = xNode.parent;
162         if(xNode.parent == null)
163         {
164             root = yNode;
165         }else if(xNode.parent.left == xNode)
166         {
167             xNode.parent.left = yNode;
168         }
169         else {
170             xNode.parent.right = yNode;
171         }
172         yNode.right = xNode;
173         xNode.parent = yNode;    
174     }
175     
176     public void Splay(int key)
177     {
178         TreeNode xNode = Search(key);
179         if(xNode == null)
180         {
181             return;
182         }
183         SplayT(xNode,this.root);
184     }
185     
186     //伸展树的Splay操作展操作是在保持伸展树有序的前提下，
187     //通过一系列旋转将伸展树T中的元素x调整至树的根部。
188     //在调整的过程中，分以下三种情况处理：
189     private void SplayT(TreeNode xNode,TreeNode Troot)
190     {
191         
192         if(Troot == null || xNode == Troot)
193         {
194             return ;
195         }
196         while(xNode.parent != null) //x是否到达根位置
197         {
198             //　1、结点x的父节点y是根节点。
199             if(xNode.parent == Troot)
200             {
201                 if (xNode.parent.left == xNode)
202                 {
203                     //如果x是y的左孩子，我们进行一次Zig(右旋)操作；
204                     rightRotate(xNode.parent);
205                 }
206                 else 
207                 {
208                     //如果x是y的右孩子，我们进行一次Zag(左旋)操作；
209                     leftRotate(xNode.parent);
210                 }
211             }
212             else
213             {
214                 //2、结点x的父节点y不是根节点，y的父节点为z。
215                 TreeNode yNode = xNode.parent;
216                 if(yNode != null)
217                 {
218                     TreeNode zNode = yNode.parent;
219                     if(xNode == yNode.left && yNode ==zNode.left)
220                     {
221                         //x与y同时是其父节点的左孩子
222                         rightRotate(zNode);
223                         rightRotate(yNode);
224                     }
225                     else if(xNode == yNode.right && yNode == zNode.right)
226                     {
227                         //x与y同时是其父节点的右孩子
228                         leftRotate(zNode);
229                         leftRotate(yNode);    
230                     }else if (xNode==yNode.left && yNode == zNode.right) 
231                     {
232                         //x是其父节点的左孩子，y是父节点的右孩子
233                         rightRotate(xNode.parent);
234                         leftRotate(xNode.parent);    
235                         
236                     }else
237                     {
238                         //x是其父节点的右孩子，y是父节点的左孩子
239                         leftRotate(xNode.parent);
240                         rightRotate(xNode.parent);
241                     }
242                 }
243             }
244                 
245         }        
246     }
247     //伸展树的查找操作    
248     public void SplayTree_Search(int x,TreeNode Troot)
249     {
250         TreeNode xNode = Search(x);
251         if(xNode == null)
252         {
253             return;    
254         }
255         SplayT(xNode, Troot);
256     }
257     //伸展树的插入操作
258     public void SplayTree_Insert(int x,TreeNode Troot)
259     {
260         TreeNode xNode = Insert(x);
261         if(xNode == null)
262         {
263             return;    
264         }
265         SplayT(xNode, Troot);
266     }
267     //伸展树的删除操作
268     public void SplayTree_Delete(int x,TreeNode Troot) throws Exception
269     {
270         TreeNode xNode = Search(x);
271         if(xNode == null)
272         {
273             throw new Exception("树中不存在要删除的元素x");
274         }
275         SplayTree_Remove(xNode,Troot);    
276     }
277     private void SplayTree_Remove(TreeNode xNode,TreeNode Troot) throws Exception
278     {
279         
280         if(xNode == null)
281         {
282             return;
283         }
284         TreeNode parentNode = xNode.parent;
285         if(xNode.left == null && xNode.right == null)
286         {
287             if(parentNode.left == xNode)
288             {
289                 parentNode.left = null;
290                 SplayT(parentNode, Troot);
291             }
292             if(parentNode.right == xNode)
293             {
294                 parentNode.right = null;
295                 SplayT(parentNode,Troot);
296             }
297         }
298         if(xNode.left != null && xNode.right == null)
299         {
300             if(parentNode.left == xNode)
301             {
302                 xNode.left.parent = parentNode;
303                 parentNode.left = xNode.left;
304                 SplayT(parentNode, Troot);
305             }
306             if(parentNode.right == xNode)
307             {
308                 xNode.left.parent = parentNode;
309                 parentNode.right = xNode.left;
310                 SplayT(parentNode,Troot);
311             }    
312         }
313         if(xNode.left == null && xNode.right != null)
314         {
315             if(parentNode.left == xNode)
316             {
317                 xNode.right.parent = parentNode;
318                 parentNode.left = xNode.right;
319                 SplayT(parentNode, Troot);
320             }
321             if(parentNode.right == xNode)
322             {
323                 xNode.right.parent = parentNode;
324                 parentNode.right = xNode.right;
325                 SplayT(parentNode, Troot);
326             }
327         }
328         //x的左右儿子都不为空，就删除后继，让后继的内容，代替当前内容                          
329         TreeNode successorNode = SplayTree_Successor(xNode);
330         xNode.key = successorNode.key;
331         xNode.data = successorNode.data;
332         SplayTree_Remove(successorNode,Troot);
333         SplayT(successorNode, Troot);
334     }
335     public TreeNode SplayTree_Successor(TreeNode xNode) throws Exception
336     {
337               if(xNode == null)
338               {
339                   return null;
340               }
341               TreeNode pNode = xNode;
342               //若右子树不空，则为右子树中最小的关键字
343               if(pNode.right != null)
344               {
345                   return Tree_Minimum(pNode.right);
346               }
347               TreeNode parentNode = xNode.parent;
348               //若右子树为空，且x有一个后继y.则y是x的最低祖先结点，且y的左儿子也是x的祖先
349               while(parentNode != null && pNode == parentNode.right)
350               {
351                   pNode = parentNode;
352                   parentNode = pNode.parent;
353                }
354               return parentNode;     
355     }
356     public TreeNode Tree_Maxmum(TreeNode Troot) throws Exception
357     {
358         if(Troot == null)
359         {
360             throw new Exception("树为空");
361         }
362         TreeNode xNode = Troot;
363         while(xNode.right != null)
364         {
365             xNode = xNode.right;
366         }
367         return xNode;
368     }
369     public TreeNode Tree_Minimum(TreeNode Troot) throws Exception
370     {
371         if(Troot == null)
372         {
373             throw new Exception("树为空");
374         }
375         TreeNode xNode = Troot;
376         while(xNode.left != null)
377         {
378             xNode = xNode.left;
379         }
380         return xNode;    
381     }
382     public void SplayTree_Minimum(TreeNode Troot) throws Exception
383     {
384         TreeNode xNode = Tree_Minimum(Troot);
385         if(xNode == null)
386         {
387             return;
388         }
389         SplayT(xNode,Troot);
390     }
391     public TreeNode SplayTree_Join(TreeNode Troot1,TreeNode Troot2) throws Exception
392     {
393         TreeNode xNode = Tree_Maxmum(Troot1);
394         if(xNode == null)
395         {
396             return null;
397         }
398         SplayT(xNode, Troot1);
399         xNode.right = Troot2;
400         Troot2.parent = xNode;
401         return xNode;
402         
403     }
404     
405 }

数据结构-伸展树,布布扣,bubuko.com

数据结构-伸展树

原文：http://www.cnblogs.com/Jiaoxia/p/3895211.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)