Mercurial > hg > Members > tatsuki > TreeMap

changeset 17:ab026848665a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change delete throw exception Patern
author tatsuki
date Mon, 27 Apr 2015 23:08:57 +0900
parents 19dd02f1ee8e
children a02ce8467bad
files src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java
diffstat 6 files changed, 231 insertions(+), 133 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Tue Apr 21 17:29:15 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Mon Apr 27 23:08:57 2015 +0900
@@ -12,9 +12,9 @@
 
 
     @Override
-    public Tuple deleteNode() {
+    public Node deleteNode() throws RotateParent {
         EmptyNode<K, V> emptyNode = new EmptyNode<K, V>(key);
-        return new Tuple(emptyNode, true);
+        throw new RotateParent(emptyNode);
     }
 
     @Override
@@ -87,45 +87,51 @@
      * @return
      */
     @Override
-    public Tuple replaceNode(Node<K, V> parent) {
+    public Node replaceNode(Node<K, V> parent) throws RotateParent {
 
         Node<K, V> newNode = null;
         if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する
             return deleteNode();//黒が1つ減るので木のバランスを取る
-
         } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる
             newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right());
-
             if (!this.left().isRed()) //昇格させる木のrootが黒だったらバランスを取る
-                return new Tuple(newNode, true);
-            return new Tuple(newNode, false);
-
+                throw new RotateParent(newNode);
+            return newNode;
         } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる
             newNode = createNode(right().getKey(), right().getValue(), right().left(), right().right());
             if (!this.right().isRed()) //昇格させる木のrootが黒だったらバランスを取る
-                return new Tuple(newNode, true);
-            return new Tuple(newNode, false);
-
-        } else {//子ノードが左右にある場合
+                throw new RotateParent(newNode);
+            return newNode;
+        } else {//子ノードが左右にある場合 二回目はここには入らない
             //左の部分木の最大の値を持つNodeと自身を置き換える
             Node<K, V> cur = this.left();
-
             while (cur.right().isNotEmpty()) { //左の部分期の最大値を持つNodeを取得する
                 cur = cur.right();
             }
-
-
             if (this.left().right().isNotEmpty()) { //左の部分木が右の子を持っているか
-                Tuple leftSubTreeNode = this.left().deleteSubTreeMaxNode(null);//最大値を削除した左の部分木を返す。rootはthisと同じ。
-                Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.getNode(), this.right()); //rootをcurと入れ替えることでNodeの削除は完了する
-                return leftSubTreeNode.getNode().deleteBalance(newParent, leftSubTreeNode.getRebuildFlag());
-
-
+                try {
+                    Node leftSubTreeNode = this.left().deleteSubTreeMaxNode(null,Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。
+                    Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する
+                    return newParent;
+                } catch (RotateParent e) {
+                    Node leftSubTreeNode = e.getParent();
+                    Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
+                    return leftSubTreeNode.deleteBalance(newParent);
+                }
             } else {
-                Tuple leftSubTreeNode = this.left().replaceNode(this);//右の子がいなかった場合、左の子を昇格させるだけで良い。
-                Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode.getNode(), this.right());
-                return leftSubTreeNode.getNode().deleteBalance(newParent, leftSubTreeNode.getRebuildFlag());
-
+                Node leftSubTreeNode = null;
+                try {
+                    leftSubTreeNode = this.left().replaceNode(this);//右の子がいなかった場合、左の子を昇格させるだけで良い。
+                    Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
+                    return newParent;
+                } catch (RotateParent e) {
+                    Node node = e.getParent();
+                    //if (parent != null) {
+                    Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
+                    return node.deleteBalance(newParent);
+                    // }
+                    // return node;
+                }
             }
         }
 
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Tue Apr 21 17:29:15 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Mon Apr 27 23:08:57 2015 +0900
@@ -45,13 +45,13 @@
     }
 
     @Override
-    public Tuple replaceNode(Node<K, V> parent) { // not use method
-        return new Tuple(this, false);
+    public Node replaceNode(Node<K, V> parent) { // not use method
+        return this;
     }
 
     @Override
-    protected Tuple deleteNode() { //not use method
-        return new Tuple(this, false);
+    protected Node deleteNode() { //not use method
+        return this;
     }
 
     @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Tue Apr 21 17:29:15 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Mon Apr 27 23:08:57 2015 +0900
@@ -7,33 +7,52 @@
  */
 public abstract class Node<K, V> {
 
-    protected  final K key;
-    protected  final V value;
-    protected  final Node<K, V> right;
-    protected  final Node<K, V> left;
+    protected K key;
+    protected V value;
+    protected Node<K, V> right;
+    protected Node<K, V> left;
+    protected boolean rebuildFlag = false;
 
     public Node(K key, V value) {
         this.key = key;
         this.value = value;
-        this.left = null;
-        this.right = null;
     }
 
-    public Node(K key, V value,final Node<K, V> left, final Node<K, V> right) {
+    public Node(K key, V value, Node<K, V> left, Node<K, V> right) {
         this.key = key;
         this.value = value;
         this.right = right;
         this.left = left;
     }
 
+    public void setRebuildFlag(boolean rebuildFlag) {
+        this.rebuildFlag = rebuildFlag;
+    }
+
     public Node<K, V> left() {
         return left;
     }
 
-    public int compare(final K parentKey) {
+    public int compare(K parentKey) {
         return (parentKey.hashCode() - getKey().hashCode());
     }
 
+    public Optional<V> get(K key) {
+        Node<K, V> cur = this;
+
+        while (cur.isNotEmpty()) {
+            int result = compare(key);
+            if (result > 0)
+                cur = cur.right();
+            else if (result < 0)
+                cur = cur.left();
+            else if (result == 0)
+                return Optional.ofNullable(cur.getValue());
+        }
+        return Optional.ofNullable(null);
+    }
+
+
     public Node<K, V> right() {
         return right;
     }
@@ -47,22 +66,9 @@
     }
 
 
-    public Optional<V> get(final K key) {
-        Node<K, V> cur = this;
-        while (cur.isNotEmpty()) {
-            final int result = cur.compare(key);
-            if (result > 0)
-                cur = cur.right();
-            else if (result < 0)
-                cur = cur.left();
-            else if (result == 0)
-                return Optional.ofNullable(cur.getValue());
-        }
-        return Optional.ofNullable(null);
-    }
-
     public Node<K, V> put(K k, V value) {
         int result = compare(k);
+
         if (result > 0) {
             Node<K, V> node = right.put(k, value);
             node = createNode(key, this.value, left, node);
@@ -72,48 +78,86 @@
             return createNode(key, this.value, node, right).insBalance();
         }
         return createNode(key, value, left, right); // equals
+
     }
 
-    public Tuple delete(K key, Node<K, V> parent) {
+    public Node<K, V> delete(K key, Node<K, V> parent, Rotate side) throws RotateParent {
         if (this.isNotEmpty()) {
             int result = compare(key);
-            if (result > 0) {
-                Tuple node = right.delete(key, this);
-                if (parent == null || node == null)
-                    return node;
-                return node.getNode().deleteBalance(parent, node.getRebuildFlag());
-            } else if (result < 0) {
-                Tuple node = left.delete(key, this);
-                if (parent == null || node == null)
-                    return node;
-                return node.getNode().deleteBalance(parent, node.getRebuildFlag());
-            } else if (result == 0) {
-                Tuple node = replaceNode(parent); // equals
-                if (parent == null || node == null)
-                    return node;
-                return node.getNode().deleteBalance(parent, node.getRebuildFlag());
+
+            try {
+                Node<K, V> node = null;
+                if (result > 0) {
+                    node = right.delete(key, this, Rotate.R);
+                    if (node == null)
+                        return null;
+                    if (parent == null)
+                        return node;
+                } else if (result < 0) {
+                    node = left.delete(key, this, Rotate.L);
+                    if (node == null)
+                        return null;
+                    if (parent == null)
+                        return node;
+                } else if (result == 0) {
+                    node = replaceNode(parent);
+                    if (parent == null)// equals
+                        return node;
+                    if (side == Rotate.R)
+                        return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node);
+                    else
+                        return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right());
+
+                }
+                if (side == Rotate.L)
+                    return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right());
+                else
+                    return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node);
+            } catch (RotateParent e) {
+                Node node = e.getParent();
+                if (parent != null)
+                    return node.deleteBalance(parent);
+                return node;
             }
         }
         return null; // no key
     }
 
 
-    public Tuple deleteSubTreeMaxNode(Node<K, V> parent) {
-        Tuple node;
+    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent, Rotate side) throws RotateParent {
+        Node<K, V> node;
         if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る
-            node = right().deleteSubTreeMaxNode(this);
-            if (parent == null)
-                return node;
-            return node.getNode().deleteBalance(parent, node.getRebuildFlag());
+            try {
+                node = right().deleteSubTreeMaxNode(this, Rotate.R);
+                // return node;
+            } catch (RotateParent e) {
+                node = e.getParent();
+                if (parent == null)
+                    throw e;
+                return node.deleteBalance(parent);
+            }
+        } else {
+            try {
+                node = this.replaceNode(parent);
+                // return node;
+            } catch (RotateParent e) {
+                node = e.getParent();
+                if (parent == null)
+                    throw e;
+                return node.deleteBalance(parent);
+            }
         }
-        node = this.replaceNode(parent);
         if (parent == null)
             return node;
-        return node.getNode().deleteBalance(parent, node.getRebuildFlag());
+        if (side == Rotate.R)
+            return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node);
+        else
+            return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right());
+
     }
 
-    public Tuple deleteBalance(Node<K, V> parent, boolean flag) {
-        if (flag && !isRed()) {
+    public Node deleteBalance(Node<K, V> parent) throws RotateParent {
+        if (!isRed()) {
             if (0 > compare(parent.getKey())) { //自身がどちらの子かを調べる
                 boolean rightChild = parent.left().right().isRed();
                 boolean leftChild = parent.left().left().isRed();
@@ -121,7 +165,7 @@
                 if (!parent.isRed()) { //親が黒
                     if (!parent.left().isRed()) { //左の子が黒
                         if (!rightChild && !leftChild)
-                            return rebuildThree(parent, Rotate.R);
+                            throw new RotateParent(rebuildThree(parent, Rotate.R));
                         if (rightChild)
                             return rebuildfive(parent, Rotate.R);
                         else if (leftChild)
@@ -144,7 +188,7 @@
                 if (!parent.isRed()) { //親が黒
                     if (!parent.right().isRed()) { //左の子が黒
                         if (!rightChild && !leftChild)
-                            return rebuildThree(parent, Rotate.L);
+                            throw new RotateParent(rebuildThree(parent, Rotate.L));
                         if (rightChild)
                             return rebuildsix(parent, Rotate.L);
                         else if (leftChild)
@@ -162,64 +206,57 @@
                 }
             }
         }
-        Node newParent = null;
         if (0 > (compare(parent.getKey())))
-            newParent = parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
+            return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
         else
-            newParent = parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
-        return new Tuple(newParent, false);
+            return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
     }
 
-    protected Tuple rebuildTwo(Node<K, V> parent, Rotate side) { // case2
+    protected Node<K, V> rebuildTwo(Node<K, V> parent, Rotate side) throws RotateParent { // case2
         if (side == Rotate.L) { // rotate Left
-            Node<K, V> leftSubTreeRoot = parent.right().createNode(parent.getKey(), parent.getValue(), this, parent.right().left()); // check
-            Tuple leftNode = this.deleteBalance(leftSubTreeRoot, true);
-            Node<K, V> rightNode = parent.right().right();
-            Node newParent = parent.createNode(parent.right().getKey(), parent.right().getValue(), leftNode.getNode(), rightNode);
-            return new Tuple(newParent, false);
+            Node<K, V> node = parent.right();
+            Node<K, V> leftSubTreeRoot = node.createNode(parent.getKey(), parent.getValue(), this, node.left()); // check
+            Node<K, V> leftNode = this.deleteBalance(leftSubTreeRoot);
+            Node<K, V> rightNode = node.right();
+            return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNode);
         } else {  // rotate Right
-            Node<K, V> rightSubTreeRoot = parent.left().createNode(parent.getKey(), parent.getValue(), parent.left().right(), this);
-            Tuple rightNode = this.deleteBalance(rightSubTreeRoot, true);
-            Node<K, V> leftNode = parent.left().left();
-            Node newParent = parent.createNode(parent.left().getKey(), parent.left().getValue(), leftNode, rightNode.getNode());
-            return new Tuple(newParent, false);
+            Node<K, V> node = parent.left();
+            Node<K, V> rightSubTreeRoot = node.createNode(parent.getKey(), parent.getValue(), node.right(), this);
+            Node<K, V> rightNode = this.deleteBalance(rightSubTreeRoot);
+            Node<K, V> leftNode = node.left();
+            return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNode);
         }
-
     }
 
-    protected Tuple rebuildThree(Node<K, V> parent, Rotate side) { // case3 再起
+    protected Node rebuildThree(Node<K, V> parent, Rotate side) { // case3 再帰
         if (side == Rotate.L) {
             Node<K, V> rightNode;
             if (parent.right().isNotEmpty())
                 rightNode = new RedNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right()); // check
             else
                 rightNode = new EmptyNode<>();
-            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightNode);
-            return new Tuple(newParent, true);
+            return parent.createNode(parent.getKey(), parent.getValue(), this, rightNode);
         } else {
             Node<K, V> leftNode;
             if (parent.left().isNotEmpty())
                 leftNode = new RedNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right()); // check
             else
                 leftNode = new EmptyNode<>();
-            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), leftNode, this);
-            return new Tuple(newParent, true);
+            return parent.createNode(parent.getKey(), parent.getValue(), leftNode, this);
         }
     }
 
-    protected Tuple rebuildFour(Node<K, V> parent, Rotate side) { //case 4
+    protected Node rebuildFour(Node<K, V> parent, Rotate side) { //case 4
         if (side == Rotate.R) {
             Node<K, V> leftNode = new RedNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right());
-            Node newParent = new BlackNode<K, V>(parent.getKey(), parent.getValue(), leftNode, this);
-            return new Tuple(newParent, false);
+            return new BlackNode<K, V>(parent.getKey(), parent.getValue(), leftNode, this);
         } else {
             Node<K, V> rightNode = new RedNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right());
-            Node newParent = new BlackNode<K, V>(parent.getKey(), parent.getValue(), this, rightNode);
-            return new Tuple(newParent, false);
+            return new BlackNode<K, V>(parent.getKey(), parent.getValue(), this, rightNode);
         }
     }
 
-    protected Tuple rebuildfive(Node<K, V> parent, Rotate side) { //case5
+    protected Node rebuildfive(Node<K, V> parent, Rotate side) { //case5
         if (side == Rotate.R) { // rotate Left
             Node<K, V> leftChild = new RedNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right().left());
             Node<K, V> rightChild = parent.left().right().right();
@@ -235,17 +272,15 @@
         }
     }
 
-    protected Tuple rebuildsix(Node<K, V> parent, Rotate side) { //case6
+    protected Node rebuildsix(Node<K, V> parent, Rotate side) { //case6
         if (side == Rotate.L) { // rotate Left
             Node<K, V> leftChild = parent.right().createNode(parent.getKey(), parent.getValue(), this, parent.right().left()); //check
             Node<K, V> rightChild = new BlackNode<K, V>(parent.right().right().getKey(), parent.right().right().getValue(), parent.right().right().left(), parent.right().right().right());
-            Node newParent = parent.createNode(parent.right().getKey(), parent.right().getValue(), leftChild, rightChild);
-            return new Tuple(newParent, false);
+            return parent.createNode(parent.right().getKey(), parent.right().getValue(), leftChild, rightChild);
         } else {  // rotate Right
             Node<K, V> leftChild = new BlackNode<K, V>(parent.left().left().getKey(), parent.left().left().getValue(), parent.left().left().left(), parent.left().left().right());
             Node<K, V> rightChild = parent.left().createNode(parent.getKey(), parent.getValue(), parent.left().right(), this);
-            Node newParent = parent.createNode(parent.left().getKey(), parent.left().getValue(), leftChild, rightChild);
-            return new Tuple(newParent, false);
+            return parent.createNode(parent.left().getKey(), parent.left().getValue(), leftChild, rightChild);
         }
     }
 
@@ -260,9 +295,9 @@
 
     abstract boolean isRed();
 
-    public abstract Tuple replaceNode(Node<K, V> parent);
+    public abstract Node replaceNode(Node<K, V> parent) throws RotateParent;
 
-    protected abstract Tuple deleteNode();
+    protected abstract Node deleteNode() throws RotateParent;
 
     protected abstract int checkBlackCount(int count); // test method
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Tue Apr 21 17:29:15 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Mon Apr 27 23:08:57 2015 +0900
@@ -29,9 +29,9 @@
     }
 
     @Override
-    protected Tuple deleteNode() {
+    protected Node deleteNode() {
         EmptyNode emptyNode = new EmptyNode(this.getKey());
-        return new Tuple(emptyNode, false);
+        return emptyNode;
     }
 
     @Override
@@ -64,7 +64,7 @@
     }
 
     @Override
-    public Tuple replaceNode(Node<K, V> parent) {
+    public Node replaceNode(Node<K, V> parent) throws RotateParent {
 
         Node<K, V> newNode = null;
         if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する
@@ -72,11 +72,11 @@
 
         } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる
             newNode = left().createNode(left().getKey(), left().getValue(), left().left(), left().right());
-            return new Tuple(newNode,false);
+            return newNode;
 
         } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる
             newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right());
-            return new Tuple(newNode,false);
+            return newNode;
 
         } else {//子ノードが左右にある場合
             //左の部分木の最大の値を持つNodeと自身を置き換える
@@ -86,17 +86,31 @@
                 cur = cur.right();
             }
 
-            Tuple leftSubTreeNode = null;
+            Node leftSubTreeNode = null;
 
             if (this.left().right().isNotEmpty()) {
-                leftSubTreeNode = this.left().deleteSubTreeMaxNode(null);
-                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.getNode(), this.right());
-                return leftSubTreeNode.getNode().deleteBalance(newNode,leftSubTreeNode.getRebuildFlag());
-
+                try {
+                    leftSubTreeNode = this.left().deleteSubTreeMaxNode(null,Rotate.L);
+                    newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
+                    return newNode;
+                } catch (RotateParent e) {
+                    leftSubTreeNode = e.getParent();
+                    Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
+                    return leftSubTreeNode.deleteBalance(newParent);
+                }
             } else {
-                leftSubTreeNode = this.left().replaceNode(this);
-                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.getNode(), this.right());
-                return leftSubTreeNode.getNode().deleteBalance(newNode,leftSubTreeNode.getRebuildFlag());
+                try {
+                    leftSubTreeNode = this.left().replaceNode(this);
+                    newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
+                    return newNode;
+                } catch (RotateParent e) {
+                    Node node = e.getParent();
+                    //if (parent != null) {
+                    Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
+                    return node.deleteBalance(newParent);
+                    // }
+                    // return node;
+                }
             }
 
         }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Tue Apr 21 17:29:15 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Mon Apr 27 23:08:57 2015 +0900
@@ -49,8 +49,8 @@
     }
 
 
-    public TreeMap<K,V> delete(K key) {
-       Node node = root.delete(key,null).getNode();
+    public TreeMap<K,V> delete(K key) throws RotateParent {
+       Node node = root.delete(key, null,Rotate.N);
         if (node == null)
             return this; // not key
         if (!node.isNotEmpty())
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Tue Apr 21 17:29:15 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Mon Apr 27 23:08:57 2015 +0900
@@ -1,5 +1,6 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.test;
 
+import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.RotateParent;
 import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap;
 
 import java.util.ArrayList;
@@ -11,17 +12,18 @@
  * Created by e115731 on 15/04/04.
  */
 public class TreeMapDelete {
-    public static void main(String args[]) {
+    public static void main(String args[]) throws RotateParent {
         TreeMap<Integer, Integer> map = new TreeMap();
-        for (int count = 1; count < 2000; count++) {
+        for (int count = 1; count < 10000; count++) {
             map = map.put(count, count);
         }
 
         ArrayList<Integer> list = new ArrayList();
-        for (int i = 1; i < 2000; i++) {
+        for (int i = 1; i < 10000; i++) {
             list.add(i);
         }
 
+//        test(map);
         Collections.shuffle(list);
         for (Integer num : list) {
             System.out.println(num);
@@ -29,11 +31,52 @@
             map = newMap;
             map.checkBlackCount();
         }
-        for (Integer num : list) {
-         //   System.out.println(num);
-        }
 
         System.out.println("end");
     }
 
+    public static void test(TreeMap map) throws RotateParent {
+        TreeMap newMap = map.delete(13);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(26);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(5);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(3);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(29);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(8);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(22);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(2);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(20);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(11);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(19);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(6);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(25);
+        map = newMap;
+        map.checkBlackCount();
+        newMap = map.delete(12);
+        map = newMap;
+        map.checkBlackCount();
+    }
 }