Splay tree的splay操作

2019-11-06 06:43:15

字体：大中小

来源：转载

供稿：网友

splay tree 主要适用于对统一对象的连续读取 splay(insertNode) 操作就是将当前节点移动到 root节点

public class SplayTree<T> { PRivate Node<T> root = null; /** * @param insertNode */ public void splayTree(Node<T> insertNode){ if(insertNode.parent!=null){ if(insertNode.parent.parent==null){/* parent * / * insert * */ if(insertNode.parent.index>insertNode.index){ rotateRight(insertNode); }/* parent * / * insert * */ else{ rotateLeft(insertNode); } }else{ if(insertNode.parent.index>insertNode.index){ if(insertNode.parent.parent.index>insertNode.parent.index){/* grandfather parent insert * / / / / * parent insert grandfather parent * / / * insert grandfather * */ rotateRight(insertNode.parent); rotateRight(insertNode); }/* * grandfather grandfather insert * / / / / * parent insert grandfather parent * / / * insert parent * */ else{ rotateRight(insertNode); rotateLeft(insertNode); } if(insertNode.parent!=null){ splayTree(insertNode); } }else{/* * grandfather grandfather insert * / / / / * parent insert parent grandfather * / / * insert parent * */ if(insertNode.parent.parent.index>insertNode.parent.index){ rotateLeft(insertNode); rotateRight(insertNode); }/* * grandfather parent insert * / / / / * parent grandfather insert parent * /insert / * grandfather * **/ else{ rotateLeft(insertNode.parent); rotateLeft(insertNode); } if(insertNode.parent!=null){ splayTree(insertNode); } } } } root=insertNode; } /** * @param itemNode */ public void rotateRight(Node<T> itemNode){ Node<T> parent=itemNode.parent; Node<T> grandParent=parent.parent; Node<T> right=itemNode.right; parent.parent=itemNode; itemNode.right=parent; parent.left=right; if(right!=null){ right.parent=parent; } itemNode.parent=grandParent; if(grandParent!=null){ if(grandParent.index>itemNode.index){ grandParent.left=itemNode; }else{ grandParent.right=itemNode; } } } public void rotateLeft(Node<T> itemNode){ Node<T> parent=itemNode.parent; Node<T> grandParent=parent.parent; Node<T> left=itemNode.left; parent.parent=itemNode; itemNode.left=parent; parent.right=left; if(left!=null){ left.parent=parent; } itemNode.parent=grandParent; if(grandParent!=null){ if(grandParent.index>itemNode.index){ grandParent.left=itemNode; }else{ grandParent.right=itemNode; } } } public static class Node<T> { Node<T> parent; int index; T t; Node<T> left; Node<T> right; public Node(Node<T> parent, int index, T t) { super(); this.parent = parent; this.index = index; this.t = t; } }}

上一篇：与现有.NET事件桥接

下一篇：codeforces 782B The Meeting Place Cannot Be Changed

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注