Mercurial > hg > Members > shoshi > AADS

changeset 2:36f2373f867b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added AVLTree.java remove operation
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Wed, 10 Aug 2011 20:14:19 +0900
parents 15920e9b562d
children 24613dfbaeab
files src/tree/AVLTreeMap.java
diffstat 1 files changed, 66 insertions(+), 93 deletions(-) [+]
line wrap: on
line diff
--- a/src/tree/AVLTreeMap.java	Tue Aug 09 11:13:36 2011 +0900
+++ b/src/tree/AVLTreeMap.java	Wed Aug 10 20:14:19 2011 +0900
@@ -11,9 +11,11 @@
 		
 		map.put(10,"10");
 		map.put(20,"20");
-		map.put(30,"20");
+		map.put(30,"30");
 		map.put(5,"5");
 		map.put(7,"7");
+		
+		map.remove(20);
 	}
 	
 	public AVLTreeMap()
@@ -88,127 +90,98 @@
 		return cur;
 	}
 	
-	public V remove(K key)
+	public V remove(K _key)
 	{
-		RemoveResult<K,V> r = findRemoveTarget(root,key);
+		RemoveResult<K,V> r = removeTarget(root,_key);
 		root = r.cur;
-		return r.target.value;
+		return r.removed.value;
 	}
 	
-	private RemoveResult<K,V> findRemoveTarget(Node<K,V> cur,K key)
+	private RemoveResult<K,V> removeTarget(Node<K,V> _cur,K _key)
 	{
-		int result = cur.key.compareTo(key);
+		int result = _cur.key.compareTo(_key);
+		
 		if(result < 0){
 			//right
-			if(cur == NULL_NODE){
-				return new RemoveResult<K,V>(cur,NULL_NODE);
+			if(_cur.right == NULL_NODE){
+				//not found
+				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;
-				}
-			}
+			RemoveResult<K,V> r = removeTarget(_cur.right,_key);
+			_cur.right = r.cur;
+			_cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1;
 			
-			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;
+			//要素の削除では，部分木の要素が減ったと考えるのではなく，もう片方の部分木の要素が増えたと考えれば書きやすい
+			int diff = _cur.ldepth - _cur.rdepth;
 			if(diff > 1){
-				int rottype = result * cur.left.key.compareTo(key);
-				if(rottype > 0){
-					r.cur = singleRotate(cur,OP_LEFT);
-					return r;
+				//determine that rotation will be single or double
+				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;
+					r.cur = doubleRotate(_cur,OP_LEFTRIGHT);
 				}
 			}
 			
-			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);
+		}else if(result > 0){
+			//left
+			if(_cur.left == NULL_NODE){
+				//not found
+				return new RemoveResult<K,V>(_cur,NULL_NODE);
 			}
 			
-			return r;
+			RemoveResult<K,V> r = removeTarget(_cur.right,_key);
+			_cur.left = r.cur;
+			_cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1;
+
+			int diff = _cur.rdepth - _cur.ldepth;
+			if(diff > 1){
+				//determine that rotation will be single or double
+				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);
+				}
+			}
 		}
+		
+		//find.
+		
+		//見つかったので，ノードの代わりのノードを検索する．
+		RemoveResult<K,V> r = findNearestNode(_cur.left);
+		if(r != null){
+			
+		}
+		
+		//見つかった場合は自身を削除対象とする
+		
+		
+		return null;
 	}
 	
-	private RemoveResult<K,V> findSubstituteNode(Node<K,V> cur)
+	public RemoveResult<K,V> findNearestNode(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;
+		if(_cur == NULL_NODE){
+			return null;
 		}
 		
-		RemoveResult<K,V> result = new RemoveResult<K,V>(cur.left,cur);
-		return result;
+		return null;
 	}
 	
-	private static class RemoveResult<K,V>
+	public static class RemoveResult<K,V>
 	{
-		Node<K,V> cur;
-		Node<K,V> target;
+		public Node<K,V> removed;
+		public Node<K,V> cur;
 		
-		public RemoveResult(Node<K,V> cur,Node<K,V> target)
+		public RemoveResult(Node<K,V> _removed,Node<K,V> _cur)
 		{
-			this.cur = cur;
-			this.target = target;
+			removed = _removed;
+			cur = _cur;
 		}
 	}