Mercurial > hg > Members > tatsuki > TreeMap

changeset 13:b6739b88edeb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
create Tuple<Node,rebuildFlag>
author tatsuki
date Sat, 18 Apr 2015 12:01:41 +0900
parents 73e915f29b42
children 0c126652d4b1
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
diffstat 5 files changed, 138 insertions(+), 89 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Fri Apr 17 19:06:00 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Sat Apr 18 12:01:41 2015 +0900
@@ -12,10 +12,9 @@
 
 
     @Override
-    public Node deleteNode() {
+    public Tuple deleteNode() {
         EmptyNode<K, V> emptyNode = new EmptyNode<K, V>(key);
-        emptyNode.setRebuildFlag(true);
-        return emptyNode;
+        return new Tuple(emptyNode, true);
     }
 
     @Override
@@ -28,7 +27,6 @@
     }
 
 
-
     @Override
     protected boolean isNotEmpty() {
         return true;
@@ -84,13 +82,12 @@
     }
 
 
-
     /**
      * @param parent
      * @return
      */
     @Override
-    public Node replaceNode(Node<K, V> parent) {
+    public Tuple replaceNode(Node<K, V> parent) {
 
         Node<K, V> newNode = null;
         if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する
@@ -98,15 +95,16 @@
 
         } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる
             newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right());
+
             if (!this.left().isRed()) //昇格させる木のrootが黒だったらバランスを取る
-                newNode.setRebuildFlag(true);
-            return newNode;
+                return new Tuple(newNode, true);
+            return new Tuple(newNode, false);
 
         } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる
             newNode = createNode(right().getKey(), right().getValue(), right().left(), right().right());
             if (!this.right().isRed()) //昇格させる木のrootが黒だったらバランスを取る
-                newNode.setRebuildFlag(true);
-            return newNode;
+                return new Tuple(newNode, true);
+            return new Tuple(newNode, false);
 
         } else {//子ノードが左右にある場合
             //左の部分木の最大の値を持つNodeと自身を置き換える
@@ -118,16 +116,15 @@
 
 
             if (this.left().right().isNotEmpty()) { //左の部分木が右の子を持っているか
-                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);
+                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());
 
-                return newNode;
 
             } else {
-                Node<K, V> leftSubTreeNode = this.left().replaceNode(this);//右の子がいなかった場合、左の子を昇格させるだけで良い。
-                Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
-                return leftSubTreeNode.deleteBalance(newParent);
+                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());
 
             }
         }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Fri Apr 17 19:06:00 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Sat Apr 18 12:01:41 2015 +0900
@@ -45,13 +45,13 @@
     }
 
     @Override
-    public Node replaceNode(Node<K, V> parent) { // not use method
-        return this;
+    public Tuple replaceNode(Node<K, V> parent) { // not use method
+        return new Tuple(this, false);
     }
 
     @Override
-    protected Node deleteNode() { //not use method
-        return this;
+    protected Tuple deleteNode() { //not use method
+        return new Tuple(this, false);
     }
 
     @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Fri Apr 17 19:06:00 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Sat Apr 18 12:01:41 2015 +0900
@@ -11,7 +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;
         this.value = value;
@@ -24,9 +24,6 @@
         this.left = left;
     }
 
-    public void setRebuildFlag(boolean rebuildFlag){
-        this.rebuildFlag = rebuildFlag;
-    }
     public Node<K, V> left() {
         return left;
     }
@@ -36,17 +33,22 @@
     }
 
     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);
     }
 
@@ -65,6 +67,7 @@
 
 
     public Node<K, V> put(K k, V value) {
+
         int result = compare(k);
 
         if (result > 0) {
@@ -75,181 +78,229 @@
             Node node = left.put(k, value);
             return createNode(key, this.value, node, right).insBalance();
         }
+
         return createNode(key, value, left, right); // equals
 
     }
 
-    public Node<K, V> delete(K key, Node<K, V> parent) throws RotateParent {
+    public Tuple delete(K key, Node<K, V> parent) {
         if (this.isNotEmpty()) {
             int result = compare(key);
+            ;
 
-            try {
-                if (result > 0) {
-                    Node<K, V> node;
-                    node = right.delete(key, this);
-                    if (parent == null || node == null)
-                        return node;
+            if (result > 0) {
+                Tuple node = right.delete(key, this);
+                if (parent == null || node == null)
                     return node;
-                } else if (result < 0) {
-                    Node 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 = left.delete(key, this);
+                if (parent == null || node == null)
                     return node;
-                } else if (result == 0) {
-                    Node node = replaceNode(parent); // equals
-                    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;
-                }
-            } catch (RotateParent e) {
-                return e.getParent().deleteBalance(parent);
+                return node.getNode().deleteBalance(parent, node.getRebuildFlag());
             }
         }
         return null; // no key
     }
 
 
-    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) throws RotateParent {
-        Node<K, V> node;
+    public Tuple deleteSubTreeMaxNode(Node<K, V> parent) {
 
+        Tuple node;
         if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る
             node = right().deleteSubTreeMaxNode(this);
             if (parent == null)
                 return node;
-            return node.deleteBalance(parent);
+            return node.getNode().deleteBalance(parent, node.getRebuildFlag());
+
         }
+
+
         node = this.replaceNode(parent);
         if (parent == null)
             return node;
-        return node.deleteBalance(parent);
+        return node.getNode().deleteBalance(parent, node.getRebuildFlag());
+
     }
 
-    public Node deleteBalance(Node<K, V> parent) throws RotateParent {
-        if (!isRed()) {
+    public Tuple deleteBalance(Node<K, V> parent, boolean flag) {
+
+        if (flag && !isRed()) {
+
             if (0 > compare(parent.getKey())) { //自身がどちらの子かを調べる
                 boolean rightChild = parent.left().right().isRed();
                 boolean leftChild = parent.left().left().isRed();
 
+
                 if (!parent.isRed()) { //親が黒
+
                     if (!parent.left().isRed()) { //左の子が黒
+
                         if (!rightChild && !leftChild)
-                            throw new RotateParent(rebuildThree(parent, Rotate.R));
+                            return rebuildThree(parent, Rotate.R);
+
                         if (rightChild)
                             return rebuildfive(parent, Rotate.R);
                         else if (leftChild)
                             return rebuildsix(parent, Rotate.R);
+
+
                     } else { //左の子が赤
                         return rebuildTwo(parent, Rotate.R);
                     }
+
                 } else { //親が赤
+
                     if (!rightChild && !leftChild)
                         return rebuildFour(parent, Rotate.R);
+
                     if (rightChild)
                         return rebuildfive(parent, Rotate.R);
                     else if (leftChild)
                         return rebuildsix(parent, Rotate.R);
+
                 }
+
             } else {
                 boolean rightChild = parent.right().right().isRed();
                 boolean leftChild = parent.right().left().isRed();
 
+
                 if (!parent.isRed()) { //親が黒
+
                     if (!parent.right().isRed()) { //左の子が黒
+
                         if (!rightChild && !leftChild)
-                            throw new RotateParent(rebuildThree(parent, Rotate.L));
+                            return rebuildThree(parent, Rotate.L);
+
                         if (rightChild)
                             return rebuildsix(parent, Rotate.L);
                         else if (leftChild)
                             return rebuildfive(parent, Rotate.L);
+
+
                     } else { //左の子が赤
                         return rebuildTwo(parent, Rotate.L);
                     }
+
                 } else { //親が赤
+
                     if (!rightChild && !leftChild)
                         return rebuildFour(parent, Rotate.L);
+
                     if (rightChild)
                         return rebuildsix(parent, Rotate.L);
                     else if (leftChild)
-                        return rebuildfive(parent, Rotate.L)
+                        return rebuildfive(parent, Rotate.L);
+
                 }
             }
+
         }
+
+        Node newParent = null;
         if (0 > (compare(parent.getKey())))
-            return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
+            newParent = parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
         else
-            return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
+            newParent = parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
+
+        return new Tuple(newParent, false);
+
     }
 
-    protected Node<K, V> rebuildTwo(Node<K, V> parent, Rotate side) { // case2
+    protected Tuple rebuildTwo(Node<K, V> parent, Rotate side) { // case2
         if (side == Rotate.L) { // rotate Left
-            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);
+            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);
         } else {  // rotate Right
-            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);
+            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);
         }
+
     }
 
-    protected Node rebuildThree(Node<K, V> parent, Rotate side) { // case3 再帰
+    protected Tuple 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<>();
-            return parent.createNode(parent.getKey(), parent.getValue(), this, rightNode);
+            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightNode);
+            return new Tuple(newParent, true);
+
         } 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<>();
-            return parent.createNode(parent.getKey(), parent.getValue(), leftNode, this);
+            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), leftNode, this);
+            return new Tuple(newParent, true);
+
         }
+
     }
 
-    protected Node rebuildFour(Node<K, V> parent, Rotate side) { //case 4
+    protected Tuple 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());
-            return new BlackNode<K, V>(parent.getKey(), parent.getValue(), leftNode, this);
+            Node newParent = new BlackNode<K, V>(parent.getKey(), parent.getValue(), leftNode, this);
+            return new Tuple(newParent, false);
         } else {
             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);
+            Node newParent = new BlackNode<K, V>(parent.getKey(), parent.getValue(), this, rightNode);
+            return new Tuple(newParent, false);
         }
+
     }
 
-    protected Node rebuildfive(Node<K, V> parent, Rotate side) { //case5
+    protected Tuple 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
+    protected Tuple 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());
-            return parent.createNode(parent.right().getKey(), parent.right().getValue(), leftChild, rightChild);
+            Node newParent = parent.createNode(parent.right().getKey(), parent.right().getValue(), leftChild, rightChild);
+            return new Tuple(newParent, false);
         } 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);
-            return parent.createNode(parent.left().getKey(), parent.left().getValue(), leftChild, rightChild);
+            Node newParent = parent.createNode(parent.left().getKey(), parent.left().getValue(), leftChild, rightChild);
+            return new Tuple(newParent, false);
         }
+
     }
 
 
@@ -263,9 +314,9 @@
 
     abstract boolean isRed();
 
-    public abstract Node replaceNode(Node<K, V> parent) throws RotateParent;
+    public abstract Tuple replaceNode(Node<K, V> parent);
 
-    protected abstract Node deleteNode();
+    protected abstract Tuple deleteNode();
 
     protected abstract int checkBlackCount(int count); // test method
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Fri Apr 17 19:06:00 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Sat Apr 18 12:01:41 2015 +0900
@@ -29,8 +29,9 @@
     }
 
     @Override
-    protected Node deleteNode() {
-        return new EmptyNode(this.getKey());
+    protected Tuple deleteNode() {
+        EmptyNode emptyNode = new EmptyNode(this.getKey());
+        return new Tuple(emptyNode, false);
     }
 
     @Override
@@ -63,7 +64,7 @@
     }
 
     @Override
-    public Node replaceNode(Node<K, V> parent) {
+    public Tuple replaceNode(Node<K, V> parent) {
 
         Node<K, V> newNode = null;
         if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する
@@ -71,11 +72,11 @@
 
         } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる
             newNode = left().createNode(left().getKey(), left().getValue(), left().left(), left().right());
-            return newNode;
+            return new Tuple(newNode,false);
 
         } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる
             newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right());
-            return newNode;
+            return new Tuple(newNode,false);
 
         } else {//子ノードが左右にある場合
             //左の部分木の最大の値を持つNodeと自身を置き換える
@@ -85,17 +86,17 @@
                 cur = cur.right();
             }
 
-            Node<K, V> leftSubTreeNode = new EmptyNode<>();
+            Tuple leftSubTreeNode = null;
 
             if (this.left().right().isNotEmpty()) {
                 leftSubTreeNode = this.left().deleteSubTreeMaxNode(null);
-                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
-                return leftSubTreeNode.deleteBalance(newNode);
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.getNode(), this.right());
+                return leftSubTreeNode.getNode().deleteBalance(newNode,leftSubTreeNode.getRebuildFlag());
 
             } else {
                 leftSubTreeNode = this.left().replaceNode(this);
-                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
-                return leftSubTreeNode.deleteBalance(newNode);
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.getNode(), this.right());
+                return leftSubTreeNode.getNode().deleteBalance(newNode,leftSubTreeNode.getRebuildFlag());
             }
 
         }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Fri Apr 17 19:06:00 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Sat Apr 18 12:01:41 2015 +0900
@@ -54,12 +54,12 @@
 
 
     public TreeMap<K,V> delete(K key) {
-       Node node = root.delete(key,null);
+       Node node = root.delete(key,null).getNode();
 
         if (node == null)
             return this; // not key
 
-        if (!node.exitNode())
+        if (!node.isNotEmpty())
             return new TreeMap(new EmptyNode<>(),0);
         Node newRoot = new BlackNode(node.getKey(),node.getValue(),node.left(),node.right());
         return new TreeMap(newRoot,0);