Mercurial > hg > Members > tatsuki > TreeMap
changeset 11:ef442c796b20
change method name exitNode to isNotEmpty and checkColor to isRed
| author | tatsuki |
|---|---|
| date | Fri, 17 Apr 2015 18:06:05 +0900 |
| parents | 6304463eefbf |
| children | 73e915f29b42 |
| 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 |
| diffstat | 4 files changed, 38 insertions(+), 38 deletions(-) [+] |
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java Fri Apr 17 14:16:36 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java Fri Apr 17 18:06:05 2015 +0900 @@ -30,7 +30,7 @@ @Override - protected boolean exitNode() { + protected boolean isNotEmpty() { return true; } @@ -79,7 +79,7 @@ } @Override - boolean checkColor() { + boolean isRed() { return false; } @@ -93,18 +93,18 @@ public Node replaceNode(Node<K, V> parent) { Node<K, V> newNode = null; - if (!this.left().exitNode() && !this.right().exitNode()) { //自身を削除する + if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する return deleteNode();//黒が1つ減るので木のバランスを取る - } else if (this.left().exitNode() && !this.right().exitNode()) { //左の部分木を昇格させる + } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right()); - if (!this.left().checkColor()) //昇格させる木のrootが黒だったらバランスを取る + if (!this.left().isRed()) //昇格させる木のrootが黒だったらバランスを取る newNode.setRebuildFlag(true); return newNode; - } else if (!this.left().exitNode() && this.right().exitNode()) { //右の部分木を昇格させる + } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる newNode = createNode(right().getKey(), right().getValue(), right().left(), right().right()); - if (!this.right().checkColor()) //昇格させる木のrootが黒だったらバランスを取る + if (!this.right().isRed()) //昇格させる木のrootが黒だったらバランスを取る newNode.setRebuildFlag(true); return newNode; @@ -112,12 +112,12 @@ //左の部分木の最大の値を持つNodeと自身を置き換える Node<K, V> cur = this.left(); - while (cur.right().exitNode()) { //左の部分期の最大値を持つNodeを取得する + while (cur.right().isNotEmpty()) { //左の部分期の最大値を持つNodeを取得する cur = cur.right(); } - if (this.left().right().exitNode()) { //左の部分木が右の子を持っているか + 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);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java Fri Apr 17 14:16:36 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java Fri Apr 17 18:06:05 2015 +0900 @@ -29,7 +29,7 @@ @Override - protected boolean exitNode() { + protected boolean isNotEmpty() { return false; } @@ -71,7 +71,7 @@ } @Override - boolean checkColor() { + boolean isRed() { return false; }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java Fri Apr 17 14:16:36 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java Fri Apr 17 18:06:05 2015 +0900 @@ -39,7 +39,7 @@ Node<K, V> cur = this; - while (cur.exitNode()) { + while (cur.isNotEmpty()) { int result = compare(key); if (result > 0) @@ -87,7 +87,7 @@ } public Node<K, V> delete(K key, Node<K, V> parent) { - if (this.exitNode()) { + if (this.isNotEmpty()) { int result = compare(key);; if (result > 0) { @@ -116,7 +116,7 @@ public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) { Node<K, V> node; - if (right().exitNode()) {//最大値のノードが取得できるまで潜る + if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る node = right().deleteSubTreeMaxNode(this); if (parent == null) return node; @@ -134,16 +134,16 @@ public Node deleteBalance(Node<K, V> parent){ - if (rebuildFlag && !checkColor()) { + if (rebuildFlag && !isRed()) { if (0 > compare(parent.getKey())) { //自身がどちらの子かを調べる - boolean rightChild = parent.left().right().checkColor(); - boolean leftChild = parent.left().left().checkColor(); + boolean rightChild = parent.left().right().isRed(); + boolean leftChild = parent.left().left().isRed(); - if (!parent.checkColor()) { //親が黒 + if (!parent.isRed()) { //親が黒 - if (!parent.left().checkColor()) { //左の子が黒 + if (!parent.left().isRed()) { //左の子が黒 if (!rightChild && !leftChild) return rebuildThree(parent, Rotate.R); @@ -171,13 +171,13 @@ } } else { - boolean rightChild = parent.right().right().checkColor(); - boolean leftChild = parent.right().left().checkColor(); + boolean rightChild = parent.right().right().isRed(); + boolean leftChild = parent.right().left().isRed(); - if (!parent.checkColor()) { //親が黒 + if (!parent.isRed()) { //親が黒 - if (!parent.right().checkColor()) { //左の子が黒 + if (!parent.right().isRed()) { //左の子が黒 if (!rightChild && !leftChild) return rebuildThree(parent, Rotate.L); @@ -234,7 +234,7 @@ protected Node rebuildThree(Node<K, V> parent, Rotate side) { // case3 再起 if (side == Rotate.L) { Node<K, V> rightNode; - if (parent.right().exitNode()) + 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<>(); @@ -244,7 +244,7 @@ } else { Node<K, V> leftNode; - if (parent.left().exitNode()) + 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<>(); @@ -305,7 +305,7 @@ } - protected abstract boolean exitNode(); + protected abstract boolean isNotEmpty(); public abstract Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right); @@ -313,7 +313,7 @@ abstract Rotate checkRotate(Rotate side); - abstract boolean checkColor(); + abstract boolean isRed(); public abstract Node replaceNode(Node<K, V> parent);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java Fri Apr 17 14:16:36 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java Fri Apr 17 18:06:05 2015 +0900 @@ -14,7 +14,7 @@ @Override - protected boolean exitNode() { + protected boolean isNotEmpty() { return true; } @@ -37,19 +37,19 @@ Rotate checkRotate(Rotate side) { if (side == L) { - if (left.checkColor()) + if (left.isRed()) return R; - else if (right.checkColor()) + else if (right.isRed()) return LR; return N; } else { - if (left.checkColor()) + if (left.isRed()) return RL; - else if (right.checkColor()) + else if (right.isRed()) return L; return N; @@ -58,7 +58,7 @@ } @Override - boolean checkColor() { + boolean isRed() { return true; } @@ -66,14 +66,14 @@ public Node replaceNode(Node<K, V> parent) { Node<K, V> newNode = null; - if (!this.left().exitNode() && !this.right().exitNode()) { //自身を削除する + if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する return deleteNode(); - } else if (this.left().exitNode() && !this.right().exitNode()) { //左の部分木を昇格させる + } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる newNode = left().createNode(left().getKey(), left().getValue(), left().left(), left().right()); return newNode; - } else if (!this.left().exitNode() && this.right().exitNode()) { //右の部分木を昇格させる + } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right()); return newNode; @@ -81,13 +81,13 @@ //左の部分木の最大の値を持つNodeと自身を置き換える Node<K, V> cur = this.left(); - while (cur.right().exitNode()) { + while (cur.right().isNotEmpty()) { cur = cur.right(); } Node<K, V> leftSubTreeNode = new EmptyNode<>(); - if (this.left().right().exitNode()) { + if (this.left().right().isNotEmpty()) { leftSubTreeNode = this.left().deleteSubTreeMaxNode(null); newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); return leftSubTreeNode.deleteBalance(newNode);