0001 /* 0002 * 伸展树 0003 * 基于BSTree的扩充 0004 */ 0005 0006 package dsa; 0007 0008 public class SplayTree extends BSTree implements Dictionary { 0009 /**************************** 构造方法 ****************************/ 0010 public SplayTree() { super(); } 0011 public SplayTree(BinTreePosition r) { super(r); } 0012 public SplayTree(BinTreePosition r, Comparator c) { super(r, c); } 0013 0014 /**************************** 词典方法(覆盖父类BSTree) ****************************/ 0015 //若词典中存在以key为关键码的条目,则返回其中的一个条目;否则,返回null 0016 public Entry find(Object key) { 0017 if (isEmpty()) return null; 0018 BSTreeNode u = binSearch((BSTreeNode)root, key, C); 0019 root = moveToRoot(u); 0020 return (0 == C.compare(key, u.getKey())) ? (Entry)u.getElem() : null; 0021 } 0022 0023 //插入条目(key, value),并返回该条目 0024 public Entry insert(Object key, Object value) { 0025 Entry e = super.insert(key, value);//调用父类方法完成插入 0026 root = moveToRoot(lastV);//重新平衡化 0027 return e; 0028 } 0029 0030 //若词典中存在以key为关键码的条目,则将摘除其中的一个并返回;否则,返回null 0031 public Entry remove(Object key) { 0032 Entry e = super.remove(key);//调用父类方法完成删除 0033 if (null != e && null != lastV) root = moveToRoot(lastV);//重新平衡化 0034 return e; 0035 } 0036 0037 /**************************** 辅助方法 ****************************/ 0038 //从节点z开始,自上而下重新平衡化 0039 protected static BinTreePosition moveToRoot(BinTreePosition z) { 0040 while (z.hasParent()) 0041 if (!z.getParent().hasParent()) 0042 if (z.isLChild()) z = zig(z); 0043 else z = zag(z); 0044 else if (z.isLChild()) 0045 if (z.getParent().isLChild()) z = zigzig(z); 0046 else z = zigzag(z); 0047 else if (z.getParent().isLChild()) z = zagzig(z); 0048 else z = zagzag(z); 0049 return z; 0050 } 0051 0052 //v为左孩子 0053 //顺时针旋转v,使之上升一层(伸展树) 0054 //返回新的子树根 0055 protected static BinTreePosition zig(BinTreePosition v) { 0056 if (null != v && v.isLChild()) {//v必须有父亲,而且必须是左孩子 0057 BinTreePosition p = v.getParent();//父亲 0058 BinTreePosition g = p.getParent();//祖父 0059 boolean asLChild = p.isLChild();//父亲是否祖父的左孩子 0060 v.secede();//摘出v(于是p的左孩子为空) 0061 BinTreePosition c = v.getRChild();//将v的右孩子 0062 if (null != c) p.attachL(c.secede());//作为p的左孩子 0063 p.secede();//摘出父亲 0064 v.attachR(p);//将p作为v的右孩子 0065 if (null != g)//若祖父存在,则将v作为其孩子 0066 if (asLChild) g.attachL(v); 0067 else g.attachR(v); 0068 } 0069 return v; 0070 } 0071 0072 //v为右孩子 0073 //逆时针旋转v,使之上升一层(伸展树) 0074 //返回新的子树根 0075 protected static BinTreePosition zag(BinTreePosition v) { 0076 if (null != v && v.isRChild()) {//v必须有父亲,而且必须是右孩子 0077 BinTreePosition p = v.getParent();//父亲 0078 BinTreePosition g = p.getParent();//祖父 0079 boolean asLChild = p.isLChild();//父亲是否祖父的左孩子 0080 v.secede();//摘出v(于是p的左孩子为空) 0081 BinTreePosition c = v.getLChild();//将v的左孩子 0082 if (null != c) p.attachR(c.secede());//作为p的右孩子 0083 p.secede();//摘出父亲 0084 v.attachL(p);//将p作为v的左孩子 0085 if (null != g)//若祖父存在,则将v作为其孩子 0086 if (asLChild) g.attachL(v); 0087 else g.attachR(v); 0088 } 0089 return v; 0090 } 0091 0092 //v为左孩子,父亲为左孩子 0093 //顺时针旋转v,使之上升两层(伸展树) 0094 //返回新的子树根 0095 protected static BinTreePosition zigzig(BinTreePosition v) { 0096 if (null != v && v.isLChild() && v.hasParent() && v.getParent().isLChild()) { 0097 BinTreePosition p = v.getParent();//父亲 0098 BinTreePosition g = p.getParent();//祖父 0099 BinTreePosition s = g.getParent();//曾祖父 0100 boolean asLChild = g.isLChild();//祖父是否曾祖父的左孩子 0101 g.secede(); 0102 p.secede(); 0103 v.secede(); 0104 BinTreePosition c;//临时变量,辅助孩子的移动 0105 c = p.getRChild(); if (null != c) g.attachL(c.secede());//p的右孩子作为g的左孩子 0106 c = v.getRChild(); if (null != c) p.attachL(c.secede());//v的右孩子作为p的左孩子 0107 p.attachR(g);//g作为p的右孩子 0108 v.attachR(p);//p作为v的右孩子 0109 if (null != s)//若曾祖父存在,则将v作为其孩子 0110 if (asLChild) s.attachL(v); 0111 else s.attachR(v); 0112 } 0113 return v; 0114 } 0115 0116 //v为右孩子,父亲为右孩子 0117 //顺时针旋转v,使之上升两层(伸展树) 0118 //返回新的子树根 0119 protected static BinTreePosition zagzag(BinTreePosition v) { 0120 if (null != v && v.isRChild() && v.hasParent() && v.getParent().isRChild()) { 0121 BinTreePosition p = v.getParent();//父亲 0122 BinTreePosition g = p.getParent();//祖父 0123 BinTreePosition s = g.getParent();//曾祖父 0124 boolean asLChild = g.isLChild();//祖父是否曾祖父的左孩子 0125 g.secede(); 0126 p.secede(); 0127 v.secede(); 0128 BinTreePosition c;//临时变量,辅助孩子的移动 0129 c = p.getLChild(); if (null != c) g.attachR(c.secede());//p的左孩子作为g的右孩子 0130 c = v.getLChild(); if (null != c) p.attachR(c.secede());//v的左孩子作为p的右孩子 0131 p.attachL(g);//g作为p的左孩子 0132 v.attachL(p);//p作为v的左孩子 0133 if (null != s)//若曾祖父存在,则将v作为其孩子 0134 if (asLChild) s.attachL(v); 0135 else s.attachR(v); 0136 } 0137 return v; 0138 } 0139 0140 //v为左孩子,父亲为右孩子 0141 //顺时针旋转v,使之上升两层(伸展树) 0142 //返回新的子树根 0143 protected static BinTreePosition zigzag(BinTreePosition v) { 0144 if (null != v && v.isLChild() && v.hasParent() && v.getParent().isRChild()) { 0145 BinTreePosition p = v.getParent();//父亲 0146 BinTreePosition g = p.getParent();//祖父 0147 BinTreePosition s = g.getParent();//曾祖父 0148 boolean asLChild = g.isLChild();//祖父是否曾祖父的左孩子 0149 g.secede(); 0150 p.secede(); 0151 v.secede(); 0152 BinTreePosition c;//临时变量,辅助孩子的移动 0153 c = v.getLChild(); if (null != c) g.attachR(c.secede());//v的左孩子作为g的右孩子 0154 c = v.getRChild(); if (null != c) p.attachL(c.secede());//v的右孩子作为p的左孩子 0155 v.attachL(g);//g作为v的左孩子 0156 v.attachR(p);//p作为v的右孩子 0157 if (null != s)//若曾祖父存在,则将v作为其孩子 0158 if (asLChild) s.attachL(v); 0159 else s.attachR(v); 0160 } 0161 return v; 0162 } 0163 0164 //v为右孩子,父亲为左孩子 0165 //顺时针旋转v,使之上升两层(伸展树) 0166 //返回新的子树根 0167 protected static BinTreePosition zagzig(BinTreePosition v) { 0168 if (null != v && v.isRChild() && v.hasParent() && v.getParent().isLChild()) { 0169 BinTreePosition p = v.getParent();//父亲 0170 BinTreePosition g = p.getParent();//祖父 0171 BinTreePosition s = g.getParent();//曾祖父 0172 boolean asLChild = g.isLChild();//祖父是否曾祖父的左孩子 0173 g.secede(); 0174 p.secede(); 0175 v.secede(); 0176 BinTreePosition c;//临时变量,辅助孩子的移动 0177 c = v.getRChild(); if (null != c) g.attachL(c.secede());//v的右孩子作为g的左孩子 0178 c = v.getLChild(); if (null != c) p.attachR(c.secede());//v的左孩子作为p的右孩子 0179 v.attachR(g);//g作为v的右孩子 0180 v.attachL(p);//p作为v的左孩子 0181 if (null != s)//若曾祖父存在,则将v作为其孩子 0182 if (asLChild) s.attachL(v); 0183 else s.attachR(v); 0184 } 0185 return v; 0186 } 0187 }