Mercurial > hg > Members > tatsuki > TreeMap

changeset 6:710680857286

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
bag fix rebuildFour
author tatsuki
date Mon, 06 Apr 2015 14:34:49 +0900
parents 6928ef8ba6f0
children 6c3147a90b56
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, 125 insertions(+), 99 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Mon Apr 06 00:09:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Mon Apr 06 14:34:49 2015 +0900
@@ -13,7 +13,8 @@
 
     @Override
     public Node deleteNode() {
-        EmptyNode<K, V> emptyNode = new EmptyNode<K, V>();
+        EmptyNode<K, V> emptyNode = new EmptyNode<K, V>(key);
+        emptyNode.setRebuildFlag(true);
         return emptyNode;
     }
 
@@ -42,11 +43,12 @@
                     return rebuildsix(parent, editNodeSide);
             }
         }
-        return this;
-    }
+        if (0 > (parent.getKey().hashCode() - this.getKey().hashCode()))
+            return parent.createNode(parent.getKey(), parent.getValue(), parent.right(), this);
+        else
+            return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
 
-
-
+    }
 
 
     @Override
@@ -62,7 +64,7 @@
 
     @Override
     Node insBalance() {
-        Rotate spin = left.firstCheckColor(L);
+        Rotate spin = left.checkRotate(L);
 
         if (spin == R) {
             Node<K, V> leftChild = new BlackNode<K, V>(left.left().getKey(), left.left().getValue(), left.left().left(), left.left().right());
@@ -76,7 +78,7 @@
 
         }
 
-        spin = right.firstCheckColor(R);
+        spin = right.checkRotate(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());
@@ -94,12 +96,12 @@
 
 
     @Override
-    Rotate firstCheckColor(Rotate side) {
+    Rotate checkRotate(Rotate side) {
         return N;
     }
 
     @Override
-    boolean secondCheckColor() {
+    boolean checkColor() {
         return false;
     }
 
@@ -107,10 +109,10 @@
     DeleteRebuildFlag RebuildDelete(Rotate side) {
 
         DeleteRebuildFlag flag;
-        if (side == Rotate.R) {
-            flag = this.left().firstChildRebuildDelete(side);
+        if (side == Rotate.R) {//どっち側のNodeを編集したか 右側を編集して来たならRが来る
+            flag = this.left().childRebuildDelete(side);
         } else {
-            flag = this.right().firstChildRebuildDelete(side);
+            flag = this.right().childRebuildDelete(side);
         }
 
         if (flag == DeleteRebuildFlag.allBlack)
@@ -120,56 +122,49 @@
     }
 
     @Override
-    DeleteRebuildFlag firstChildRebuildDelete(Rotate side) {
+    DeleteRebuildFlag childRebuildDelete(Rotate side) {
 
-        boolean rightChild = this.right().secondChildRebuildDelete();
-        boolean leftChild = this.left().secondChildRebuildDelete();
+        boolean rightChild = this.right().checkColor();
+        boolean leftChild = this.left().checkColor();
 
-        if (rightChild && leftChild)
+        if (!rightChild && !leftChild)
             return DeleteRebuildFlag.allBlack;
 
-        if (side == Rotate.R) {
+        if (side == Rotate.R) {//どっち側のNodeを編集したか 右側を編集して来たならRが来る
             if (rightChild)
+                return DeleteRebuildFlag.five;
+            else
                 return DeleteRebuildFlag.six;
-            else
-                return DeleteRebuildFlag.five;
         }
 
         if (side == Rotate.L) {
             if (leftChild)
-                return DeleteRebuildFlag.six;
+                return DeleteRebuildFlag.five;
             else
-                return DeleteRebuildFlag.five;
+                return DeleteRebuildFlag.six;
         }
 
         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つ減るので木のバランスを取る
+            return deleteNode();//黒が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;
+            if (!this.left().checkColor()) //昇格させる木のrootが黒だったらバランスを取る
+                newNode.setRebuildFlag(true);
+            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;
+            if (!this.right().checkColor()) //昇格させる木のrootが黒だったらバランスを取る
+                newNode.setRebuildFlag(true);
+            return newNode;
 
         } else {//子ノードが左右にある場合
             //左の部分木の最大の値を持つNodeと自身を置き換える
@@ -185,14 +180,16 @@
                 leftSubTreeNode = this.left().deleteSubTreeMaxNode(this);
             } else {
                 leftSubTreeNode = this.left().replaceNode(this);
+                Node newParent = this.createNode(this.left().getKey(),this.left().getValue(),leftSubTreeNode,this.right());
+                return leftSubTreeNode.deleteBalance(newParent);
+
             }
 
 
             newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, right());
-            if (cur.secondChildRebuildDelete())
-                return newNode.deleteBalance(parent);
-            else
-                return newNode;
+            if (!cur.checkColor()) //置き換えるNodeが黒だったらバランスを取る
+                newNode.setRebuildFlag(true);
+            return newNode;
         }
 
     }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Mon Apr 06 00:09:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Mon Apr 06 14:34:49 2015 +0900
@@ -13,6 +13,10 @@
         super(null, null);
     }
 
+    public EmptyNode(K key) { //keyは削除時の回転処理に使用する
+        super(key, null);
+    }
+
     @Override
     protected boolean exitNode() {
         return false;
@@ -69,7 +73,12 @@
                     return rebuildsix(parent, editNodeSide);
             }
         }
-        return this;
+
+        if (0 > (parent.getKey().hashCode() - this.getKey().hashCode()))
+            return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
+        else
+            return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
+
     }
 
     @Override
@@ -78,12 +87,12 @@
     }
 
     @Override
-    Rotate firstCheckColor(Rotate side) {
+    Rotate checkRotate(Rotate side) {
         return N;
     }
 
     @Override
-    boolean secondCheckColor() {
+    boolean checkColor() {
         return false;
     }
 
@@ -93,13 +102,8 @@
     }
 
     @Override
-    DeleteRebuildFlag firstChildRebuildDelete(Rotate side) {
+    DeleteRebuildFlag childRebuildDelete(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 Apr 06 00:09:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Mon Apr 06 14:34:49 2015 +0900
@@ -55,6 +55,10 @@
         return right;
     }
 
+    public boolean getRebuildFlag() {
+        return rebuildFlag;
+    }
+
     public K getKey() {
         return key;
     }
@@ -82,26 +86,32 @@
     }
 
     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);
+        if (this.exitNode()) {
+            int result = key.hashCode() - this.key.hashCode();
+            if (result > 0) {
+                Node<K, V> node = right.delete(key, this);
+                if (parent == null || node == null)
+                    return 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) {
+                Node node = left.delete(key, this);
+                if (parent == null || node == null)
+                    return node;
+
+                return node.deleteBalance(parent);
 
-        } else if (result == 0) {
-            return replaceNode(parent).deleteBalance(parent); // equals
+            } else if (result == 0) {
+                Node node = replaceNode(parent); // equals
+                if (parent == null || node == null)
+                    return node;
+                return node.deleteBalance(parent);
+            }
         }
-
-        return this; //not found key
+        return null; // no key
     }
 
 
-
     public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) {
 
         if (!right().right().exitNode()) {
@@ -119,9 +129,9 @@
     }
 
 
-    protected Node<K,V> rebuildTwo(Node<K, V> parent, Rotate side) { // case2
+    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> leftSubTreeRoot = parent.right().createNode(parent.getKey(), parent.getValue(), this, parent.right().left()); // check
             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);
@@ -138,13 +148,22 @@
 
     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> rightNode;
+            if (parent.right().exitNode())
+                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);
             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);
+
+        } else {
+            Node<K, V> leftNode;
+            if (parent.left().exitNode())
+                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);
             newParent.setRebuildFlag(true);
             return newParent;
 
@@ -153,13 +172,13 @@
     }
 
     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);
+        if (side == Rotate.R) {
+            Node<K, V> rightNode = new RedNode<K, V>(this.getKey(), this.getValue(), this.left(), this.right());
+            return new BlackNode<K, V>(parent.getKey(), parent.getValue(), parent.left(), 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);
+            Node<K, V> leftNode = new RedNode<K, V>(this.getKey(), this.getValue(), this.left(), this.right()); // ok
+            return new BlackNode<K, V>(parent.getKey(), parent.getValue(), leftNode, parent.right());
         }
 
     }
@@ -208,17 +227,15 @@
 
     public abstract Node deleteBalance(Node<K, V> Parent);
 
-    abstract Rotate firstCheckColor(Rotate side);
+    abstract Rotate checkRotate(Rotate side);
 
-    abstract boolean secondCheckColor();
+    abstract boolean checkColor();
 
     abstract DeleteRebuildFlag RebuildDelete(Rotate side);
 
-    abstract DeleteRebuildFlag firstChildRebuildDelete(Rotate side);
+    abstract DeleteRebuildFlag childRebuildDelete(Rotate side);
 
-    abstract boolean secondChildRebuildDelete();
-
-    public abstract Node replaceNode(Node<K, V> parent) ;
+    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 Apr 06 00:09:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Mon Apr 06 14:34:49 2015 +0900
@@ -29,32 +29,36 @@
     }
 
     @Override
-    public Node deleteBalance(Node<K, V> parent) { // not use method
-        return this;
+    public Node deleteBalance(Node<K, V> parent) {
+
+        if (0 > (parent.getKey().hashCode() - this.getKey().hashCode()))
+            return createNode(parent.getKey(), parent.getValue(), parent.right(), this);
+        else
+            return createNode(parent.getKey(), parent.getValue(), this, parent.right());
     }
 
     @Override
     protected Node deleteNode() {
-        return new EmptyNode();
+        return new EmptyNode(this.getKey());
     }
 
     @Override
-    Rotate firstCheckColor(Rotate side) {
+    Rotate checkRotate(Rotate side) {
 
         if (side == L) {
-            if (left.secondCheckColor())
+            if (left.checkColor())
                 return R;
 
-            else if (right.secondCheckColor())
+            else if (right.checkColor())
                 return LR;
 
             return N;
         } else {
 
-            if (left.secondCheckColor())
+            if (left.checkColor())
                 return RL;
 
-            else if (right.secondCheckColor())
+            else if (right.checkColor())
                 return L;
 
             return N;
@@ -63,7 +67,7 @@
     }
 
     @Override
-    boolean secondCheckColor() {
+    boolean checkColor() {
         return true;
     }
 
@@ -72,9 +76,9 @@
 
         DeleteRebuildFlag flag;
         if (side == Rotate.R) {
-            flag = this.left().firstChildRebuildDelete(side);
+            flag = this.left().childRebuildDelete(side);
         } else {
-            flag = this.right().firstChildRebuildDelete(side);
+            flag = this.right().childRebuildDelete(side);
         }
 
         if (flag == DeleteRebuildFlag.allBlack)
@@ -84,16 +88,11 @@
     }
 
     @Override
-    DeleteRebuildFlag firstChildRebuildDelete(Rotate side) {
+    DeleteRebuildFlag childRebuildDelete(Rotate side) {
         return DeleteRebuildFlag.two;
     }
 
     @Override
-    boolean secondChildRebuildDelete() {
-        return false;
-    }
-
-    @Override
     public Node replaceNode(Node<K, V> parent) {
 
         Node<K, V> newNode = null;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Mon Apr 06 00:09:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Mon Apr 06 14:34:49 2015 +0900
@@ -54,6 +54,10 @@
 
     public TreeMap<K,V> delete(K key) {
        Node node = root.delete(key,null);
+
+        if (node == null)
+            return this; // not key
+
         Node newRoot = new BlackNode(node.getKey(),node.getValue(),node.left(),node.right());
         return new TreeMap(newRoot,0);
     }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Mon Apr 06 00:09:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Mon Apr 06 14:34:49 2015 +0900
@@ -3,6 +3,7 @@
 import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap;
 
 import java.util.Optional;
+import java.util.Random;
 
 /**
  * Created by e115731 on 15/04/04.
@@ -10,11 +11,15 @@
 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);
+        for (int count = 1; count < 50; count++) {
             map = map.put(count, count);
         }
-        TreeMap<Integer, Integer> deleteMap = map.delete(13);
+        for (int count = 1; count < 50; count++) {
+            Random ran = new Random();
+            int num = ran.nextInt(50);
+            TreeMap newMap = map.delete(34);
+            map = newMap;
+        }
 
         System.out.println("end");
     }