JAVA之伸展樹

2019-11-11 00:11:30

字體：大中小

來源：轉載

供稿：網友

伸展樹與二叉平衡查找樹 AVL樹（帶有平衡條件的樹）查找的時候最壞的情形為0（N）并不壞，只要它不經常發生就可以。任何一次訪問，即使花費0（N），任然可能非?？?。具有最壞運行時間0（N）但保證對任意M次連續操作最多花費O（MlogN）運行時間確實讓人滿意了。伸展樹和其它樹的區別就是沒訪問一個節點的時候，那個節點就會成為根節點，這樣下次訪問的時候時間為0（1）并且與二叉平衡查找樹比少了高度的屬性和判斷平衡信息，因此從某種程度上簡化代碼。

在伸展樹中最主要的一部分就是伸展，分為兩種情況第一種是之字形（zig-zag）情形，第二種就是一字形（zig-zig） 這里寫圖片描述

package tree;/* * 伸展樹：他保證從空樹開始連續M次對樹的操作最多花費0（MlogN）時間 */public class STree<AnyType extends Comparable<? super AnyType>>{ PRivate Node root; private class Node{ public Node left;//左孩子 public Node right;//右孩子 public Node parent;//父親節點 public AnyType x;//data數據 public Node(AnyType x){ this.x = x; parent = null; left = null; right = null; } } public STree(){ root = null; } //查找 public AnyType find(AnyType key){ root = find(root, key); if(root == null || root.x.compareTo(key) != 0) return null; return root.x; } private Node find(Node p, AnyType key){ if(p == null || key == null) return null; Node prep = null; while(p != null){ prep = p; int cmp = key.compareTo(p.x); if(cmp < 0) p = p.left; else if(cmp > 0) p = p.right; else break; } root = splay(prep); return root; } //插入 public void insert(AnyType data){ if(data == null) return; if(root == null){ root = new Node(data); return; } Node t = find(root, data); int cmp = data.compareTo(t.x); if(cmp == 0){//更新value root.x = data; return; } root = new Node(data); //先把T分為左右子樹，再合并 if(cmp < 0){//插入新根，以t->lchild和t為左/右孩子 Node x = t.left; root.left = x; root.right = t; t.parent = root; if(x != null){ x.parent = root; t.left = null; } }else if(cmp > 0){ Node x = t.right; root.left = t; root.right = x; t.parent = root; if(x != null){ x.parent = root; t.right = null; } } } //刪除 public void delect(AnyType key){ if(key == null) return; Node t = find(root, key); if(t == null || key.compareTo(t.x) != 0) return; if(t.right == null){//右子樹為空 root = root.left; root.parent = null; return; } //右子數不空 //1.刪除T節點，得到子樹tl, tr Node tl = t.left, tr = t.right; tr.parent = null; //2.將右子樹最小節點min伸展至右子樹樹根，min一定沒有左子節點 Node min = min(tr); //3.將tl作為左子樹鏈接到min上 min.left = tl; if(tl != null) tl.parent = min; root = min; } public AnyType min(){ if(root == null) return null; root = min(root); return root.x; } private Node min(Node x){ if(x == null) return null; while(x.left != null) x = x.left; x = splay(x); return x; } public AnyType max(){ if(root == null) return null; root = max(root); return root.x; } private Node max(Node x){ if(x == null) return null; while(x.right != null) x = x.right; x = splay(x); return x; } private Node splay(Node v){//v是找到的節點 if(v == null) return null; Node p, g; //v的父親與祖父 //自上而下，反復對v做雙層伸展 while((p = v.parent) != null && (g = p.parent) != null){ Node gg = g.parent;//（great-grand parent）為父 if(isLChild(v)){ if(isLChild(p)){//zig-zig(g)先g結點右旋，zig（p）在p右旋 attachAsLChild(g, p.right); attachAsRChild(p, g); attachAsLChild(p, v.right); attachAsRChild(v, p); }else{//zig-zag(p)先p右旋，再g左旋zag（g） attachAsLChild(p, v.right); attachAsRChild(v, p); attachAsRChild(g, v.left); attachAsLChild(v, g); } }else{ if(isRChild(p)){//zag-zag,zag(g)先g結點左旋，zig(p)再p左旋 attachAsRChild(g, p.left); attachAsLChild(p.left, g); attachAsRChild(p, v.left); attachAsLChild(v, p); }else{//zag-zig,先p左旋，zag(p),再g右旋zig(g) attachAsRChild(p, v.left); attachAsLChild(v, p); attachAsLChild(g, v.right); attachAsRChild(v, g); } } //若v原先的曾祖父gg不存在，則v現在應為樹根 if(gg == null) v.parent = null; else{//否則，gg此后應該以v作為左或右孩子 if(gg.left == g) attachAsLChild(gg, v); else attachAsRChild(gg, v); } } //雙層伸展結束時，必有g == null, 但p可能非空 //若p果真非空，則額外在做一次單旋 if(p != null && p == v.parent){ if(isLChild(v)){//zig attachAsRChild(p, v.right); attachAsRChild(v, p); }else{//zag attachAsRChild(p, v.left); attachAsLChild(v, p); } } v.parent = null; return v; } //判斷n是否是父節點的左孩子 private boolean isLChild(Node n){ Node p = n.parent; return p.left == n; } //判斷n是否是父節點的右孩子 private boolean isRChild(Node n){ Node p = n.parent; return p.right == n; } //在節點p與rc（可能為空）之間建立父（左）子關系 private void attachAsLChild(Node parent, Node lchild){ parent.left = lchild; if(lchild != null) lchild.parent = parent; } //在節點p與rc（可能為空）之間建立父（右）子關系 private void attachAsRChild(Node parent, Node rchild){ parent.right = rchild; if(rchild != null) rchild.parent = parent; } public void prearder(){ prearder(root); System.out.println("前序遍歷"); System.out.println(); } private void prearder(Node p){ if(p == null) return; System.out.print(p.x+" "); prearder(p.left); prearder(p.right); } //測試 public static void main(String[] args){ STree<Integer> st = new STree<Integer>(); for(int i=0; i<10; i++) st.insert(i); st.find(5); st.prearder(); }}

上一篇：java中transient關鍵字學習記錄

下一篇：那些經常被遺忘的 Java 面試題