Mercurial > hg > Members > tatsuki > TreeMap

changeset 7:6c3147a90b56

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
minner change
author tatsuki
date Mon, 06 Apr 2015 22:35:12 +0900
parents 710680857286
children 97225df15574
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, 165 insertions(+), 48 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Mon Apr 06 14:34:49 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Mon Apr 06 22:35:12 2015 +0900
@@ -19,13 +19,22 @@
     }
 
     @Override
+    protected int checkBlackCount(int count) { // test method
+        count++;
+        left().checkBlackCount(count);
+        right().checkBlackCount(count);
+        count--;
+        return count;
+    }
+
+    @Override
     public Node deleteBalance(Node<K, V> parent) {
         if (rebuildFlag) {
             Rotate editNodeSide;
-            if (0 > (parent.getKey().hashCode() - this.getKey().hashCode()))
-                editNodeSide = Rotate.R;
+            if (0 > (parent.getKey().hashCode() - key.hashCode())) //自身がどちらの子かを調べる
+                editNodeSide = Rotate.R;//右の子
             else
-                editNodeSide = Rotate.L;
+                editNodeSide = Rotate.L;//左の子
 
             DeleteRebuildFlag flag = parent.RebuildDelete(editNodeSide);
 
@@ -44,7 +53,7 @@
             }
         }
         if (0 > (parent.getKey().hashCode() - this.getKey().hashCode()))
-            return parent.createNode(parent.getKey(), parent.getValue(), parent.right(), this);
+            return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
         else
             return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
 
@@ -170,27 +179,40 @@
             //左の部分木の最大の値を持つNodeと自身を置き換える
             Node<K, V> cur = this.left();
 
-            while (cur.right().exitNode()) {
+            while (cur.right().exitNode()) { //左の部分期の最大値を持つNodeを取得する
                 cur = cur.right();
             }
 
             Node<K, V> leftSubTreeNode = new EmptyNode<>();
 
-            if (this.left().right().exitNode()) {
-                leftSubTreeNode = this.left().deleteSubTreeMaxNode(this);
+            if (this.left().right().exitNode()) { //左の部分木が右の子を持っているか
+                leftSubTreeNode = this.left().deleteSubTreeMaxNode(this);//最大値を削除した左の部分木を返す。rootはthisと同じ。
+                Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する
+                newNode = leftSubTreeNode.deleteBalance(newParent);
+
+                return newNode;
+
             } else {
-                leftSubTreeNode = this.left().replaceNode(this);
-                Node newParent = this.createNode(this.left().getKey(),this.left().getValue(),leftSubTreeNode,this.right());
+                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.checkColor()) //置き換えるNodeが黒だったらバランスを取る
-                newNode.setRebuildFlag(true);
-            return newNode;
         }
 
     }
+
+    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) {
+
+        if (!right().right().exitNode()) {
+            Node<K, V> node = right().replaceNode(this).deleteBalance(this); //怪しい地点
+            return node;
+
+        }
+
+        Node<K, V> node = right().deleteSubTreeMaxNode(this);
+        if (parent == null)
+            return node;
+        return node.deleteBalance(parent);
+    }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Mon Apr 06 14:34:49 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Mon Apr 06 22:35:12 2015 +0900
@@ -17,6 +17,17 @@
         super(key, null);
     }
 
+    @Override // 回転処理時にEmptyNodeの子を見ることがあるのでleft rightでEmptyNodeを返すようにする
+    public Node<K, V> left() {
+        return new EmptyNode<>();
+    }
+
+    @Override
+    public Node<K, V> right() {
+        return new EmptyNode<>();
+    }
+
+
     @Override
     protected boolean exitNode() {
         return false;
@@ -106,4 +117,14 @@
         return DeleteRebuildFlag.allBlack;
     }
 
+    @Override
+    protected int checkBlackCount(int count) { // test method
+        System.out.println("blackCount = " + count);
+        return count;
+    }
+
+    @Override
+    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) {
+        return this;
+    }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Mon Apr 06 14:34:49 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Mon Apr 06 22:35:12 2015 +0900
@@ -88,6 +88,7 @@
     public Node<K, V> delete(K key, Node<K, V> 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)
@@ -98,7 +99,6 @@
                 Node node = left.delete(key, this);
                 if (parent == null || node == null)
                     return node;
-
                 return node.deleteBalance(parent);
 
             } else if (result == 0) {
@@ -112,16 +112,7 @@
     }
 
 
-    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) {
-
-        if (!right().right().exitNode()) {
-
-            return right().replaceNode(this);
-
-        }
-
-        return right().deleteSubTreeMaxNode(this).deleteBalance(parent);
-    }
+    public abstract Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) ;
 
     public void setRebuildFlag(boolean flag) {
         this.rebuildFlag = flag;
@@ -138,8 +129,8 @@
 
         } 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();
+            Node<K, V> rightNode = this.deleteBalance(rightSubTreeRoot);
+            Node<K, V> leftNode = parent.left().left();
             return parent.createNode(parent.left().getKey(), parent.left().getValue(), leftNode, rightNode);
 
         }
@@ -173,12 +164,13 @@
 
     protected Node rebuildFour(Node<K, V> parent, Rotate side) { //case 4
         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);
+            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);
 
         } else {
-            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());
+            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);
+
         }
 
     }
@@ -193,7 +185,7 @@
             Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), leftSubTreeRoot, this);
             return this.rebuildsix(newParent, Rotate.R);
 
-        } else {  // rotate Right
+        } 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);
@@ -205,20 +197,22 @@
 
     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> 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());
             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);
+            Node<K, V> rightChild = parent.left().createNode(parent.getKey(), parent.getValue(), parent.left().right(), this);
+            return parent.createNode(parent.left().getKey(), parent.left().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);
@@ -239,4 +233,5 @@
 
     protected abstract Node deleteNode();
 
+    protected abstract int checkBlackCount(int count); // test method
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Mon Apr 06 14:34:49 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Mon Apr 06 22:35:12 2015 +0900
@@ -32,7 +32,7 @@
     public Node deleteBalance(Node<K, V> parent) {
 
         if (0 > (parent.getKey().hashCode() - this.getKey().hashCode()))
-            return createNode(parent.getKey(), parent.getValue(), parent.right(), this);
+            return createNode(parent.getKey(), parent.getValue(), parent.left(), this);
         else
             return createNode(parent.getKey(), parent.getValue(), this, parent.right());
     }
@@ -100,11 +100,11 @@
             return deleteNode();
 
         } else if (this.left().exitNode() && !this.right().exitNode()) { //左の部分木を昇格させる
-            newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right());
+            newNode = left().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());
+            newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right());
             return newNode;
 
         } else {//子ノードが左右にある場合
@@ -119,14 +119,39 @@
 
             if (this.left().right().exitNode()) {
                 leftSubTreeNode = this.left().deleteSubTreeMaxNode(this);
+                newNode = cur.createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.left(), leftSubTreeNode.right());
+                return leftSubTreeNode.deleteBalance(newNode);
+
             } else {
                 leftSubTreeNode = this.left().replaceNode(this);
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.left(), this.right());
+                return leftSubTreeNode.deleteBalance(newNode);
             }
 
+        }
+    }
+
+    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) {
+
+        if (!right().right().exitNode()) {
+            Node<K, V> node = right().replaceNode(this); //怪しい地点
+            if (parent == null)
+                return node;
+            return node;
+
+        }
+
+        Node<K, V> node = right().deleteSubTreeMaxNode(this);
+        if (parent == null)
+            return node;
+        return node.deleteBalance(parent);
+    }
+
 
-            newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, right());
-            return newNode;
-        }
-
+    @Override
+    protected int checkBlackCount(int count) { // test method
+        left().checkBlackCount(count);
+        right().checkBlackCount(count);
+        return count;
     }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Mon Apr 06 14:34:49 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Mon Apr 06 22:35:12 2015 +0900
@@ -58,8 +58,13 @@
         if (node == null)
             return this; // not key
 
+        if (!node.exitNode())
+            return new TreeMap(new EmptyNode<>(),0);
         Node newRoot = new BlackNode(node.getKey(),node.getValue(),node.left(),node.right());
         return new TreeMap(newRoot,0);
     }
 
+    public void checkBlackCount(){
+        root.checkBlackCount(0);
+    }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Mon Apr 06 14:34:49 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Mon Apr 06 22:35:12 2015 +0900
@@ -2,6 +2,8 @@
 
 import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap;
 
+import java.util.ArrayList;
+import java.util.Collections;
 import java.util.Optional;
 import java.util.Random;
 
@@ -11,16 +13,63 @@
 public class TreeMapDelete {
     public static void main(String args[]) {
         TreeMap<Integer, Integer> map = new TreeMap();
-        for (int count = 1; count < 50; count++) {
+        for (int count = 1; count < 15; count++) {
             map = map.put(count, count);
         }
-        for (int count = 1; count < 50; count++) {
-            Random ran = new Random();
-            int num = ran.nextInt(50);
-            TreeMap newMap = map.delete(34);
+
+        ArrayList<Integer> list = new ArrayList();
+        for (int i = 1; i < 15; i++) {
+            list.add(i);
+        }
+
+
+        test(map);
+
+        Collections.shuffle(list);
+        for (Integer num : list) {
+            System.out.println(num);
+            TreeMap newMap = map.delete(num);
             map = newMap;
+            map.checkBlackCount();
+            System.out.println("-----------------------------------");
+        }
+        for (Integer num : list) {
+            System.out.println(num);
         }
 
         System.out.println("end");
     }
+
+    public static void test(TreeMap map) {
+        TreeMap neMap = map.delete(9);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(4);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(5);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(14);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(11);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(3);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(12);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(8);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(2);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(10);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(1);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(13);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(6);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(7);
+        neMap.checkBlackCount();
+
+
+    }
 }