Mercurial > hg > Members > shoshi > AADS

comparison src/tree/AVLTreeMap.java @ 3:24613dfbaeab default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
finished implementing AVL-Tree remove operation
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Wed, 10 Aug 2011 23:35:57 +0900
parents 36f2373f867b
children
comparison
equal deleted inserted replaced
2:36f2373f867b 3:24613dfbaeab
108 return new RemoveResult<K,V>(_cur,NULL_NODE); 108 return new RemoveResult<K,V>(_cur,NULL_NODE);
109 } 109 }
110 110
111 RemoveResult<K,V> r = removeTarget(_cur.right,_key); 111 RemoveResult<K,V> r = removeTarget(_cur.right,_key);
112 _cur.right = r.cur; 112 _cur.right = r.cur;
113 r.cur = _cur;
113 _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1; 114 _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1;
114 115
115 //要素の削除では，部分木の要素が減ったと考えるのではなく，もう片方の部分木の要素が増えたと考えれば書きやすい 116 //要素の削除では，部分木の要素が減ったと考えるのではなく，もう片方の部分木の要素が増えたと考えれば書きやすい
116 int diff = _cur.ldepth - _cur.rdepth; 117 int diff = _cur.ldepth - _cur.rdepth;
117 if(diff > 1){ 118 if(diff > 1){
133 return new RemoveResult<K,V>(_cur,NULL_NODE); 134 return new RemoveResult<K,V>(_cur,NULL_NODE);
134 } 135 }
135 136
136 RemoveResult<K,V> r = removeTarget(_cur.right,_key); 137 RemoveResult<K,V> r = removeTarget(_cur.right,_key);
137 _cur.left = r.cur; 138 _cur.left = r.cur;
139 r.cur = _cur;
138 _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1; 140 _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1;
139 141
140 int diff = _cur.rdepth - _cur.ldepth; 142 int diff = _cur.rdepth - _cur.ldepth;
141 if(diff > 1){ 143 if(diff > 1){
142 //determine that rotation will be single or double 144 //determine that rotation will be single or double
152 154
153 //find. 155 //find.
154 156
155 //見つかったので，ノードの代わりのノードを検索する． 157 //見つかったので，ノードの代わりのノードを検索する．
156 RemoveResult<K,V> r = findNearestNode(_cur.left); 158 RemoveResult<K,V> r = findNearestNode(_cur.left);
157 if(r != null){ 159 if(r == null){
158 160 //左部分木は存在していない、そのため右部分木をかわりに配置する
159 } 161 r = new RemoveResult<K,V>(_cur,_cur.right);
160 162 }else{
161 //見つかった場合は自身を削除対象とする 163 //左部分木より代替ノードを取得した
162 164 r.removed = new Node<K,V>(_cur.key,_cur.value,0,0,NULL_NODE,NULL_NODE);
163 165 _cur.key = r.removed.key;
164 return null; 166 _cur.value = r.removed.value;
167 _cur.left = r.cur;
168 r.cur = _cur;
169
170 _cur.ldepth = Math.max(_cur.left.ldepth,_cur.left.rdepth) + 1;
171
172 int diff = _cur.rdepth - _cur.ldepth;
173 if(diff > 1){
174 Node<K,V> right = _cur.right;
175 int rottype = right.rdepth - right.ldepth;
176 if(rottype >= 0){
177 r.cur = singleRotate(_cur,OP_RIGHT);
178 }else{
179 r.cur = doubleRotate(_cur,OP_RIGHTLEFT);
180 }
181 }
182
183 r.removed = _cur;
184 }
185
186 return r;
165 } 187 }
166 188
167 public RemoveResult<K,V> findNearestNode(Node<K,V> _cur) 189 public RemoveResult<K,V> findNearestNode(Node<K,V> _cur)
168 { 190 {
169 if(_cur == NULL_NODE){ 191 if(_cur == NULL_NODE){
170 return null; 192 return null;
171 } 193 }
172 194
173 return null; 195 RemoveResult<K,V> r = findNearestNode(_cur.right);
196 if(r == null){
197 r = new RemoveResult<K,V>(_cur,_cur.left);
198 return r;
199 }
200 _cur.right = r.cur;
201 _cur.ldepth = Math.max(_cur.left.ldepth,_cur.left.rdepth) + 1;
202 r.cur = _cur;
203 int diff = _cur.rdepth - _cur.ldepth;
204
205 if(diff > 1){
206 Node<K,V> left = _cur.left;
207 int rottype = left.ldepth - left.rdepth;
208 if(rottype >= 0){
209 r.cur = singleRotate(_cur,OP_LEFT);
210 }else{
211 r.cur = doubleRotate(_cur,OP_LEFTRIGHT);
212 }
213 }
214
215 return r;
174 } 216 }
175 217
176 public static class RemoveResult<K,V> 218 public static class RemoveResult<K,V>
177 { 219 {
178 public Node<K,V> removed; 220 public Node<K,V> removed;