Mercurial > hg > Members > tatsuki > TreeMap

changeset 5:6928ef8ba6f0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement delete
author tatsuki
date Mon, 06 Apr 2015 00:09:38 +0900
parents 3de906fb90d1
children 710680857286
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/DeleteRebuildFlag.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 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/Util.java
diffstat 8 files changed, 475 insertions(+), 57 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Mon Mar 30 12:58:27 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Mon Apr 06 00:09:38 2015 +0900
@@ -10,54 +10,89 @@
         super(key, value, left, right);
     }
 
+
     @Override
-    public Node clone() {
-        return new BlackNode<K, V>(key, value, left, right);
+    public Node deleteNode() {
+        EmptyNode<K, V> emptyNode = new EmptyNode<K, V>();
+        return emptyNode;
     }
 
     @Override
+    public Node deleteBalance(Node<K, V> parent) {
+        if (rebuildFlag) {
+            Rotate editNodeSide;
+            if (0 > (parent.getKey().hashCode() - this.getKey().hashCode()))
+                editNodeSide = Rotate.R;
+            else
+                editNodeSide = Rotate.L;
+
+            DeleteRebuildFlag flag = parent.RebuildDelete(editNodeSide);
+
+
+            switch (flag) {
+                case two:
+                    return rebuildTwo(parent, editNodeSide);
+                case three:
+                    return rebuildThree(parent, editNodeSide);
+                case four:
+                    return rebuildFour(parent, editNodeSide);
+                case five:
+                    return rebuildfive(parent, editNodeSide);
+                case six:
+                    return rebuildsix(parent, editNodeSide);
+            }
+        }
+        return this;
+    }
+
+
+
+
+
+    @Override
     protected boolean exitNode() {
         return true;
     }
 
     @Override
-    public Node<K,V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) {
+    public Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) {
         return new BlackNode<K, V>(key, value, left, right);
     }
 
 
     @Override
-    Node balance() {
+    Node insBalance() {
         Rotate spin = left.firstCheckColor(L);
 
         if (spin == R) {
-            Node<K, V> leftChild = new BlackNode<K,V>(left.left().getKey(), left.left().getValue(), left.left().left(), left.left().right());
-            Node<K,V> rightChild = new BlackNode<K,V>(getKey(), getValue(), left.right(), right);
-            return new RedNode<K,V>(left.getKey(), left.getValue(), leftChild, rightChild);
+            Node<K, V> leftChild = new BlackNode<K, V>(left.left().getKey(), left.left().getValue(), left.left().left(), left.left().right());
+            Node<K, V> rightChild = new BlackNode<K, V>(getKey(), getValue(), left.right(), right);
+            return new RedNode<K, V>(left.getKey(), left.getValue(), leftChild, rightChild);
 
         } else if (spin == LR) {
-            Node<K,V> leftChild = new BlackNode<K,V>(left.getKey(), left.getValue(), left.left(), left.right().left());
-            Node<K,V> rightChild = new BlackNode<K,V>(getKey(), getValue(), left.right().right(), right);
-            return new RedNode<K,V>(left.right().getKey(), left.right().getValue(), leftChild, rightChild);
+            Node<K, V> leftChild = new BlackNode<K, V>(left.getKey(), left.getValue(), left.left(), left.right().left());
+            Node<K, V> rightChild = new BlackNode<K, V>(getKey(), getValue(), left.right().right(), right);
+            return new RedNode<K, V>(left.right().getKey(), left.right().getValue(), leftChild, rightChild);
 
         }
 
         spin = right.firstCheckColor(R);
         if (spin == L) {
-            Node<K, V> leftChild = new BlackNode<K,V>(getKey(), getValue(), left, right.left());
-            Node<K, V> rightChild = new BlackNode<K,V>(right.right().getKey(), (V) right.right().getValue(), right.right().left(), right.right().right());
-            return new RedNode<K,V>(right.getKey(), right.getValue(), leftChild, rightChild);
+            Node<K, V> leftChild = new BlackNode<K, V>(getKey(), getValue(), left, right.left());
+            Node<K, V> rightChild = new BlackNode<K, V>(right.right().getKey(), (V) right.right().getValue(), right.right().left(), right.right().right());
+            return new RedNode<K, V>(right.getKey(), right.getValue(), leftChild, rightChild);
 
         } else if (spin == RL) {
-            Node<K, V> leftChild = new BlackNode<K,V>(getKey(), getValue(), left, right.left().left());
-            Node<K, V> rightChild = new BlackNode<K,V>(right.getKey(), right.getValue(), right.left().right(), right.right());
-            return new RedNode<K,V>(right.left().getKey(), right.left().getValue(), leftChild, rightChild);
+            Node leftChild = new BlackNode(getKey(), getValue(), left, right.left().left());
+            Node rightChild = new BlackNode(right.getKey(), right.getValue(), right.left().right(), right.right());
+            return new RedNode(right.left().getKey(), right.left().getValue(), leftChild, rightChild);
 
         }
 
         return this;
     }
 
+
     @Override
     Rotate firstCheckColor(Rotate side) {
         return N;
@@ -67,4 +102,98 @@
     boolean secondCheckColor() {
         return false;
     }
+
+    @Override
+    DeleteRebuildFlag RebuildDelete(Rotate side) {
+
+        DeleteRebuildFlag flag;
+        if (side == Rotate.R) {
+            flag = this.left().firstChildRebuildDelete(side);
+        } else {
+            flag = this.right().firstChildRebuildDelete(side);
+        }
+
+        if (flag == DeleteRebuildFlag.allBlack)
+            return DeleteRebuildFlag.three;
+
+        return flag;
+    }
+
+    @Override
+    DeleteRebuildFlag firstChildRebuildDelete(Rotate side) {
+
+        boolean rightChild = this.right().secondChildRebuildDelete();
+        boolean leftChild = this.left().secondChildRebuildDelete();
+
+        if (rightChild && leftChild)
+            return DeleteRebuildFlag.allBlack;
+
+        if (side == Rotate.R) {
+            if (rightChild)
+                return DeleteRebuildFlag.six;
+            else
+                return DeleteRebuildFlag.five;
+        }
+
+        if (side == Rotate.L) {
+            if (leftChild)
+                return DeleteRebuildFlag.six;
+            else
+                return DeleteRebuildFlag.five;
+        }
+
+        return null;
+    }
+
+    @Override
+    boolean secondChildRebuildDelete() {
+        return true;
+    }
+
+    @Override
+    public Node replaceNode(Node<K, V> parent) {
+
+        Node<K, V> newNode = null;
+        if (!this.left().exitNode() && !this.right().exitNode()) { //自身を削除する
+            return deleteNode().deleteBalance(parent);//黒が1つ減るので木のバランスを取る
+
+        } else if (this.left().exitNode() && !this.right().exitNode()) { //左の部分木を昇格させる
+            newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right());
+            if (this.left().secondChildRebuildDelete())
+                return newNode.deleteBalance(parent);
+            else
+                return newNode;
+
+        } else if (!this.left().exitNode() && this.right().exitNode()) { //右の部分木を昇格させる
+            newNode = createNode(right().getKey(), right().getValue(), right().left(), right().right());
+            if (this.right().secondChildRebuildDelete())
+                return newNode.deleteBalance(parent);
+            else
+                return newNode;
+
+        } else {//子ノードが左右にある場合
+            //左の部分木の最大の値を持つNodeと自身を置き換える
+            Node<K, V> cur = this.left();
+
+            while (cur.right().exitNode()) {
+                cur = cur.right();
+            }
+
+            Node<K, V> leftSubTreeNode = new EmptyNode<>();
+
+            if (this.left().right().exitNode()) {
+                leftSubTreeNode = this.left().deleteSubTreeMaxNode(this);
+            } else {
+                leftSubTreeNode = this.left().replaceNode(this);
+            }
+
+
+            newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, right());
+            if (cur.secondChildRebuildDelete())
+                return newNode.deleteBalance(parent);
+            else
+                return newNode;
+        }
+
+    }
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/DeleteRebuildFlag.java	Mon Apr 06 00:09:38 2015 +0900
@@ -0,0 +1,8 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
+
+/**
+ * Created by e115731 on 15/04/05.
+ */
+public enum DeleteRebuildFlag {
+    one,two,three,four,five,six,allBlack
+}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Mon Mar 30 12:58:27 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Mon Apr 06 00:09:38 2015 +0900
@@ -18,28 +18,62 @@
         return false;
     }
 
-    @Override
-    public Node<K, V> clone() {
-        return new EmptyNode<K, V>();
-    }
 
     @Override
     public Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) {
         return new RedNode<K, V>(key, value, new EmptyNode<K, V>(), new EmptyNode<K, V>());
     }
 
-    @Override
-    public Node<K, V> put(Comparable<? super K> k, V value) {
+
+    public Node<K, V> put(K k, V value) {
         return new RedNode(k, value, new EmptyNode<K, V>(), new EmptyNode<K, V>());
     }
 
     @Override
-    Node balance() {
-        return clone();
+    public Node replaceNode(Node<K, V> parent) { // not use method
+        return this;
+    }
+
+    @Override
+    protected Node deleteNode() { //not use method
+        return this;
+    }
+
+    @Override
+    Node insBalance() {
+        return this;
     }
 
     @Override
-    public Optional<V> get(Comparable<? super K> key) {
+    public Node deleteBalance(Node<K, V> parent) {
+        if (rebuildFlag) {
+            Rotate editNodeSide;
+            if (0 > (parent.getKey().hashCode() - this.getKey().hashCode()))
+                editNodeSide = Rotate.R;
+            else
+                editNodeSide = Rotate.L;
+
+            DeleteRebuildFlag flag = parent.RebuildDelete(editNodeSide);
+
+
+            switch (flag) {
+                case two:
+                    return rebuildTwo(parent, editNodeSide);
+                case three:
+                    return rebuildThree(parent, editNodeSide);
+                case four:
+                    return rebuildFour(parent, editNodeSide);
+                case five:
+                    return rebuildfive(parent, editNodeSide);
+                case six:
+                    return rebuildsix(parent, editNodeSide);
+            }
+        }
+        return this;
+    }
+
+    @Override
+    public Optional<V> get(K key) {
         return Optional.ofNullable((V) getValue());
     }
 
@@ -52,4 +86,20 @@
     boolean secondCheckColor() {
         return false;
     }
+
+    @Override
+    DeleteRebuildFlag RebuildDelete(Rotate side) { //not use method
+        return null;
+    }
+
+    @Override
+    DeleteRebuildFlag firstChildRebuildDelete(Rotate side) {
+        return DeleteRebuildFlag.allBlack;
+    }
+
+    @Override
+    boolean secondChildRebuildDelete() {
+        return true;
+    }
+
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Mon Mar 30 12:58:27 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Mon Apr 06 00:09:38 2015 +0900
@@ -11,6 +11,7 @@
     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;
@@ -29,12 +30,12 @@
     }
 
 
-    public Optional<V> get(Comparable<? super K> key) {
+    public Optional<V> get(K key) {
 
         Node<K, V> cur = this;
 
         while (cur.exitNode()) {
-            int result = key.compareTo(cur.getKey());
+            int result = key.hashCode() - cur.getKey().hashCode();
 
             if (result > 0)
                 cur = cur.right();
@@ -63,33 +64,162 @@
     }
 
 
-    public Node<K, V> put(Comparable<? super K> k, V value) {
+    public Node<K, V> put(K k, V value) {
 
-        int result = k.compareTo(this.key);
+        int result = k.hashCode() - this.key.hashCode();
 
         if (result > 0) {
             Node<K, V> node = right.put(k, value);
             node = createNode(key, this.value, left, node);
-            return node.balance();
+            return node.insBalance();
         } else if (result < 0) {
             Node node = left.put(k, value);
-            return createNode(key, this.value, node, right).balance();
+            return createNode(key, this.value, node, right).insBalance();
         }
 
         return createNode(key, value, left, right); // equals
 
     }
 
-    public abstract Node clone();
+    public Node<K, V> delete(K key, Node<K, V> parent) {
+        int result = key.hashCode() - this.key.hashCode();
+
+        if (result > 0) {
+            Node<K, V> node = right.delete(key, this);
+            node = createNode(getKey(), getValue(), left, node);
+            return node.deleteBalance(parent);
+
+        } else if (result < 0) {
+            Node node = left.delete(key, this);
+            return createNode(getKey(), getValue(), node, right).deleteBalance(parent);
+
+        } else if (result == 0) {
+            return replaceNode(parent).deleteBalance(parent); // equals
+        }
+
+        return this; //not found key
+    }
+
+
+
+    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) {
+
+        if (!right().right().exitNode()) {
+
+            return right().replaceNode(this);
+
+        }
+
+        return right().deleteSubTreeMaxNode(this).deleteBalance(parent);
+    }
+
+    public void setRebuildFlag(boolean flag) {
+        this.rebuildFlag = flag;
+
+    }
+
+
+    protected Node<K,V> rebuildTwo(Node<K, V> parent, Rotate side) { // case2
+        if (side == Rotate.L) { // rotate Left
+            Node<K, V> leftSubTreeRoot = parent.right().createNode(parent.getKey(), parent.getValue(), this, parent.right().left());
+            Node<K, V> leftNode = this.deleteBalance(leftSubTreeRoot);
+            Node<K, V> rightNode = parent.right().right();
+            return parent.createNode(parent.right().getKey(), parent.right().getValue(), leftNode, rightNode);
+
+        } else {  // rotate Right
+            Node<K, V> rightSubTreeRoot = parent.left().createNode(parent.getKey(), parent.getValue(), parent.left().right(), this);
+            Node<K, V> leftNode = this.deleteBalance(rightSubTreeRoot);
+            Node<K, V> rightNode = parent.left().left();
+            return parent.createNode(parent.left().getKey(), parent.left().getValue(), leftNode, rightNode);
+
+        }
+
+    }
+
+    protected Node rebuildThree(Node<K, V> parent, Rotate side) { // case3 再起
+        if (side == Rotate.L) {
+            Node<K, V> rightNode = new BlackNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right());
+            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightNode);
+            newParent.setRebuildFlag(true);
+            return newParent;
+        } else {  // rotate Right
+            Node<K, V> rightNode = new BlackNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right());
+            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightNode);
+            newParent.setRebuildFlag(true);
+            return newParent;
+
+        }
+
+    }
+
+    protected Node rebuildFour(Node<K, V> parent, Rotate side) { //case 4
+        if (side == Rotate.L) {
+            Node<K, V> rightNode = new RedNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right());
+            return new BlackNode<K, V>(parent.getKey(), parent.getValue(), this, rightNode);
+
+        } else {
+            Node<K, V> leftNode = new RedNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right());
+            return new BlackNode<K, V>(parent.getKey(), parent.getValue(), leftNode, this);
+        }
+
+    }
+
+    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();
+            Node<K, V> leftSubTreeRoot = new BlackNode<K, V>(parent.left().right().getKey(), parent.left().right().getValue(), leftChild, rightChild);
+            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), leftSubTreeRoot, this);
+            return this.rebuildsix(newParent, Rotate.R);
+
+        } else {  // rotate Right
+            Node<K, V> leftChild = parent.right().left().left();
+            Node<K, V> rightChild = new RedNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left().right(), parent.right().right());
+            Node<K, V> rightSubTreeRoot = new BlackNode<K, V>(parent.right().left().getKey(), parent.right().left().getValue(), leftChild, rightChild);
+            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightSubTreeRoot);
+            return this.rebuildsix(newParent, Rotate.L);
+
+        }
+    }
+
+    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());
+            Node<K, V> rightChild = new BlackNode<K, V>(parent.right().right().getKey(), parent.right().right().getValue(), parent.right().right().left(), parent.right().right().right());
+            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(), this, parent.right().left());
+            return parent.createNode(parent.right().getKey(), parent.right().getValue(), leftChild, rightChild);
+
+        }
+
+    }
 
 
     protected abstract boolean exitNode();
 
     public abstract Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right);
 
-    abstract Node<K, V> balance();
+    abstract Node<K, V> insBalance();
+
+    public abstract Node deleteBalance(Node<K, V> Parent);
 
     abstract Rotate firstCheckColor(Rotate side);
 
     abstract boolean secondCheckColor();
+
+    abstract DeleteRebuildFlag RebuildDelete(Rotate side);
+
+    abstract DeleteRebuildFlag firstChildRebuildDelete(Rotate side);
+
+    abstract boolean secondChildRebuildDelete();
+
+    public abstract Node replaceNode(Node<K, V> parent) ;
+
+    protected abstract Node deleteNode();
+
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Mon Mar 30 12:58:27 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Mon Apr 06 00:09:38 2015 +0900
@@ -14,26 +14,31 @@
 
 
     @Override
-    public Node<K,V> clone() {
-        return new RedNode<K,V>(key, value, left, right);
-    }
-
-    @Override
     protected boolean exitNode() {
         return true;
     }
 
     @Override
-    public Node<K,V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) {
-        return new RedNode<K,V>(key, value, left, right);
+    public Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) {
+        return new RedNode<K, V>(key, value, left, right);
     }
 
     @Override
-    protected Node<K,V> balance() {
+    protected Node<K, V> insBalance() {
         return this;
     }
 
     @Override
+    public Node deleteBalance(Node<K, V> parent) { // not use method
+        return this;
+    }
+
+    @Override
+    protected Node deleteNode() {
+        return new EmptyNode();
+    }
+
+    @Override
     Rotate firstCheckColor(Rotate side) {
 
         if (side == L) {
@@ -62,5 +67,67 @@
         return true;
     }
 
+    @Override
+    DeleteRebuildFlag RebuildDelete(Rotate side) {
 
+        DeleteRebuildFlag flag;
+        if (side == Rotate.R) {
+            flag = this.left().firstChildRebuildDelete(side);
+        } else {
+            flag = this.right().firstChildRebuildDelete(side);
+        }
+
+        if (flag == DeleteRebuildFlag.allBlack)
+            return DeleteRebuildFlag.four;
+
+        return flag;
+    }
+
+    @Override
+    DeleteRebuildFlag firstChildRebuildDelete(Rotate side) {
+        return DeleteRebuildFlag.two;
+    }
+
+    @Override
+    boolean secondChildRebuildDelete() {
+        return false;
+    }
+
+    @Override
+    public Node replaceNode(Node<K, V> parent) {
+
+        Node<K, V> newNode = null;
+        if (!this.left().exitNode() && !this.right().exitNode()) { //自身を削除する
+            return deleteNode();
+
+        } else if (this.left().exitNode() && !this.right().exitNode()) { //左の部分木を昇格させる
+            newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right());
+            return newNode;
+
+        } else if (!this.left().exitNode() && this.right().exitNode()) { //右の部分木を昇格させる
+            newNode = createNode(right().getKey(), right().getValue(), right().left(), right().right());
+            return newNode;
+
+        } else {//子ノードが左右にある場合
+            //左の部分木の最大の値を持つNodeと自身を置き換える
+            Node<K, V> cur = this.left();
+
+            while (cur.right().exitNode()) {
+                cur = cur.right();
+            }
+
+            Node<K, V> leftSubTreeNode = new EmptyNode<>();
+
+            if (this.left().right().exitNode()) {
+                leftSubTreeNode = this.left().deleteSubTreeMaxNode(this);
+            } else {
+                leftSubTreeNode = this.left().replaceNode(this);
+            }
+
+
+            newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, right());
+            return newNode;
+        }
+
+    }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Mon Mar 30 12:58:27 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Mon Apr 06 00:09:38 2015 +0900
@@ -29,7 +29,7 @@
     }
 
     public Optional<V> get(K key) {
-        return root.get((Comparable<? super K>) key);
+        return root.get(key);
     }
 
     public TreeMap put(K key, V value) {
@@ -42,7 +42,7 @@
             return new TreeMap<K, V>(newRoot, size++);
         }
 
-        Node<K, V> newEntry = root.put((Comparable<? super K>) key, value);
+        Node<K, V> newEntry = root.put(key, value);
         Node<K, V> newRoot = new BlackNode(newEntry.getKey(), newEntry.getValue(), newEntry.left(), newEntry.right());
         return new TreeMap(newRoot, 0);
     }
@@ -52,19 +52,10 @@
         return root == null;
     }
 
-    public Iterator<K> keys() {
-
-        return new Iterator<K>() {
+    public TreeMap<K,V> delete(K key) {
+       Node node = root.delete(key,null);
+        Node newRoot = new BlackNode(node.getKey(),node.getValue(),node.left(),node.right());
+        return new TreeMap(newRoot,0);
+    }
 
-            @Override
-            public boolean hasNext() {
-                return false;
-            }
-
-            @Override
-            public K next() {
-                return null;
-            }
-        };
-    }
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Mon Apr 06 00:09:38 2015 +0900
@@ -0,0 +1,21 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.test;
+
+import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap;
+
+import java.util.Optional;
+
+/**
+ * Created by e115731 on 15/04/04.
+ */
+public class TreeMapDelete {
+    public static void main(String args[]) {
+        TreeMap<Integer, Integer> map = new TreeMap();
+        for (int count = 1; count < 15; count = count + 2) {
+            map = map.put(count + 1, count + 1);
+            map = map.put(count, count);
+        }
+        TreeMap<Integer, Integer> deleteMap = map.delete(13);
+
+        System.out.println("end");
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/Util.java	Mon Apr 06 00:09:38 2015 +0900
@@ -0,0 +1,22 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.test;
+
+import java.util.TreeMap;
+
+/**
+ * Created by e115731 on 15/04/03.
+ */
+public class Util {
+    public static void main(String args[]) {
+        TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
+        map.put(6, 6);
+        map.put(5, 5);
+        map.put(4, 4);
+        map.put(3, 3);
+        map.put(2, 2);
+        map.put(1, 1);
+        map.get(1);
+        map.remove(6);
+        map.get(1);
+        System.out.println("test");
+    }
+}