# HG changeset patch # User tatsuki # Date 1428298489 -32400 # Node ID 71068085728667c3827b5f7abea3f3a14e3bdb05 # Parent 6928ef8ba6f01d907dfa226687198ef2d03dcb02 bag fix rebuildFour diff -r 6928ef8ba6f0 -r 710680857286 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java --- 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 emptyNode = new EmptyNode(); + EmptyNode emptyNode = new EmptyNode(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 leftChild = new BlackNode(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 leftChild = new BlackNode(getKey(), getValue(), left, right.left()); Node rightChild = new BlackNode(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 parent) { Node 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; } } diff -r 6928ef8ba6f0 -r 710680857286 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java --- 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; - } - } diff -r 6928ef8ba6f0 -r 710680857286 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java --- 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 delete(K key, Node parent) { - int result = key.hashCode() - this.key.hashCode(); - - if (result > 0) { - Node 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 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 deleteSubTreeMaxNode(Node parent) { if (!right().right().exitNode()) { @@ -119,9 +129,9 @@ } - protected Node rebuildTwo(Node parent, Rotate side) { // case2 + protected Node rebuildTwo(Node parent, Rotate side) { // case2 if (side == Rotate.L) { // rotate Left - Node leftSubTreeRoot = parent.right().createNode(parent.getKey(), parent.getValue(), this, parent.right().left()); + Node leftSubTreeRoot = parent.right().createNode(parent.getKey(), parent.getValue(), this, parent.right().left()); // check Node leftNode = this.deleteBalance(leftSubTreeRoot); Node rightNode = parent.right().right(); return parent.createNode(parent.right().getKey(), parent.right().getValue(), leftNode, rightNode); @@ -138,13 +148,22 @@ protected Node rebuildThree(Node parent, Rotate side) { // case3 再起 if (side == Rotate.L) { - Node rightNode = new BlackNode(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right()); + Node rightNode; + if (parent.right().exitNode()) + rightNode = new RedNode(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right()); // check + else + rightNode = new EmptyNode<>(); Node newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightNode); newParent.setRebuildFlag(true); return newParent; - } else { // rotate Right - Node rightNode = new BlackNode(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right()); - Node newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightNode); + + } else { + Node leftNode; + if (parent.left().exitNode()) + leftNode = new RedNode(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right()); // check + else + leftNode = new EmptyNode<>(); + Node newParent = parent.createNode(parent.getKey(), parent.getValue(), leftNode, this); newParent.setRebuildFlag(true); return newParent; @@ -153,13 +172,13 @@ } protected Node rebuildFour(Node parent, Rotate side) { //case 4 - if (side == Rotate.L) { - Node rightNode = new RedNode(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right()); - return new BlackNode(parent.getKey(), parent.getValue(), this, rightNode); + if (side == Rotate.R) { + Node rightNode = new RedNode(this.getKey(), this.getValue(), this.left(), this.right()); + return new BlackNode(parent.getKey(), parent.getValue(), parent.left(), rightNode); } else { - Node leftNode = new RedNode(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right()); - return new BlackNode(parent.getKey(), parent.getValue(), leftNode, this); + Node leftNode = new RedNode(this.getKey(), this.getValue(), this.left(), this.right()); // ok + return new BlackNode(parent.getKey(), parent.getValue(), leftNode, parent.right()); } } @@ -208,17 +227,15 @@ public abstract Node deleteBalance(Node 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 parent) ; + public abstract Node replaceNode(Node parent); protected abstract Node deleteNode(); diff -r 6928ef8ba6f0 -r 710680857286 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java --- 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 parent) { // not use method - return this; + public Node deleteBalance(Node 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 parent) { Node newNode = null; diff -r 6928ef8ba6f0 -r 710680857286 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java --- 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 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); } diff -r 6928ef8ba6f0 -r 710680857286 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java --- 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 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 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"); }