--- a/src/tree/AVLTreeMap.java	Wed Jul 06 15:19:52 2011 +0900
+++ b/src/tree/AVLTreeMap.java	Tue Aug 09 11:13:36 2011 +0900
@@ -1,8 +1,5 @@
 package tree;
 
-import java.util.LinkedList;
-import java.util.Random;
-
 public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V>
 {
 	private Node<K,V> root;
@@ -12,22 +9,11 @@
 	{
 		AVLTreeMap<Integer,String> map = new AVLTreeMap<Integer,String>();
 		
-		Random r = new Random();
-		LinkedList<Integer> keys = new LinkedList<Integer>();
-		for(int i = 0;i < 30000;i ++){
-			int num = r.nextInt();
-			keys.add(num);
-			map.put(num,Integer.toString(num));
-		}
-		
-		for(Integer key : keys){
-			String value = map.get(key);
-			if(!key.toString().equals(value)){
-				System.out.println("gehoge");
-			}
-		}
-		
-		System.out.println("hoge");
+		map.put(10,"10");
+		map.put(20,"20");
+		map.put(30,"20");
+		map.put(5,"5");
+		map.put(7,"7");
 	}
 	
 	public AVLTreeMap()
@@ -59,7 +45,7 @@
 			}
 			
 			cur.right = _put(cur.right,key,value);
-			cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth);
+			cur.rdepth = Math.max(cur.right.ldepth,cur.right.rdepth) + 1;
 			int diff = cur.rdepth - cur.ldepth;
 			
 			if(diff > 1){
@@ -72,7 +58,6 @@
 					return doubleRotate(cur,OP_RIGHTLEFT);
 				}
 			}
-			
 		}else if(result > 0){
 			//left
 			if(cur.left == NULL_NODE){
@@ -103,6 +88,130 @@
 		return cur;
 	}
 	
+	public V remove(K key)
+	{
+		RemoveResult<K,V> r = findRemoveTarget(root,key);
+		root = r.cur;
+		return r.target.value;
+	}
+	
+	private RemoveResult<K,V> findRemoveTarget(Node<K,V> cur,K key)
+	{
+		int result = cur.key.compareTo(key);
+		if(result < 0){
+			//right
+			if(cur == NULL_NODE){
+				return new RemoveResult<K,V>(cur,NULL_NODE);
+			}
+			
+			RemoveResult<K,V> r = findRemoveTarget(cur.right,key);
+			cur.right = r.cur;
+			cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth) + 1;
+			
+			int diff = cur.rdepth - cur.ldepth;
+			if(diff > 1){
+				int rottype = result * cur.right.key.compareTo(key);
+				if(rottype > 0){
+					r.cur = singleRotate(cur,OP_RIGHT);
+					return r;
+				}else{
+					r.cur = doubleRotate(cur,OP_RIGHTLEFT);
+					return r;
+				}
+			}
+			
+			r.cur = cur;
+			return r;
+		}else if(result > 0 ){
+			//left
+			if(cur == NULL_NODE){
+				return new RemoveResult<K,V>(cur,NULL_NODE);
+			}
+			
+			RemoveResult<K,V> r = findRemoveTarget(cur.left,key);
+			cur.left = r.cur;
+			cur.ldepth = Math.max(cur.left.rdepth,cur.left.ldepth) + 1;
+			
+			int diff = cur.rdepth - cur.ldepth;
+			if(diff > 1){
+				int rottype = result * cur.left.key.compareTo(key);
+				if(rottype > 0){
+					r.cur = singleRotate(cur,OP_LEFT);
+					return r;
+				}else{
+					r.cur = doubleRotate(cur,OP_LEFTRIGHT);
+					return r;
+				}
+			}
+			
+			r.cur = cur;
+			return r;
+		}else{
+			//find
+			if(cur.left == NULL_NODE && cur.right == NULL_NODE){
+				//delete
+				return new RemoveResult<K,V>(NULL_NODE,cur);
+			}
+			
+			if(cur.left != NULL_NODE && cur.right == NULL_NODE){
+				//replace left
+				return new RemoveResult<K,V>(cur.left,cur);
+			}
+			
+			if(cur.left == NULL_NODE && cur.right != NULL_NODE){
+				//replace right
+				return new RemoveResult<K,V>(cur.right,cur);
+			}
+			
+			//both nodes are not null
+			RemoveResult<K,V> r = findSubstituteNode(cur.left);
+			cur.key = r.target.key;
+			cur.value = r.target.value;
+			cur.right = r.cur;
+			cur.rdepth = Math.max(cur.ldepth,cur.rdepth) + 1;
+			
+			int diff = cur.rdepth - cur.ldepth;
+			if(diff > 1){
+				r.cur = doubleRotate(cur,OP_LEFTRIGHT);
+			}
+			
+			return r;
+		}
+	}
+	
+	private RemoveResult<K,V> findSubstituteNode(Node<K,V> cur)
+	{
+		if(cur.right != NULL_NODE){
+			RemoveResult<K,V> result = findSubstituteNode(cur.right);
+			cur.right = result.cur;
+			cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth) + 1;
+			
+			int diff = cur.ldepth - cur.rdepth;
+			if(diff > 1){
+				result.cur = singleRotate(cur.left,OP_LEFT);
+				return result;
+			}
+			
+			result.cur = cur;
+			return result;
+		}
+		
+		RemoveResult<K,V> result = new RemoveResult<K,V>(cur.left,cur);
+		return result;
+	}
+	
+	private static class RemoveResult<K,V>
+	{
+		Node<K,V> cur;
+		Node<K,V> target;
+		
+		public RemoveResult(Node<K,V> cur,Node<K,V> target)
+		{
+			this.cur = cur;
+			this.target = target;
+		}
+	}
+	
 	private static final int OP_LEFT = 1;
 	private static final int OP_RIGHT = 2;
 	
@@ -167,36 +276,25 @@
 		return cur.value;
 	}
 	
-	@Override
-	public V remove(K key)
-	{
-		
-	}
-	
-	private Node<K,V> _remove(K key)
-	{
-		
-	}
-	
 	private static class Node<K,V>
 	{
 		K key;
 		V value;
 		
+		int rdepth;
+		int ldepth;
+		
 		Node<K,V> left;
 		Node<K,V> right;
 		
-		int ldepth;
-		int rdepth;
-		
 		public Node(K key,V value,int rdepth,int ldepth,Node<K,V> left,Node<K,V> right)
 		{
+			this.right = right;
+			this.left = left;
+			this.ldepth = ldepth;
+			this.rdepth = rdepth;
 			this.key = key;
 			this.value = value;
-			this.ldepth = ldepth;
-			this.rdepth = rdepth;
-			this.left = left;
-			this.right = right;
 		}
 		
 		@Override