E81086713E446D36F62B2AA2A3502B5EB155

Java杂家

杂七杂八。。。一家之言

BlogJava 首页 新随笔 联系 聚合 管理
  141 Posts :: 1 Stories :: 174 Comments :: 0 Trackbacks
伸展树与半伸展树属于自组织的数据结构,能按访问频率调整节点的位置
调整一般通过如下方式:
1)绕根的单旋转,跟AVL的单旋转类似
2)一字型旋转(ZigZig Rotation)
3)之字形旋转(ZigZag Rotation)

旋转操作较简单,有点点繁琐。
半伸展树不做完全的一字型旋转,它只让父节点绕祖父节点做单旋转。

不管怎样,每次访问(插入/查找 ,删除时展开被删除父节点)后把该节点调整到根节点的位置


伸展树代码:
package algorithms.tree;





/**
 * 
@author yovn
 *
 
*/
public class SplayTree<extends Comparable<E>> extends DefaultBSTree<E> implements BSTree<E> {

    
    
    
static class SplayTreeNode<extends Comparable<E>> extends BSTNode<E>
    {

        SplayTreeNode
<E> parent;
        
        SplayTreeNode(SplayTreeNode
<E> parent,E key) {
            
super(key);
            
this.parent=parent;
            
        
        }
        
    }
    
    
    
    @Override
    
public boolean delete(E ele) {
          
return _delete((SplayTreeNode<E>)root,ele);
    }



    
private boolean _delete(SplayTreeNode<E> pointer, E ele) {
        
int cmp=ele.compareTo(pointer.key);
        
while(cmp!=0)
        {
            
if(cmp<0)
            {
                pointer
=(SplayTreeNode<E>)pointer.left;
            }
            
else
            {
                pointer
=(SplayTreeNode<E>)pointer.right;
            }
            
if(pointer==null)return false;
            cmp
=ele.compareTo(pointer.key);
        }
        
//okay find it
        SplayTreeNode<E> p=pointer.parent;
        
if(pointer.left==null)
        {
            
if(p!=null)
            {
                keep_right(pointer);
                splay(p);
            }
            
else {
                root 
= p.right;
                
if(root!=null)((SplayTreeNode<E>)root).parent=null;
            }
            
        }
        
else if(pointer.right==null)
        {
            
if(p!=null)
            {
                keep_left(pointer);
                splay(p);
            }
            
else {
                root 
= p.left;
                
if(root!=null)((SplayTreeNode<E>)root).parent=null;
            }
        }
        
else
        {
            SplayTreeNode
<E> todo=(SplayTreeNode<E>)pointer.left;
            SplayTreeNode
<E> todoP=null;
            
while(todo.right!=null)
            {
                todoP
=todo;
                todo
=(SplayTreeNode<E>)todo.right;
            }
            pointer.key
=todo.key;
            
if (todoP != null) {
                todoP.right 
= todo.left;
                
if (todo.left != null)
                    ((SplayTreeNode
<E>) todo.left).parent = todoP;
            }
            
else
            {
                pointer.left
=null;
            }
            splay(pointer.parent);
            
        }
        
return true;
    }



    
private void keep_left(SplayTreeNode<E> pointer) {
        SplayTreeNode
<E> p=pointer.parent;
        
if(p.left==pointer)
        {
            p.left
=pointer.left;
            
if(p.left!=null)((SplayTreeNode<E>)p.left).parent=p;
        }
        
else if(p.right==pointer)
        {
            p.right
=pointer.left;
            
if(p.right!=null)((SplayTreeNode<E>)p.right).parent=p;
        }
        
    }



    
private void keep_right(SplayTreeNode<E> pointer) {
        SplayTreeNode
<E> p=pointer.parent;
        
if(p.left==pointer)
        {
            p.left
=pointer.right;
            
if(p.left!=null)((SplayTreeNode<E>)p.left).parent=p;
        }
        
else if(p.right==pointer)
        {
            p.right
=pointer.right;
            
if(p.right!=null)((SplayTreeNode<E>)p.right).parent=p;
        }
        
    }



    



    
protected void splay(SplayTreeNode<E> cur) {
    
        
if(cur==null)return;
    
        
while(cur!=root)
        {
            
if(cur.parent==root)
            {
                
//single Rotation
                SingleRotation(cur,cur.parent);
                cur.parent
=null;
                root
=cur;
            
            }
            
else if(cur.parent.left==cur&&cur.parent.parent.left==cur.parent)
            {
                
                cur
=Left_ZigZig(cur,cur.parent,cur.parent.parent);
                
            }
            
else if(cur.parent.right==cur&&cur.parent.parent.right==cur.parent)
            {
                cur
=Right_ZigZig(cur,cur.parent,cur.parent.parent);
            }
            
else if(cur.parent.left==cur&&cur.parent.parent.right==cur.parent)
            {
                cur
=RL_ZigZag(cur,cur.parent,cur.parent.parent);
            }
            
else if(cur.parent.right==cur&&cur.parent.parent.left==cur.parent)
            {
                cur
=LR_ZigZag(cur,cur.parent,cur.parent.parent);
            }
            
else
            {
                System.out.println(
"Oooops!!!");
            }
        }
    }



    
private SplayTreeNode<E> LR_ZigZag(SplayTreeNode<E> cur,
            SplayTreeNode
<E> p, SplayTreeNode<E> g) {
        SplayTreeNode
<E> gp=g.parent;
        
        g.left
=cur.right;
        setParent(cur.right,g);
        
        g.parent
=cur;
        cur.right
=g;
        
        p.right
=cur.left;
        setParent(cur.left,p);
        
        p.parent
=cur;
        cur.left
=p;
        
if(gp!=null)
        {
            
if(gp.left==g)
            {
                gp.left
=cur;
            }
            
else
            {
                gp.right
=cur;
                
            }
        }
        
else root=cur;
        cur.parent
=gp;
        
return cur;
    }



    
private SplayTreeNode<E> RL_ZigZag(SplayTreeNode<E> cur,
            SplayTreeNode
<E> p, SplayTreeNode<E> g) {
        SplayTreeNode
<E> gp=g.parent;
        
        g.right
=cur.left;
        setParent(cur.left,g);
        
        g.parent
=cur;
        cur.left
=g;
        
        p.left
=cur.right;
        setParent(cur.right,p);
        
        p.parent
=cur;
        cur.right
=p;
        
if(gp!=null)
        {
            
if(gp.left==g)
            {
                gp.left
=cur;
            }
            
else
            {
                gp.right
=cur;
                
            }
        }
        
else root=cur;
        cur.parent
=gp;
        
return cur;
    }



    
protected SplayTreeNode<E> Right_ZigZig(SplayTreeNode<E> cur, SplayTreeNode<E> p,
            SplayTreeNode
<E> g) {
        SplayTreeNode
<E> gp=g.parent;
        
        g.right
=p.left;
        setParent(p.left,g);
        
        
        p.right
=cur.left;
        setParent(cur.left,p);
        
        g.parent
=p;
        p.left
=g;
        
        p.parent
=cur;
        cur.left
=p;
        
if(gp!=null)
        {
            
if(gp.left==g)
            {
                gp.left
=cur;
            }
            
else
            {
                gp.right
=cur;
                
            }
        }
        
else root=cur;
        cur.parent
=gp;
        
return cur;
        
    }



    
protected SplayTreeNode<E> Left_ZigZig(SplayTreeNode<E> cur, SplayTreeNode<E> p,
            SplayTreeNode
<E> g) {
        SplayTreeNode
<E> gp=g.parent;
        g.left
=p.right;
        setParent(p.right,g);
        
        g.parent
=p;
        p.right
=g;
        
        
        p.left
=cur.right;
        setParent(cur.right,p);
        
        p.parent
=cur;
        cur.right
=p;
        
if(gp!=null)
        {
            
if(gp.left==g)
            {
                gp.left
=cur;
            }
            
else
            {
                gp.right
=cur;
                
            }
        }
        
else root=cur;
        cur.parent
=gp;
        
return cur;
        
    }



    
final void setParent(BSTNode<E> c, BSTNode<E> p) {
        
if(c!=null)((SplayTreeNode<E>)c).parent=(SplayTreeNode<E>)p;
        
    }



    
private void SingleRotation(SplayTreeNode<E> cur, SplayTreeNode<E> p) {
        
if(p.left==cur)
        {
            
            p.left
=cur.right;
            
if(cur.right!=null)((SplayTreeNode<E>)cur.right).parent=p;
            cur.right
=p;
            p.parent
=cur;
            
        }
        
else if(p.right==cur)
        {
            p.right
=cur.left;
            
if(cur.left!=null)((SplayTreeNode<E>)cur.left).parent=p;
            cur.left
=p;
            p.parent
=cur;
            
        }
        
        
    }



    @Override
    
public void insert(E ele) {

        
if (root == null) {
            root 
= new SplayTreeNode<E>(null,ele);
            
return;
        }
        _insert((SplayTreeNode
<E>)root,ele);
    }
    
    
private final void _insert(SplayTreeNode<E> pointer,E ele)
    {
        
        
int cmp=pointer.key.compareTo(ele);
        
if(cmp==0)
        {
            
throw new IllegalArgumentException();
        }
        
        
if(cmp>0)
        {
            
if(pointer.left==null)
            {
                pointer.left 
=new SplayTreeNode<E>(pointer,ele);
                splay((SplayTreeNode
<E>)pointer.left);
                
return;
            }
             _insert((SplayTreeNode
<E>)pointer.left,ele);
            
        }
        
else
        {
            
if(pointer.right==null)
            {
                pointer.right
=new SplayTreeNode<E>(pointer,ele);
                splay((SplayTreeNode
<E>)pointer.right);
                
return ;
            }
            _insert((SplayTreeNode
<E>)pointer.right,ele);
        }
    }


    

    @Override
    
public boolean search(E ele) {
        
return _search((SplayTreeNode<E>)root,ele);
    }

    
    
private boolean _search(SplayTreeNode<E> pointer, E ele) {
        
if(pointer==null)return false;
        
int cmp=pointer.key.compareTo(ele);
        
if(cmp==0)
        {
            splay(pointer);
            
return true;
        }
        
        
if(cmp>0)
        {
        
            
             
return _search((SplayTreeNode<E>)pointer.left,ele);
            
        }
        
else
        {
            
            
            
return _search((SplayTreeNode<E>)pointer.right,ele);
        }
    }


    
/**
     * 
     
*/
    
public SplayTree() {
    
    }

}
半伸展树仅仅改变一下一字旋转时的操作:
package algorithms.tree;


/**
 * 
@author yovn
 *
 
*/
public class SemiPlayTree<extends Comparable<E>>extends SplayTree<E> {

    @Override
    
protected algorithms.tree.SplayTree.SplayTreeNode<E> Left_ZigZig(
            algorithms.tree.SplayTree.SplayTreeNode
<E> cur,
            algorithms.tree.SplayTree.SplayTreeNode
<E> p,
            algorithms.tree.SplayTree.SplayTreeNode
<E> g) {
        SplayTreeNode
<E> gp=g.parent;
        g.left
=p.right;
        setParent(p.right,g);

        p.right
=g;
        g.parent
=p;
        
if(gp!=null)
        {
            
if(gp.left==g)
            {
                gp.left
=p;
            }
            
else
            {
                gp.right
=p;
                
            }
        }
        
else root=p;
        p.parent
=gp;
        
return p;
    }

    @Override
    
protected algorithms.tree.SplayTree.SplayTreeNode<E> Right_ZigZig(
            algorithms.tree.SplayTree.SplayTreeNode
<E> cur,
            algorithms.tree.SplayTree.SplayTreeNode
<E> p,
            algorithms.tree.SplayTree.SplayTreeNode
<E> g) {
        SplayTreeNode
<E> gp=g.parent;
        g.right
=p.left;
        setParent(p.left,g);

        p.left
=g;
        g.parent
=p;
        
if(gp!=null)
        {
            
if(gp.left==g)
            {
                gp.left
=p;
            }
            
else
            {
                gp.right
=p;
                
            }
        }
        
else root=p;
        p.parent
=gp;
        
return p;
    }

    

}


posted on 2007-12-19 00:39 DoubleH 阅读(2401) 评论(0)  编辑  收藏 所属分类: Memorandum

只有注册用户登录后才能发表评论。


网站导航: