Mercurial > hg > Members > shoshi > jungle > jungle-core
changeset 297:1f929fe9c153
fix RedBlackJungleTree delete
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/BlackNode.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/BlackNode.java Thu Jan 05 09:49:20 2017 +0900 @@ -12,7 +12,6 @@ super(key, value, left, right); } - @Override public rebuildNode deleteNode() { EmptyNode<K, V> emptyNode = new EmptyNode<>(key); @@ -122,7 +121,7 @@ Node<K, V> newParent = createNode(this.left().getKey(), this.left().getValue(), node, this.right()); return node.deleteBalance(newParent, ctr); } - Node<K,V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode(); + Node<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode(); newNode = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); return new rebuildNode(false, newNode); }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Node.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Node.java Thu Jan 05 09:49:20 2017 +0900 @@ -205,6 +205,7 @@ } } } + if (0 > (compare(parent.getKey(), ctr))) { newNode = parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this); return new rebuildNode<>(false, newNode); @@ -218,15 +219,13 @@ 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 - rebuildNode<K, V> rebuildNode = new rebuildNode<>(false, leftSubTreeRoot); - rebuildNode<K, V> leftNodeRebuildNode = this.deleteBalance(rebuildNode.getNode(), ctr); + rebuildNode<K, V> leftNodeRebuildNode = this.deleteBalance(leftSubTreeRoot, ctr); Node<K, V> rightNode = node.right(); return parent.createNode(node.getKey(), node.getValue(), leftNodeRebuildNode.getNode(), rightNode); } else { // rotate Right Node<K, V> node = parent.left(); Node<K, V> rightSubTreeRoot = node.createNode(parent.getKey(), parent.getValue(), node.right(), this); - rebuildNode<K, V> rightSubTreeRebuildNode = new rebuildNode<>(false, rightSubTreeRoot); - rebuildNode<K, V> rightNodeRebuildNode = this.deleteBalance(rightSubTreeRebuildNode.getNode(), ctr); + rebuildNode<K, V> rightNodeRebuildNode = this.deleteBalance(rightSubTreeRoot, ctr); Node<K, V> leftNode = node.left(); return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNodeRebuildNode.getNode()); }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java Thu Jan 05 09:49:20 2017 +0900 @@ -12,7 +12,6 @@ super(key, value, left, right); } - @Override protected boolean isNotEmpty() { return true; @@ -56,6 +55,19 @@ return true; } + @Override + public rebuildNode<K, V> deleteBalance(Node<K, V> parent, Comparator ctr) { + Node<K,V> newNode = null; + if (0 > (compare(parent.getKey(), ctr))) { + newNode = parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this); + return new rebuildNode<>(false, newNode); + } else { + newNode = parent.createNode(parent.getKey(), parent.getValue(), this, parent.right()); + return new rebuildNode<>(false, newNode); + } + } + + @SuppressWarnings("unchecked") @Override public rebuildNode replaceNode(Node<K, V> parent, Comparator ctr) {
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/BlackTreeNode.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/BlackTreeNode.java Thu Jan 05 09:49:20 2017 +0900 @@ -15,7 +15,7 @@ public class BlackTreeNode extends ColorlessTreeNode { public BlackTreeNode(ColorlessTreeNode node) { - this(node.getAttrs(), node.key(),node.value(),node.left(),node.right()); + this(node.getAttrs(), node.key(), node.value(), node.left(), node.right()); } public BlackTreeNode(TreeMap<String, ByteBuffer> _attrs, String balanceKey, ByteBuffer value, ColorlessTreeNode left, ColorlessTreeNode right) { @@ -23,18 +23,8 @@ } @Override - public RedBlackTreeNodeChildren getChildren() { - return new RedBlackTreeNodeChildren(this, getAttrs()); - } - - @Override - public RedBlackTreeNodeAttribute getAttributes() { - return new RedBlackTreeNodeAttribute(left(), right(), getAttrs(),key(),value()); - } - - @Override public ColorlessTreeNode createNode(TreeMap<String, ByteBuffer> newAttrs, String insertKey, ByteBuffer insertValue, ColorlessTreeNode left, ColorlessTreeNode right) { - return new BlackTreeNode(newAttrs,insertKey,insertValue,left,right); + return new BlackTreeNode(newAttrs, insertKey, insertValue, left, right); } @Override @@ -42,6 +32,12 @@ return null;//new BlackTreeNode(); } + @Override + protected RebuildNode deleteNode() { + ColorlessTreeNode emptyNode = new EmptyTreeNode(value()); + return new RebuildNode(true, emptyNode); + } + public TreeNode clone() { return new BlackTreeNode(getAttrs(), key(), value(), left(), right()); } @@ -83,24 +79,22 @@ ColorlessTreeNode newLeftChild = new BlackTreeNode(left().left().getAttrs(), left().left().key(), left().left().value(), left().left().left(), left().left().right()); ColorlessTreeNode newRightChild = new BlackTreeNode(getAttrs(), key(), value(), left().right(), right()); return new RedTreeNode(left().getAttrs(), left().key(), left().value(), newLeftChild, newRightChild); - } else - if (spin == Rotate.LR) { - ColorlessTreeNode newLeftChild = new BlackTreeNode(left().getAttrs(), left().key(), left().value(), left().left(), left().right().left()); - ColorlessTreeNode newRightChild = new BlackTreeNode(getAttrs(), key(), value(), left().right().right(), right()); - return new RedTreeNode(left().right().getAttrs(), left().right().key(), left().right().value(), newLeftChild, newRightChild); - } + } else if (spin == Rotate.LR) { + ColorlessTreeNode newLeftChild = new BlackTreeNode(left().getAttrs(), left().key(), left().value(), left().left(), left().right().left()); + ColorlessTreeNode newRightChild = new BlackTreeNode(getAttrs(), key(), value(), left().right().right(), right()); + return new RedTreeNode(left().right().getAttrs(), left().right().key(), left().right().value(), newLeftChild, newRightChild); + } spin = right().checkRotate(Rotate.R); if (spin == Rotate.L) { ColorlessTreeNode newLeftChild = new BlackTreeNode(getAttrs(), key(), value(), left(), right().left()); ColorlessTreeNode newRightChild = new BlackTreeNode(right().right().getAttrs(), right().right().key(), right().right().value(), right().right().left(), right().right().right()); return new RedTreeNode(right().getAttrs(), right().key(), right().value(), newLeftChild, newRightChild); - } else - if (spin == Rotate.RL) { - ColorlessTreeNode newLeftChild = new BlackTreeNode(getAttrs(), key(), value(), left(), right().left().left()); - ColorlessTreeNode newRightChild = new BlackTreeNode(right().getAttrs(), right().key(), right().value(), right().left().right(), right().right()); - return new RedTreeNode(right().left().getAttrs(), right().left().key(), right().left().value(), newLeftChild, newRightChild); - } + } else if (spin == Rotate.RL) { + ColorlessTreeNode newLeftChild = new BlackTreeNode(getAttrs(), key(), value(), left(), right().left().left()); + ColorlessTreeNode newRightChild = new BlackTreeNode(right().getAttrs(), right().key(), right().value(), right().left().right(), right().right()); + return new RedTreeNode(right().left().getAttrs(), right().left().key(), right().left().value(), newLeftChild, newRightChild); + } return this; } @@ -115,7 +109,46 @@ @Override protected RebuildNode replaceNode(ColorlessTreeNode parent) { - return null; + ColorlessTreeNode newNode; + if (this.left().empty() && this.right().empty()) { //自身を削除する + return deleteNode();//黒が1つ減るので木のバランスを取る + } else if (!this.left().empty() && this.right().empty()) { //左の部分木を昇格させる + newNode = createNode(left().getAttrs(), left().key(), left().value(), left().left(), left().right()); + if (!this.left().isRed()) //昇格させる木のrootが黒だったらバランスを取る + return new RebuildNode(true, newNode); + return new RebuildNode(false, newNode); + } else if (this.left().empty() && !this.right().empty()) { //右の部分木を昇格させる + newNode = createNode(right().getAttrs(), right().key(), right().value(), right().left(), right().right()); + if (!this.right().isRed()) //昇格させる木のrootが黒だったらバランスを取る + return new RebuildNode(true, newNode); + return new RebuildNode(false, newNode); + } else {//子ノードが左右にある場合 二回目はここには入らない + //左の部分木の最大の値を持つNodeと自身を置き換える + ColorlessTreeNode cur = this.left(); + while (!cur.right().empty()) { //左の部分期の最大値を持つNodeを取得する + cur = cur.right(); + } + if (!this.left().right().empty()) { //左の部分木が右の子を持っているか + RebuildNode leftSubTreeNodeRebuildNode = this.left().deleteSubTreeMaxNode(null, Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。 + if (leftSubTreeNodeRebuildNode.rebuild()) { + ColorlessTreeNode leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode(); + ColorlessTreeNode newParent = createNode(cur.getAttrs(), cur.key(), cur.value(), leftSubTreeNode, this.right()); + return leftSubTreeNode.deleteBalance(newParent); + } + ColorlessTreeNode leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode(); + newNode = createNode(cur.getAttrs(), cur.key(), cur.value(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する + return new RebuildNode(false, newNode); + } else { + RebuildNode leftSubTreeNodeRebuildNode = this.left().replaceNode(this);//右の子がいなかった場合、左の子を昇格させるだけで良い。 + if (leftSubTreeNodeRebuildNode.rebuild()) { + ColorlessTreeNode node = leftSubTreeNodeRebuildNode.getNode(); + ColorlessTreeNode newParent = createNode(this.left().getAttrs(), this.left().key(), this.left().value(), node, this.right()); + return node.deleteBalance(newParent); + } + ColorlessTreeNode leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode(); + newNode = createNode(this.left().getAttrs(), this.left().key(), this.left().value(), leftSubTreeNode, this.right()); + return new RebuildNode(false, newNode); + } + } } - }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java Thu Jan 05 09:49:20 2017 +0900 @@ -1,7 +1,6 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; -import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.Rotate; -import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.*; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import org.junit.Test; @@ -14,6 +13,7 @@ private String balanceKey; private ByteBuffer value; + private String valueStr; private TreeMap<String, ByteBuffer> attrs; private ColorlessTreeNode leftChild; private ColorlessTreeNode rightChild; @@ -24,20 +24,35 @@ this.value = value; this.leftChild = left; this.rightChild = right; + if (value != null) + this.valueStr = new String(value.array()); + } + + //test用 + public boolean get(ByteBuffer seach) { + if (!this.empty()) { + long test = value().hashCode(); + String str = new String(value().array()); + long result = this.compare(seach); + if (result > 0) { + return right().get(seach); + } else if (result < 0) { + return left().get(seach); + } else { + return true; + } + } + return false; } public ColorlessTreeNode left() { return leftChild; } - ; - public ColorlessTreeNode right() { return rightChild; } - ; - public String key() { return balanceKey; } @@ -50,20 +65,10 @@ return attrs; } - @Override - public abstract RedBlackTreeNodeChildren getChildren(); - - @Override - public abstract RedBlackTreeNodeAttribute getAttributes(); - - public abstract ColorlessTreeNode createNode(TreeMap<String, ByteBuffer> newAttrs, String insertKey, ByteBuffer insertValue, ColorlessTreeNode left, ColorlessTreeNode right); - - public abstract boolean isRed(); - - public abstract boolean empty(); - - private int compare(ByteBuffer value) { - return value().hashCode() - value.hashCode(); + private long compare(ByteBuffer value) { + long h1 = value().hashCode(); + long h2 = value.hashCode(); + return h1 - h2; } public ColorlessTreeNode addNewChild(String insertKey, ByteBuffer insertValue) { @@ -72,7 +77,7 @@ return createNode(newAttrs, insertKey, insertValue, leftChild, rightChild); } - int result = this.compare(insertValue); + long result = this.compare(insertValue); if (result > 0) { ColorlessTreeNode newNode = rightChild.addNewChild(insertKey, insertValue); newNode = createNode(getAttrs(), key(), value(), left(), newNode); @@ -86,9 +91,16 @@ } } - protected abstract ColorlessTreeNode insBalance(); - public abstract Rotate checkRotate(Rotate side); + @Override + public RedBlackTreeNodeChildren getChildren() { + return new RedBlackTreeNodeChildren(this, getAttrs()); + } + + @Override + public RedBlackTreeNodeAttribute getAttributes() { + return new RedBlackTreeNodeAttribute(left(), right(), getAttrs(), key(), value()); + } @Test /** @@ -98,14 +110,14 @@ */ public abstract int checkDepth(int count, int minCount); - public RebuildNode delete(String insertKey, ByteBuffer insertValue, ColorlessTreeNode parent, Rotate side) { + public RebuildNode delete(String insertKey, ByteBuffer deleteValue, ColorlessTreeNode parent, Rotate side) { if (!this.empty()) { RebuildNode rebuildNode; - int result = this.compare(insertValue); + long result = this.compare(deleteValue); if (result > 0) { - rebuildNode = right().delete(insertKey, insertValue, this, Rotate.R); + rebuildNode = right().delete(insertKey, deleteValue, this, Rotate.R); } else if (result < 0) { - rebuildNode = left().delete(insertKey, insertValue, this, Rotate.L); + rebuildNode = left().delete(insertKey, deleteValue, this, Rotate.L); } else { rebuildNode = replaceNode(parent); } @@ -131,12 +143,194 @@ public RebuildNode deleteBalance(ColorlessTreeNode parent) { ColorlessTreeNode newNode = null; if (!isRed()) { + if (0 > compare(parent.value())) { + boolean rightChildFlag = parent.left().right().isRed(); + boolean leftChildFlag = parent.left().left().isRed(); + + if (!parent.isRed()) {//親が黒 + if (!parent.left().isRed()) {//左の子が黒 + if (!leftChildFlag && !rightChildFlag) { + newNode = rebuildThree(parent, Rotate.R); + return new RebuildNode(true, newNode); + } + if (rightChildFlag) { + newNode = rebuildFive(parent, Rotate.R); + return new RebuildNode(false, newNode); + } else { + newNode = rebuildSix(parent, Rotate.R); + return new RebuildNode(false, newNode); + } + } else { //左の子が赤 + newNode = rebuildTwo(parent, Rotate.R); + return new RebuildNode(false, newNode); + } + } else {//親が赤 + if (!rightChildFlag && !leftChildFlag) { + newNode = rebuildFour(parent, Rotate.R); + return new RebuildNode(false, newNode); + } + if (rightChildFlag) { + newNode = rebuildFive(parent, Rotate.R); + return new RebuildNode(false, newNode); + } else { + newNode = rebuildSix(parent, Rotate.R); + return new RebuildNode(false, newNode); + } + } + } else { + boolean rightChildFlag = parent.right().right().isRed(); + boolean leftChildFlag = parent.right().left().isRed(); + if (!parent.isRed()) { //親が黒 + if (!parent.right().isRed()) { //右の子が黒 + if (!leftChildFlag && !rightChildFlag) { + newNode = rebuildThree(parent, Rotate.L); + return new RebuildNode(true, newNode); + } + if (rightChildFlag) { + newNode = rebuildSix(parent, Rotate.L); + return new RebuildNode(false, newNode); + } else { + newNode = rebuildFive(parent, Rotate.L); + return new RebuildNode(false, newNode); + } + } else { //左の子が赤 + newNode = rebuildTwo(parent, Rotate.L); + return new RebuildNode(false, newNode); + } + } else { //親が赤 + if (!rightChildFlag && !leftChildFlag) { + newNode = rebuildFour(parent, Rotate.L); + return new RebuildNode(false, newNode); + } + if (rightChildFlag) { + newNode = rebuildSix(parent, Rotate.L); + return new RebuildNode(false, newNode); + } else { + newNode = rebuildFive(parent, Rotate.L); + return new RebuildNode(false, newNode); + } + + } + } } - return null; + if (0 > compare(parent.value())) { + newNode = parent.createNode(parent.getAttrs(), parent.key(), parent.value(), parent.left(), this); + return new RebuildNode(false, newNode); + } else { + newNode = parent.createNode(parent.getAttrs(), parent.key(), parent.value(), this, parent.right()); + return new RebuildNode(false, newNode); + } } - protected RebuildNode replaceNode(ColorlessTreeNode parent) { - return null; + + private ColorlessTreeNode rebuildTwo(ColorlessTreeNode parent, Rotate side) { + if (side == Rotate.L) { + ColorlessTreeNode node = parent.right(); + ColorlessTreeNode leftSubTreeRoot = node.createNode(parent.getAttrs(), parent.key(), parent.value(), this, node.left()); + RebuildNode leftNodeRebuildNode = this.deleteBalance(leftSubTreeRoot); + ColorlessTreeNode rightNode = node.right(); + return parent.createNode(node.getAttrs(), node.key(), node.value(), leftNodeRebuildNode.getNode(), rightNode); + } else { + ColorlessTreeNode node = parent.left(); + ColorlessTreeNode rightSubTreeRoot = node.createNode(parent.getAttrs(), parent.key(), parent.value(), node.right(), this); + RebuildNode rightNoodRebuildNode = this.deleteBalance(rightSubTreeRoot); + ColorlessTreeNode leftNode = node.left(); + return parent.createNode(node.getAttrs(), node.key(), node.value(), leftNode, rightNoodRebuildNode.getNode()); + } + } + + private ColorlessTreeNode rebuildThree(ColorlessTreeNode parent, Rotate side) { + if (side == Rotate.L) { + ColorlessTreeNode rightNode; + if (!parent.right().empty()) + rightNode = new RedTreeNode(parent.right().getAttrs(), parent.right().key(), parent.right().value(), parent.right().left(), parent.right().right()); + else + rightNode = new EmptyTreeNode(); + return parent.createNode(parent.getAttrs(), parent.key(), parent.value(), this, rightNode); + } else { + ColorlessTreeNode leftNode; + if (!parent.left().empty()) + leftNode = new RedTreeNode(parent.left().getAttrs(), parent.left().key(), parent.left().value(), parent.left().left(), parent.left().right()); + else + leftNode = new EmptyTreeNode(); + return parent.createNode(parent.getAttrs(), parent.key(), parent.value(), leftNode, this); + } + } + + private ColorlessTreeNode rebuildFour(ColorlessTreeNode parent, Rotate side) { + if (side == Rotate.R) { + ColorlessTreeNode leftNode = new RedTreeNode(parent.left().getAttrs(), parent.left().key(), parent.left().value(), parent.left().left(), parent.left().right()); + return new BlackTreeNode(parent.getAttrs(), parent.key(), parent.value(), leftNode, this); + } else { + ColorlessTreeNode rightNode = new RedTreeNode(parent.right().getAttrs(), parent.right().key(), parent.right().value(), parent.right().left(), parent.right().right()); + return new BlackTreeNode(parent.getAttrs(), parent.key(), parent.value(), this, rightNode); + } } + + private ColorlessTreeNode rebuildFive(ColorlessTreeNode parent, Rotate side) { + if (side == Rotate.R) { // rotate Left + ColorlessTreeNode leftChild = new RedTreeNode(parent.left().getAttrs(), parent.left().key(), parent.left().value(), parent.left().left(), parent.left().right().left()); + ColorlessTreeNode rightChild = parent.left().right().right(); + ColorlessTreeNode leftSubTreeRoot = new BlackTreeNode(parent.left().right().getAttrs(), parent.left().right().key(), parent.left().right().value(), leftChild, rightChild); + ColorlessTreeNode newParent = parent.createNode(parent.getAttrs(), parent.key(), parent.value(), leftSubTreeRoot, this); + return this.rebuildSix(newParent, Rotate.R); + } else { // rotate Right + ColorlessTreeNode leftChild = parent.right().left().left(); + ColorlessTreeNode rightChild = new RedTreeNode(parent.right().getAttrs(), parent.right().key(), parent.right().value(), parent.right().left().right(), parent.right().right()); + ColorlessTreeNode rightSubTreeRoot = new BlackTreeNode(parent.right().left().getAttrs(), parent.right().left().key(), parent.right().left().value(), leftChild, rightChild); + ColorlessTreeNode newParent = parent.createNode(parent.getAttrs(), parent.key(), parent.value(), this, rightSubTreeRoot); + return this.rebuildSix(newParent, Rotate.L); + } + } + + private ColorlessTreeNode rebuildSix(ColorlessTreeNode parent, Rotate side) { + if (side == Rotate.L) { // rotate Left + ColorlessTreeNode leftChild = parent.right().createNode(parent.getAttrs(), parent.key(), parent.value(), this, parent.right().left()); //check + ColorlessTreeNode rightChild = new BlackTreeNode(parent.right().right().getAttrs(), parent.right().right().key(), parent.right().right().value(), parent.right().right().left(), parent.right().right().right()); + return parent.createNode(parent.right().getAttrs(), parent.right().key(), parent.right().value(), leftChild, rightChild); + } else { // rotate Right + ColorlessTreeNode leftChild = new BlackTreeNode(parent.left().left().getAttrs(), parent.left().left().key(), parent.left().left().value(), parent.left().left().left(), parent.left().left().right()); + ColorlessTreeNode rightChild = parent.left().createNode(parent.getAttrs(), parent.key(), parent.value(), parent.left().right(), this); + return parent.createNode(parent.left().getAttrs(), parent.left().key(), parent.left().value(), leftChild, rightChild); + } + + } + + public RebuildNode deleteSubTreeMaxNode(ColorlessTreeNode parent, Rotate side) { + RebuildNode rebuildNode; + ColorlessTreeNode node; + if (!right().empty()) {//最大値のノードが取得できるまで潜る + rebuildNode = right().deleteSubTreeMaxNode(this, Rotate.R); + } else { + rebuildNode = this.replaceNode(parent); + } + if (parent == null) + return rebuildNode; + + if (rebuildNode.rebuild()) { + node = rebuildNode.getNode(); + return node.deleteBalance(parent); + } + if (side == Rotate.R) + node = parent.createNode(parent.getAttrs(), parent.key(), parent.value(), parent.left(), rebuildNode.getNode()); + else + node = parent.createNode(parent.getAttrs(), parent.key(), parent.value(), rebuildNode.getNode(), parent.right()); + return new RebuildNode(false, node); + } + + protected abstract RebuildNode deleteNode(); + + public abstract ColorlessTreeNode createNode(TreeMap<String, ByteBuffer> newAttrs, String insertKey, ByteBuffer insertValue, ColorlessTreeNode left, ColorlessTreeNode right); + + public abstract boolean isRed(); + + public abstract boolean empty(); + + protected abstract RebuildNode replaceNode(ColorlessTreeNode parent); + + protected abstract ColorlessTreeNode insBalance(); + + public abstract Rotate checkRotate(Rotate side); + }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/EmptyTreeNode.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/EmptyTreeNode.java Thu Jan 05 09:49:20 2017 +0900 @@ -17,14 +17,18 @@ super(null, null, null, null, null); } - @Override - public RedBlackTreeNodeChildren getChildren() { - return new RedBlackTreeNodeChildren(this, null); + public EmptyTreeNode(ByteBuffer value) { + super(null, null, value, null, null); } @Override - public RedBlackTreeNodeAttribute getAttributes() { - return null; //使わない + public ColorlessTreeNode left() { + return new EmptyTreeNode(); + } + + @Override + public ColorlessTreeNode right() { + return new EmptyTreeNode(); } @Override @@ -33,6 +37,11 @@ } @Override + protected RebuildNode deleteNode() { + return new RebuildNode(false, this); + } + + @Override public Either<Error, TreeNode> appendRootNode() { return null; } @@ -84,4 +93,10 @@ Assert.assertTrue(count <= 2 * minCount); return minCount; } + + @Override + protected RebuildNode replaceNode(ColorlessTreeNode parent) { + return new RebuildNode(false, this); + } + }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeAttribute.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeAttribute.java Thu Jan 05 09:49:20 2017 +0900 @@ -38,7 +38,7 @@ @Override public ByteBuffer get(String key) { - if (key == null) { + if (key == null || balanceKey == null) { return null; } if (key.equals(balanceKey))
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java Thu Jan 05 09:49:20 2017 +0900 @@ -1,7 +1,6 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; -import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.Rotate; -import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.*; import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.NodeEditorError; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeChildren; @@ -13,6 +12,7 @@ import java.util.Iterator; import static jp.ac.u_ryukyu.ie.cr.jungle.util.Error.JungleTreeError.INVALID_ARGUMENT; +import static jp.ac.u_ryukyu.ie.cr.jungle.util.Error.TreeEditorError.DELETE_VALUE_NOT_FOUND; /** * Created by e115731 on 2017/01/03. @@ -64,7 +64,13 @@ if (value == null) return DefaultEither.newA(INVALID_ARGUMENT); RebuildNode newNode = node.delete(key, value, null, Rotate.N); - return null; + if (newNode == null) + return DefaultEither.newA(DELETE_VALUE_NOT_FOUND); // 削除するノードが無かった場合 + ColorlessTreeNode root = newNode.getNode(); + if (root.empty()) + return DefaultEither.newB(new EmptyTreeNode()); + ColorlessTreeNode newRoot = new BlackTreeNode(root.getAttrs(),root.key(), root.value(), root.left(), root.right()); + return DefaultEither.newB(newRoot); }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedTreeNode.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedTreeNode.java Thu Jan 05 09:49:20 2017 +0900 @@ -23,18 +23,14 @@ } @Override - public RedBlackTreeNodeChildren getChildren() { - return new RedBlackTreeNodeChildren(this, getAttrs()); - } - - @Override public ColorlessTreeNode createNode(TreeMap<String, ByteBuffer> newAttrs, String insertKey, ByteBuffer insertValue, ColorlessTreeNode left, ColorlessTreeNode right) { return new RedTreeNode(newAttrs, insertKey, insertValue, left, right); } @Override - public RedBlackTreeNodeAttribute getAttributes() { - return new RedBlackTreeNodeAttribute(left(), right(), getAttrs(), key(), value()); + protected RebuildNode deleteNode() { + ColorlessTreeNode emptyNode = new EmptyTreeNode(value()); + return new RebuildNode(false, emptyNode); } @Override @@ -81,16 +77,14 @@ if (side == Rotate.L) { if (left().isRed()) return Rotate.R; - else - if (right().isRed()) - return Rotate.LR; + else if (right().isRed()) + return Rotate.LR; return Rotate.N; } else { if (left().isRed()) return Rotate.RL; - else - if (right().isRed()) - return Rotate.L; + else if (right().isRed()) + return Rotate.L; return Rotate.N; } } @@ -105,4 +99,47 @@ return minCount; } + @Override + protected RebuildNode replaceNode(ColorlessTreeNode parent) { + ColorlessTreeNode newNode; + if (this.left().empty() && this.right().empty()) { //自身を削除する + return deleteNode(); + } else if (!this.left().empty() && this.right().empty()) { //左の部分木を昇格させる + newNode = left().createNode(left().getAttrs(), left().key(), left().value(), left().left(), left().right()); + return new RebuildNode(false, newNode); + } else if (this.left().empty() && !this.right().empty()) { //右の部分木を昇格させる + newNode = right().createNode(right().getAttrs(), right().key(), right().value(), right().left(), right().right()); + return new RebuildNode(false, newNode); + } else {//子ノードが左右にある場合 + //左の部分木の最大の値を持つNodeと自身を置き換える + ColorlessTreeNode cur = this.left(); + + while (!cur.right().empty()) { + cur = cur.right(); + } + if (!this.left().right().empty()) { + RebuildNode leftSubTreeNodeRebuildNode = this.left().deleteSubTreeMaxNode(null, Rotate.L); + if (leftSubTreeNodeRebuildNode.rebuild()) { + ColorlessTreeNode node = leftSubTreeNodeRebuildNode.getNode(); + ColorlessTreeNode newParent = createNode(cur.getAttrs(), cur.key(), cur.value(), node, this.right()); + return node.deleteBalance(newParent); + } + ColorlessTreeNode leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode(); + newNode = createNode(cur.getAttrs(), cur.key(), cur.value(), leftSubTreeNode, this.right()); + return new RebuildNode(false, newNode); + } else { + RebuildNode leftSubTreeNodeRebuildNode = this.left().replaceNode(this); + if (leftSubTreeNodeRebuildNode.rebuild()) { + ColorlessTreeNode node = leftSubTreeNodeRebuildNode.getNode(); + ColorlessTreeNode newParent = createNode(this.left().getAttrs(), this.left().key(), this.left().value(), node, this.right()); + return node.deleteBalance(newParent); + } + ColorlessTreeNode leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode(); + newNode = createNode(cur.getAttrs(),cur.key(), cur.value(), leftSubTreeNode, this.right()); + return new RebuildNode(false, newNode); + } + + } + } + }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/util/Error/TreeEditorError.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/util/Error/TreeEditorError.java Thu Jan 05 09:49:20 2017 +0900 @@ -9,5 +9,5 @@ public static final Error CAS_MISS = new DefaultError(); public static final Error APPENDED_NODE_NULL = new DefaultError(); public static final Error SET_APPENDEDNODE_ERROR= new DefaultError(); - + public static final Error DELETE_VALUE_NOT_FOUND = new DefaultError(); }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorTest.java Wed Jan 04 20:03:41 2017 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorTest.java Thu Jan 05 09:49:20 2017 +0900 @@ -22,14 +22,28 @@ public class RedBlackTreeEditorTest { + int testCount = 5000; + @Test public void RedBlackTreeEditor() { + + ByteBuffer b5 = ByteBuffer.wrap(("value" + 5).getBytes()); + ByteBuffer b6 = ByteBuffer.wrap(("value" + 6).getBytes()); + ByteBuffer b12 = ByteBuffer.wrap(("value" + 12).getBytes()); + ByteBuffer b8 = ByteBuffer.wrap(("value" + 8).getBytes()); + + long h5 = b5.hashCode(); + long h6 = b6.hashCode(); + long h12 = b12.hashCode(); + long result1 = h6 - h12; + long result2 = h5 - h12; + String key = "balanceKey"; Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser()); JungleTree tree = jungle.createNewRedBlackTree("TreeName", "balanceKey"); NodePath path = new DefaultNodePath(); - for (int count = 1; count <= 1000; count++) { + for (int count = 1; count <= testCount; count++) { JungleTreeEditor editor = tree.getJungleTreeEditor(); ByteBuffer value = ByteBuffer.wrap(("value" + count).getBytes()); Either<Error, JungleTreeEditor> either = editor.addNewChildAndPutAttribute(path, 0, key, value); @@ -42,7 +56,7 @@ JungleNodeIterator iterator = new JungleNodeIterator(rootNode); int nodeCount = 0; List<String> list = new LinkedList<>(); - for (int i = 1; i <= count ; i ++) { + for (int i = 1; i <= count; i++) { list.add(("value" + i)); } @@ -56,15 +70,73 @@ list.remove(index); } - Assert.assertEquals(list.size(),0); + Assert.assertEquals(list.size(), 0); int expectCount = count; Assert.assertEquals(expectCount, nodeCount); - ColorlessTreeNode rootNode2 = (ColorlessTreeNode)rootNode; //test用methodを使うためにcastしている - rootNode2.checkDepth(0,0); + ColorlessTreeNode rootNode2 = (ColorlessTreeNode) rootNode; //test用methodを使うためにcastしている + rootNode2.checkDepth(0, 0); } - JungleTreeEditor editor = tree.getJungleTreeEditor(); - editor.deleteChildAt(path,0); + System.out.println("------------------------------------------- delete -----------------------------------------------------------------------------------"); + for (int count = 1; count <= testCount; count++) { + System.out.println(count + "回目------------------------------------------------------------------------------------------------------------------------"); + + ColorlessTreeNode rootNode = (ColorlessTreeNode) tree.getRootNode(); + JungleNodeIterator iterator = new JungleNodeIterator(rootNode); + int nodeCount = 0; + + if (count == 2) + System.out.println("やばい"); + System.out.println("------------------------------------------------delete 前------------------------------------------------------------------------"); + while (iterator.hasNext() && rootNode.getAttributes().get(key) != null) { + ColorlessTreeNode node = (ColorlessTreeNode) iterator.next(); + if (node.empty()) + System.out.println(node.empty()); + if (node.key() == null) + System.out.println("これはやばいですよ"); + ByteBuffer seach = node.getAttributes().get(key); + int test = seach.hashCode(); + String seachStr = node.getAttributes().getString(key); + System.out.println(seachStr); + Assert.assertTrue(rootNode.get(seach)); + nodeCount++; + } + + + if (count == 2) + System.out.println("やばい"); + JungleTreeEditor editor = tree.getJungleTreeEditor(); + ByteBuffer value = ByteBuffer.wrap(("value" + count).getBytes()); + Either<Error, JungleTreeEditor> either = editor.deleteChildAt(path, 0, key, value); + Assert.assertFalse(either.isA()); + editor = either.b(); + either = editor.success(); + Assert.assertFalse(either.isA()); + + System.out.println("------------------------------------------------delete 後------------------------------------------------------------------------"); + rootNode = (ColorlessTreeNode) tree.getRootNode(); + iterator = new JungleNodeIterator(rootNode); + nodeCount = 0; + + while (iterator.hasNext() && rootNode.getAttributes().get(key) != null) { + ColorlessTreeNode node = (ColorlessTreeNode) iterator.next(); + if (node.empty()) + System.out.println(node.empty()); + if (node.key() == null) + System.out.println("これはやばいですよ"); + System.out.println(node.getAttributes().getString(key)); + ByteBuffer seach = node.getAttributes().get(key); + int test = seach.hashCode(); + String seachStr= node.getAttributes().getString(key); + Assert.assertTrue(rootNode.get(seach)); + nodeCount++; + } + + int expectCount = testCount - count; + Assert.assertEquals(expectCount, nodeCount); + } + + } }