Mercurial > hg > Members > tatsuki > TreeMap
changeset 18:a02ce8467bad
refactoring
| author | tatsuki |
|---|---|
| date | Tue, 28 Apr 2015 18:12:57 +0900 |
| parents | ab026848665a |
| children | fae4951660b4 |
| 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/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 | 4 files changed, 11 insertions(+), 43 deletions(-) [+] |
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java Mon Apr 27 23:08:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java Tue Apr 28 18:12:57 2015 +0900 @@ -88,7 +88,6 @@ */ @Override public Node replaceNode(Node<K, V> parent) throws RotateParent { - Node<K, V> newNode = null; if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する return deleteNode();//黒が1つ減るので木のバランスを取る @@ -126,15 +125,10 @@ return newParent; } catch (RotateParent e) { Node node = e.getParent(); - //if (parent != null) { Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); return node.deleteBalance(newParent); - // } - // return node; } } } - } - }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java Mon Apr 27 23:08:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java Tue Apr 28 18:12:57 2015 +0900 @@ -107,7 +107,6 @@ return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node); else return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right()); - } if (side == Rotate.L) return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right()); @@ -126,26 +125,17 @@ public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent, Rotate side) throws RotateParent { Node<K, V> node; - if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る - try { + try { + if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る node = right().deleteSubTreeMaxNode(this, Rotate.R); - // return node; - } catch (RotateParent e) { - node = e.getParent(); - if (parent == null) - throw e; - return node.deleteBalance(parent); + } else { + node = this.replaceNode(parent); } - } else { - try { - node = this.replaceNode(parent); - // return node; - } catch (RotateParent e) { - node = e.getParent(); - if (parent == null) - throw e; - return node.deleteBalance(parent); - } + } catch (RotateParent e) { + node = e.getParent(); + if (parent == null) + throw e; + return node.deleteBalance(parent); } if (parent == null) return node;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java Mon Apr 27 23:08:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java Tue Apr 28 18:12:57 2015 +0900 @@ -36,26 +36,19 @@ @Override Rotate checkRotate(Rotate side) { - if (side == L) { if (left.isRed()) return R; - else if (right.isRed()) return LR; - return N; } else { - if (left.isRed()) return RL; - else if (right.isRed()) return L; - return N; } - } @Override @@ -65,19 +58,15 @@ @Override public Node replaceNode(Node<K, V> parent) throws RotateParent { - Node<K, V> newNode = null; if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する return deleteNode(); - } 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().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right()); return newNode; - } else {//子ノードが左右にある場合 //左の部分木の最大の値を持つNodeと自身を置き換える Node<K, V> cur = this.left(); @@ -85,9 +74,7 @@ while (cur.right().isNotEmpty()) { cur = cur.right(); } - Node leftSubTreeNode = null; - if (this.left().right().isNotEmpty()) { try { leftSubTreeNode = this.left().deleteSubTreeMaxNode(null,Rotate.L); @@ -105,11 +92,8 @@ return newNode; } catch (RotateParent e) { Node node = e.getParent(); - //if (parent != null) { Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); return node.deleteBalance(newParent); - // } - // return node; } }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java Mon Apr 27 23:08:57 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java Tue Apr 28 18:12:57 2015 +0900 @@ -14,12 +14,12 @@ public class TreeMapDelete { public static void main(String args[]) throws RotateParent { TreeMap<Integer, Integer> map = new TreeMap(); - for (int count = 1; count < 10000; count++) { + for (int count = 1; count < 3000; count++) { map = map.put(count, count); } ArrayList<Integer> list = new ArrayList(); - for (int i = 1; i < 10000; i++) { + for (int i = 1; i < 3000; i++) { list.add(i); }