splay tree 主要適用于對統(tǒng)一對象的連續(xù)讀取 splay(insertNode) 操作 就是將當(dāng)前節(jié)點移動到 root節(jié)點
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; } }}新聞熱點
疑難解答
