# HG changeset patch
# User Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
# Date 1312986957 -32400
# Node ID 24613dfbaeabaab6c76083661ebb8a653d04fdfd
# Parent  36f2373f867b0c809f6309aab9a3c5fa657ab81d
finished implementing AVL-Tree remove operation

diff -r 36f2373f867b -r 24613dfbaeab src/tree/AVLTreeMap.java
--- 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>