Mercurial > hg > Members > shoshi > AADS
diff src/tree/AVLTreeMap.java @ 3:24613dfbaeab default tip
finished implementing AVL-Tree remove operation
| author | Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Wed, 10 Aug 2011 23:35:57 +0900 |
| parents | 36f2373f867b |
| children |
line wrap: on
line diff
--- a/src/tree/AVLTreeMap.java Wed Aug 10 20:14:19 2011 +0900 +++ b/src/tree/AVLTreeMap.java Wed Aug 10 23:35:57 2011 +0900 @@ -110,6 +110,7 @@ RemoveResult<K,V> r = removeTarget(_cur.right,_key); _cur.right = r.cur; + r.cur = _cur; _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1; //要素の削除では，部分木の要素が減ったと考えるのではなく，もう片方の部分木の要素が増えたと考えれば書きやすい @@ -135,6 +136,7 @@ RemoveResult<K,V> r = removeTarget(_cur.right,_key); _cur.left = r.cur; + r.cur = _cur; _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1; int diff = _cur.rdepth - _cur.ldepth; @@ -154,14 +156,34 @@ //見つかったので，ノードの代わりのノードを検索する． RemoveResult<K,V> r = findNearestNode(_cur.left); - if(r != null){ + if(r == null){ + //左部分木は存在していない、そのため右部分木をかわりに配置する + r = new RemoveResult<K,V>(_cur,_cur.right); + }else{ + //左部分木より代替ノードを取得した + r.removed = new Node<K,V>(_cur.key,_cur.value,0,0,NULL_NODE,NULL_NODE); + _cur.key = r.removed.key; + _cur.value = r.removed.value; + _cur.left = r.cur; + r.cur = _cur; + + _cur.ldepth = Math.max(_cur.left.ldepth,_cur.left.rdepth) + 1; + int diff = _cur.rdepth - _cur.ldepth; + if(diff > 1){ + Node<K,V> right = _cur.right; + int rottype = right.rdepth - right.ldepth; + if(rottype >= 0){ + r.cur = singleRotate(_cur,OP_RIGHT); + }else{ + r.cur = doubleRotate(_cur,OP_RIGHTLEFT); + } + } + + r.removed = _cur; } - //見つかった場合は自身を削除対象とする - - - return null; + return r; } public RemoveResult<K,V> findNearestNode(Node<K,V> _cur) @@ -170,7 +192,27 @@ return null; } - return null; + RemoveResult<K,V> r = findNearestNode(_cur.right); + if(r == null){ + r = new RemoveResult<K,V>(_cur,_cur.left); + return r; + } + _cur.right = r.cur; + _cur.ldepth = Math.max(_cur.left.ldepth,_cur.left.rdepth) + 1; + r.cur = _cur; + int diff = _cur.rdepth - _cur.ldepth; + + if(diff > 1){ + Node<K,V> left = _cur.left; + int rottype = left.ldepth - left.rdepth; + if(rottype >= 0){ + r.cur = singleRotate(_cur,OP_LEFT); + }else{ + r.cur = doubleRotate(_cur,OP_LEFTRIGHT); + } + } + + return r; } public static class RemoveResult<K,V>