Mercurial > hg > Members > tatsuki > TreeMap

changeset 12:73e915f29b42

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
RotateParent by exception
author one@firefly.cr.ie.u-ryukyu.ac.jp
date Fri, 17 Apr 2015 19:06:00 +0900
parents ef442c796b20
children b6739b88edeb
files src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java
diffstat 1 files changed, 39 insertions(+), 91 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Fri Apr 17 18:06:05 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Fri Apr 17 19:06:00 2015 +0900
@@ -36,22 +36,17 @@
     }
 
     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);
     }
 
@@ -70,7 +65,6 @@
 
 
     public Node<K, V> put(K k, V value) {
-
         int result = compare(k);
 
         if (result > 0) {
@@ -81,211 +75,168 @@
             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) {
+    public Node<K, V> delete(K key, Node<K, V> parent) throws RotateParent {
         if (this.isNotEmpty()) {
-            int result = compare(key);;
-
-            if (result > 0) {
-                Node<K, V> node = right.delete(key, this);
-                if (parent == null || node == null)
-                    return node;
-                return node.deleteBalance(parent);
+            int result = compare(key);
 
-            } else if (result < 0) {
-                Node node = left.delete(key, this);
-                if (parent == null || node == null)
+            try {
+                if (result > 0) {
+                    Node<K, V> node;
+                    node = right.delete(key, this);
+                    if (parent == null || node == null)
+                        return node;
                     return node;
-                return node.deleteBalance(parent);
-
-            } else if (result == 0) {
-                Node node = replaceNode(parent); // equals
-                if (parent == null || node == null)
+                } else if (result < 0) {
+                    Node node = left.delete(key, this);
+                    if (parent == null || node == null)
+                        return node;
                     return node;
-                return node.deleteBalance(parent);
+                } else if (result == 0) {
+                    Node node = replaceNode(parent); // equals
+                    if (parent == null || node == null)
+                        return node;
+                    return node;
+                }
+            } catch (RotateParent e) {
+                return e.getParent().deleteBalance(parent);
             }
         }
         return null; // no key
     }
 
 
-    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) {
+    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) throws RotateParent {
+        Node<K, V> node;
 
-        Node<K, V> node;
         if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る
             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 Node deleteBalance(Node<K, V> parent){
-
-        if (rebuildFlag && !isRed()) {
-
+    public Node deleteBalance(Node<K, V> parent) throws RotateParent {
+        if (!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)
-                            return rebuildThree(parent, Rotate.R);
-
+                            throw new RotateParent(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)
-                            return rebuildThree(parent, Rotate.L);
-
+                            throw new RotateParent(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)
                 }
             }
-
         }
-
         if (0 > (compare(parent.getKey())))
             return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
         else
             return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
-
     }
 
     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()); // check
+            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 = parent.right().right();
-            return parent.createNode(parent.right().getKey(), parent.right().getValue(), leftNode, rightNode);
-
+            Node<K, V> rightNode = node.right();
+            return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNode);
         } else {  // rotate Right
-            Node<K, V> rightSubTreeRoot = parent.left().createNode(parent.getKey(), parent.getValue(), parent.left().right(), this);
+            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 = parent.left().left();
-            return parent.createNode(parent.left().getKey(), parent.left().getValue(), leftNode, rightNode);
-
+            Node<K, V> leftNode = node.left();
+            return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNode);
         }
-
     }
 
-    protected Node rebuildThree(Node<K, V> parent, Rotate side) { // case3 再起
+    protected Node 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<>();
-            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightNode);
-            newParent.setRebuildFlag(true);
-            return newParent;
-
+            return parent.createNode(parent.getKey(), parent.getValue(), this, rightNode);
         } 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<>();
-            Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), leftNode, this);
-            newParent.setRebuildFlag(true);
-            return newParent;
-
+            return parent.createNode(parent.getKey(), parent.getValue(), leftNode, this);
         }
-
     }
 
     protected Node 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);
-
         } 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);
-
         }
-
     }
 
     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);
-
         }
     }
 
@@ -294,14 +245,11 @@
             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(), parent.left().right(), this);
             return parent.createNode(parent.left().getKey(), parent.left().getValue(), leftChild, rightChild);
-
         }
-
     }
 
 
@@ -315,7 +263,7 @@
 
     abstract boolean isRed();
 
-    public abstract Node replaceNode(Node<K, V> parent);
+    public abstract Node replaceNode(Node<K, V> parent) throws RotateParent;
 
     protected abstract Node deleteNode();