Mercurial > hg > Members > tatsuki > TreeMap

comparison src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java @ 18:a02ce8467bad

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
refactoring
author tatsuki
date Tue, 28 Apr 2015 18:12:57 +0900
parents ab026848665a
children 3d9be68ef707
comparison
equal deleted inserted replaced
17:ab026848665a 18:a02ce8467bad
86 * @param parent 86 * @param parent
87 * @return 87 * @return
88 */ 88 */
89 @Override 89 @Override
90 public Node replaceNode(Node<K, V> parent) throws RotateParent { 90 public Node replaceNode(Node<K, V> parent) throws RotateParent {
91
92 Node<K, V> newNode = null; 91 Node<K, V> newNode = null;
93 if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する 92 if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する
94 return deleteNode();//黒が1つ減るので木のバランスを取る 93 return deleteNode();//黒が1つ減るので木のバランスを取る
95 } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる 94 } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる
96 newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right()); 95 newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right());
124 leftSubTreeNode = this.left().replaceNode(this);//右の子がいなかった場合、左の子を昇格させるだけで良い。 123 leftSubTreeNode = this.left().replaceNode(this);//右の子がいなかった場合、左の子を昇格させるだけで良い。
125 Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); 124 Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
126 return newParent; 125 return newParent;
127 } catch (RotateParent e) { 126 } catch (RotateParent e) {
128 Node node = e.getParent(); 127 Node node = e.getParent();
129 //if (parent != null) {
130 Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right()); 128 Node newParent = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
131 return node.deleteBalance(newParent); 129 return node.deleteBalance(newParent);
132 // }
133 // return node;
134 } 130 }
135 } 131 }
136 } 132 }
137
138 } 133 }
139
140 } 134 }