Mercurial > hg > Members > tatsuki > TreeMap
changeset 10:6304463eefbf
delete
RebuildDelete
RebuildDeleteChild
| author | tatsuki |
|---|---|
| date | Fri, 17 Apr 2015 14:16:36 +0900 |
| parents | 5da70bcfb824 |
| children | ef442c796b20 |
| 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/test/TreeMapDelete.java |
| diffstat | 5 files changed, 98 insertions(+), 243 deletions(-) [+] |
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java Thu Apr 16 21:03:44 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java Fri Apr 17 14:16:36 2015 +0900 @@ -27,76 +27,6 @@ return count; } - @Override - public Node deleteBalance(Node<K, V> parent) { - if (rebuildFlag) { - Rotate editNodeSide; - DeleteRebuildFlag flag; - if (0 > compare(parent)) { //自身がどちらの子かを調べる - editNodeSide = Rotate.R;//右の子 - flag = parent.right().childRebuildDelete(Rotate.R); - - if (parent.right().isBlack()) { - boolean rightChild = this.right().checkColor(); - boolean leftChild = this.left().checkColor(); - - if (!rightChild && !leftChild) - return DeleteRebuildFlag.allBlack; - - if (rightChild) - return DeleteRebuildFlag.five; - else - return DeleteRebuildFlag.six; - - } else { - //red - } - - } else { - editNodeSide = Rotate.L;//左の子 - flag = parent.right().childRebuildDelete(Rotate.L); - - if (parent.left().isBlack()) { - boolean rightChild = this.right().checkColor(); - boolean leftChild = this.left().checkColor(); - - if (!rightChild && !leftChild) - return DeleteRebuildFlag.allBlack; - - if (leftChild) - return DeleteRebuildFlag.five; - else - return DeleteRebuildFlag.six; - - } else { - //red - } - } - - - if (flag == DeleteRebuildFlag.allBlack) { - if (parent.isBlack()) - return rebuildThree(parent, editNodeSide); - else - return rebuildFour(parent, editNodeSide); - } - - switch (flag) { - case two: - return rebuildTwo(parent, editNodeSide); - case five: - return rebuildfive(parent, editNodeSide); - case six: - return rebuildsix(parent, editNodeSide); - } - } - if (0 > (compare(parent))) - return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this); - else - return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right()); - - } - @Override @@ -153,48 +83,12 @@ return false; } - @Override - DeleteRebuildFlag RebuildDelete(Rotate side) { - DeleteRebuildFlag flag; - if (side == Rotate.R) {//どっち側のNodeを編集したか 右側を編集して来たならRが来る - flag = this.left().childRebuildDelete(side); - } else { - flag = this.right().childRebuildDelete(side); - } - - if (flag == DeleteRebuildFlag.allBlack) - return DeleteRebuildFlag.three; - - return flag; - } - - @Override - DeleteRebuildFlag childRebuildDelete(Rotate side) { - boolean rightChild = this.right().checkColor(); - boolean leftChild = this.left().checkColor(); - - if (!rightChild && !leftChild) - return DeleteRebuildFlag.allBlack; - - if (side == Rotate.R) {//どっち側のNodeを編集したか 右側を編集して来たならRが来る - if (rightChild) - return DeleteRebuildFlag.five; - else - return DeleteRebuildFlag.six; - } - - if (side == Rotate.L) { - if (leftChild) - return DeleteRebuildFlag.five; - else - return DeleteRebuildFlag.six; - } - - return null; - } - + /** + * @param parent + * @return + */ @Override public Node replaceNode(Node<K, V> parent) {
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java Thu Apr 16 21:03:44 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java Fri Apr 17 14:16:36 2015 +0900 @@ -59,38 +59,6 @@ return this; } - @Override - public Node deleteBalance(Node<K, V> parent) { - if (rebuildFlag) { - Rotate editNodeSide; - if (0 > (parent.getKey().hashCode() - this.getKey().hashCode())) - editNodeSide = Rotate.R; - else - editNodeSide = Rotate.L; - - DeleteRebuildFlag flag = parent.RebuildDelete(editNodeSide); - - - switch (flag) { - case two: - return rebuildTwo(parent, editNodeSide); - case three: - return rebuildThree(parent, editNodeSide); - case four: - return rebuildFour(parent, editNodeSide); - case five: - return rebuildfive(parent, editNodeSide); - case six: - return rebuildsix(parent, editNodeSide); - } - } - - 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 public Optional<V> get(K key) { @@ -108,16 +76,6 @@ } @Override - DeleteRebuildFlag RebuildDelete(Rotate side) { //not use method - return null; - } - - @Override - DeleteRebuildFlag childRebuildDelete(Rotate side) { - return DeleteRebuildFlag.allBlack; - } - - @Override protected int checkBlackCount(int count) { // test method System.out.println("blackCount = " + count); return count;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java Thu Apr 16 21:03:44 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java Fri Apr 17 14:16:36 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,12 +24,15 @@ this.left = left; } + public void setRebuildFlag(boolean rebuildFlag){ + this.rebuildFlag = rebuildFlag; + } public Node<K, V> left() { return left; } - public int compare(Node<K, V> parent) { - return (parent.getKey().hashCode() - key.hashCode()); + public int compare(K parentKey) { + return (parentKey.hashCode() - getKey().hashCode()); } public Optional<V> get(K key) { @@ -37,7 +40,7 @@ Node<K, V> cur = this; while (cur.exitNode()) { - int result = key.hashCode() - cur.getKey().hashCode(); + int result = compare(key); if (result > 0) cur = cur.right(); @@ -68,7 +71,7 @@ public Node<K, V> put(K k, V value) { - int result = k.hashCode() - this.key.hashCode(); + int result = compare(k); if (result > 0) { Node<K, V> node = right.put(k, value); @@ -85,7 +88,7 @@ public Node<K, V> delete(K key, Node<K, V> parent) { if (this.exitNode()) { - int result = key.hashCode() - this.key.hashCode(); + int result = compare(key);; if (result > 0) { Node<K, V> node = right.delete(key, this); @@ -122,13 +125,94 @@ } - node = this.replaceNode(parent); //怪しい地点 + node = this.replaceNode(parent); if (parent == null) return node; return node.deleteBalance(parent); } + public Node deleteBalance(Node<K, V> parent){ + + if (rebuildFlag && !checkColor()) { + + if (0 > compare(parent.getKey())) { //自身がどちらの子かを調べる + boolean rightChild = parent.left().right().checkColor(); + boolean leftChild = parent.left().left().checkColor(); + + + if (!parent.checkColor()) { //親が黒 + + if (!parent.left().checkColor()) { //左の子が黒 + + if (!rightChild && !leftChild) + 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().checkColor(); + boolean leftChild = parent.right().left().checkColor(); + + + if (!parent.checkColor()) { //親が黒 + + if (!parent.right().checkColor()) { //左の子が黒 + + if (!rightChild && !leftChild) + 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); + + } + } + + } + + 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 @@ -227,16 +311,10 @@ abstract Node<K, V> insBalance(); - public abstract Node deleteBalance(Node<K, V> Parent); - abstract Rotate checkRotate(Rotate side); abstract boolean checkColor(); - abstract DeleteRebuildFlag RebuildDelete(Rotate side); - - abstract DeleteRebuildFlag childRebuildDelete(Rotate side); - public abstract Node replaceNode(Node<K, V> parent); protected abstract Node deleteNode();
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java Thu Apr 16 21:03:44 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java Fri Apr 17 14:16:36 2015 +0900 @@ -29,15 +29,6 @@ } @Override - public Node deleteBalance(Node<K, V> parent) { - - 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 protected Node deleteNode() { return new EmptyNode(this.getKey()); } @@ -72,27 +63,6 @@ } @Override - DeleteRebuildFlag RebuildDelete(Rotate side) { - - DeleteRebuildFlag flag; - if (side == Rotate.R) { - flag = this.left().childRebuildDelete(side); - } else { - flag = this.right().childRebuildDelete(side); - } - - if (flag == DeleteRebuildFlag.allBlack) - return DeleteRebuildFlag.four; - - return flag; - } - - @Override - DeleteRebuildFlag childRebuildDelete(Rotate side) { - return DeleteRebuildFlag.two; - } - - @Override public Node replaceNode(Node<K, V> parent) { Node<K, V> newNode = null;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java Thu Apr 16 21:03:44 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java Fri Apr 17 14:16:36 2015 +0900 @@ -13,18 +13,15 @@ public class TreeMapDelete { public static void main(String args[]) { TreeMap<Integer, Integer> map = new TreeMap(); - for (int count = 1; count < 200; count++) { + for (int count = 1; count < 2000; count++) { map = map.put(count, count); } ArrayList<Integer> list = new ArrayList(); - for (int i = 1; i < 200; i++) { + for (int i = 1; i < 2000; i++) { list.add(i); } - - // test(map); - Collections.shuffle(list); for (Integer num : list) { System.out.println(num); @@ -33,52 +30,10 @@ map.checkBlackCount(); } for (Integer num : list) { - System.out.println(num); + // System.out.println(num); } System.out.println("end"); } - public static void test(TreeMap map) { - TreeMap neMap = map.delete(11); - neMap.checkBlackCount(); - neMap = neMap.delete(2); - neMap.checkBlackCount(); - neMap = neMap.delete(8); - neMap.checkBlackCount(); - neMap = neMap.delete(6); - neMap.checkBlackCount(); - neMap = neMap.delete(5); - neMap.checkBlackCount(); - neMap = neMap.delete(3); - neMap.checkBlackCount(); - neMap = neMap.delete(12); - neMap.checkBlackCount(); - neMap = neMap.delete(16); - neMap.checkBlackCount(); - neMap = neMap.delete(13); - neMap.checkBlackCount(); - neMap = neMap.delete(17); - neMap.checkBlackCount(); - 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(14); - neMap.checkBlackCount(); - neMap = neMap.delete(9); - neMap.checkBlackCount(); - neMap = neMap.delete(15); - neMap.checkBlackCount(); - neMap = neMap.delete(18); - neMap.checkBlackCount(); - - - } }