首页 > 代码库 > 数据结构-伸展树
数据结构-伸展树
声明：本文是对某高中生的竞赛论文学习的文章
介绍：
二叉查找树能够支持多种动态集合操作。对于一个含有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(左旋)操作；
2、结点x的父节点y不是根节点，y的父节点为z。
且x与y同时是各自父节点的左孩子，这时我们进行Zig-Zig操作；
或者是同时是各自父节点的右孩子，这时我们进行一次Zag-Zag操作。
3、结点x的父节点y不是根节点，y的父节点为z。
且x与y分别是其父节点的左孩子和右孩子，这时我们进行一次Zig-Zag操作。
或者是x与y分别是其父节点的右孩子和左孩子，这时我们进行一次Zag-Zig操作。
如下图所示，执行Splay(1,T)，将元素1调整的树根的位置，执行Splay(2)将元素2调整到树根的位置。从直观上看，树比原来“平衡”多了，而伸展操作的过 程并不复杂，只需要左旋和右旋。
基本操作：
利用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。
划分：以元素x为边界，将伸展树T划分成两个伸展树T1和T2，其中，T1中的元素都小于x，T2中的元素都大于x。
首先，执行查找操作，将元素x调整为根位置，x的左子树为T1，右子树为T2。
除了上述操作外，伸展树还可以有其他的操作。
时间复杂度：
所有的操作其平摊复杂度为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 =http://www.mamicode.com/ 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 else213 {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 }else237 {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 Exception269 {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 Exception278 {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 =http://www.mamicode.com/ successorNode.data;332 SplayTree_Remove(successorNode,Troot);333 SplayT(successorNode, Troot);334 }335 public TreeNode SplayTree_Successor(TreeNode xNode) throws Exception336 {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 Exception357 {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 Exception370 {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 Exception383 {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 Exception392 {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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。