Mercurial > hg > Members > tatsuki > TreeMap

changeset 8:97225df15574

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
delete bag fix
author tatsuki
date Tue, 07 Apr 2015 00:05:06 +0900
parents 6c3147a90b56
children 5da70bcfb824
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, 52 insertions(+), 61 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Mon Apr 06 22:35:12 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Tue Apr 07 00:05:06 2015 +0900
@@ -183,18 +183,17 @@
                 cur = cur.right();
             }
 
-            Node<K, V> leftSubTreeNode = new EmptyNode<>();
 
             if (this.left().right().exitNode()) { //左の部分木が右の子を持っているか
-                leftSubTreeNode = this.left().deleteSubTreeMaxNode(this);//最大値を削除した左の部分木を返す。rootはthisと同じ。
+                Node<K, V> leftSubTreeNode = this.left().deleteSubTreeMaxNode(null);//最大値を削除した左の部分木を返す。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());
+                Node<K, V> leftSubTreeNode = this.left().replaceNode(this);//右の子がいなかった場合、左の子を昇格させるだけで良い。
+                Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
                 return leftSubTreeNode.deleteBalance(newParent);
 
             }
@@ -202,17 +201,4 @@
 
     }
 
-    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 22:35:12 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Tue Apr 07 00:05:06 2015 +0900
@@ -123,8 +123,4 @@
         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 22:35:12 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Tue Apr 07 00:05:06 2015 +0900
@@ -112,7 +112,24 @@
     }
 
 
-    public abstract Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) ;
+    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) {
+
+        Node<K, V> node;
+        if (right().exitNode()) {//最大値のノードが取得できるまで潜る
+            node = right().deleteSubTreeMaxNode(this);
+            if (parent == null)
+                return node;
+            return node.deleteBalance(parent);
+
+        }
+
+
+        node = this.replaceNode(parent); //怪しい地点
+        if (parent == null)
+            return node;
+        return node.deleteBalance(parent);
+
+    }
 
     public void setRebuildFlag(boolean flag) {
         this.rebuildFlag = flag;
@@ -211,8 +228,6 @@
     }
 
 
-
-
     protected abstract boolean exitNode();
 
     public abstract Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Mon Apr 06 22:35:12 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Tue Apr 07 00:05:06 2015 +0900
@@ -32,9 +32,9 @@
     public Node deleteBalance(Node<K, V> parent) {
 
         if (0 > (parent.getKey().hashCode() - this.getKey().hashCode()))
-            return createNode(parent.getKey(), parent.getValue(), parent.left(), this);
+            return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
         else
-            return createNode(parent.getKey(), parent.getValue(), this, parent.right());
+            return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
     }
 
     @Override
@@ -118,35 +118,19 @@
             Node<K, V> leftSubTreeNode = new EmptyNode<>();
 
             if (this.left().right().exitNode()) {
-                leftSubTreeNode = this.left().deleteSubTreeMaxNode(this);
-                newNode = cur.createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.left(), leftSubTreeNode.right());
+                leftSubTreeNode = this.left().deleteSubTreeMaxNode(null);
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
                 return leftSubTreeNode.deleteBalance(newNode);
 
             } else {
                 leftSubTreeNode = this.left().replaceNode(this);
-                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.left(), this.right());
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, 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);
-    }
-
 
     @Override
     protected int checkBlackCount(int count) { // test method
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Mon Apr 06 22:35:12 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Tue Apr 07 00:05:06 2015 +0900
@@ -66,5 +66,6 @@
 
     public void checkBlackCount(){
         root.checkBlackCount(0);
+        System.out.println("-----------------------------------");
     }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Mon Apr 06 22:35:12 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Tue Apr 07 00:05:06 2015 +0900
@@ -13,17 +13,17 @@
 public class TreeMapDelete {
     public static void main(String args[]) {
         TreeMap<Integer, Integer> map = new TreeMap();
-        for (int count = 1; count < 15; count++) {
+        for (int count = 1; count < 200; count++) {
             map = map.put(count, count);
         }
 
         ArrayList<Integer> list = new ArrayList();
-        for (int i = 1; i < 15; i++) {
+        for (int i = 1; i < 200; i++) {
             list.add(i);
         }
 
 
-        test(map);
+       // test(map);
 
         Collections.shuffle(list);
         for (Integer num : list) {
@@ -31,7 +31,6 @@
             TreeMap newMap = map.delete(num);
             map = newMap;
             map.checkBlackCount();
-            System.out.println("-----------------------------------");
         }
         for (Integer num : list) {
             System.out.println(num);
@@ -41,33 +40,43 @@
     }
 
     public static void test(TreeMap map) {
-        TreeMap neMap = map.delete(9);
+        TreeMap neMap = map.delete(11);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(2);
         neMap.checkBlackCount();
-        neMap = neMap.delete(4);
+        neMap = neMap.delete(8);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(6);
         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 = neMap.delete(16);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(13);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(17);
         neMap.checkBlackCount();
-        neMap = neMap.delete(2);
+        neMap = neMap.delete(19);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(4);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(7);
+        neMap.checkBlackCount();
+        neMap = neMap.delete(1);
         neMap.checkBlackCount();
         neMap = neMap.delete(10);
         neMap.checkBlackCount();
-        neMap = neMap.delete(1);
+        neMap = neMap.delete(14);
         neMap.checkBlackCount();
-        neMap = neMap.delete(13);
+        neMap = neMap.delete(9);
         neMap.checkBlackCount();
-        neMap = neMap.delete(6);
+        neMap = neMap.delete(15);
         neMap.checkBlackCount();
-        neMap = neMap.delete(7);
+        neMap = neMap.delete(18);
         neMap.checkBlackCount();