Mercurial > hg > Members > shoshi > AADS

comparison src/tree/AVLTreeMap.java @ 2:36f2373f867b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added AVLTree.java remove operation
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Wed, 10 Aug 2011 20:14:19 +0900
parents 15920e9b562d
children 24613dfbaeab
comparison
equal deleted inserted replaced
1:15920e9b562d 2:36f2373f867b
9 { 9 {
10 AVLTreeMap<Integer,String> map = new AVLTreeMap<Integer,String>(); 10 AVLTreeMap<Integer,String> map = new AVLTreeMap<Integer,String>();
11 11
12 map.put(10,"10"); 12 map.put(10,"10");
13 map.put(20,"20"); 13 map.put(20,"20");
14 map.put(30,"20"); 14 map.put(30,"30");
15 map.put(5,"5"); 15 map.put(5,"5");
16 map.put(7,"7"); 16 map.put(7,"7");
17
18 map.remove(20);
17 } 19 }
18 20
19 public AVLTreeMap() 21 public AVLTreeMap()
20 { 22 {
21 root = null; 23 root = null;
86 } 88 }
87 89
88 return cur; 90 return cur;
89 } 91 }
90 92
91 public V remove(K key) 93 public V remove(K _key)
92 { 94 {
93 RemoveResult<K,V> r = findRemoveTarget(root,key); 95 RemoveResult<K,V> r = removeTarget(root,_key);
94 root = r.cur; 96 root = r.cur;
95 return r.target.value; 97 return r.removed.value;
96 } 98 }
97 99
98 private RemoveResult<K,V> findRemoveTarget(Node<K,V> cur,K key) 100 private RemoveResult<K,V> removeTarget(Node<K,V> _cur,K _key)
99 { 101 {
100 int result = cur.key.compareTo(key); 102 int result = _cur.key.compareTo(_key);
103
101 if(result < 0){ 104 if(result < 0){
102 //right 105 //right
103 if(cur == NULL_NODE){ 106 if(_cur.right == NULL_NODE){
104 return new RemoveResult<K,V>(cur,NULL_NODE); 107 //not found
105 } 108 return new RemoveResult<K,V>(_cur,NULL_NODE);
106 109 }
107 RemoveResult<K,V> r = findRemoveTarget(cur.right,key); 110
108 cur.right = r.cur; 111 RemoveResult<K,V> r = removeTarget(_cur.right,_key);
109 cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth) + 1; 112 _cur.right = r.cur;
110 113 _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1;
111 int diff = cur.rdepth - cur.ldepth; 114
112 if(diff > 1){ 115 //要素の削除では，部分木の要素が減ったと考えるのではなく，もう片方の部分木の要素が増えたと考えれば書きやすい
113 int rottype = result * cur.right.key.compareTo(key); 116 int diff = _cur.ldepth - _cur.rdepth;
114 if(rottype > 0){ 117 if(diff > 1){
115 r.cur = singleRotate(cur,OP_RIGHT); 118 //determine that rotation will be single or double
116 return r; 119 Node<K,V> left = _cur.left;
117 }else{ 120 int rottype = left.ldepth - left.rdepth;
118 r.cur = doubleRotate(cur,OP_RIGHTLEFT); 121 if(rottype >= 0){
119 return r; 122 r.cur = singleRotate(_cur,OP_LEFT);
120 } 123 }else{
121 } 124 r.cur = doubleRotate(_cur,OP_LEFTRIGHT);
122 125 }
123 r.cur = cur; 126 }
127
124 return r; 128 return r;
125 }else if(result > 0 ){ 129 }else if(result > 0){
126 //left 130 //left
127 if(cur == NULL_NODE){ 131 if(_cur.left == NULL_NODE){
128 return new RemoveResult<K,V>(cur,NULL_NODE); 132 //not found
129 } 133 return new RemoveResult<K,V>(_cur,NULL_NODE);
130 134 }
131 RemoveResult<K,V> r = findRemoveTarget(cur.left,key); 135
132 cur.left = r.cur; 136 RemoveResult<K,V> r = removeTarget(_cur.right,_key);
133 cur.ldepth = Math.max(cur.left.rdepth,cur.left.ldepth) + 1; 137 _cur.left = r.cur;
134 138 _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1;
135 int diff = cur.rdepth - cur.ldepth; 139
136 if(diff > 1){ 140 int diff = _cur.rdepth - _cur.ldepth;
137 int rottype = result * cur.left.key.compareTo(key); 141 if(diff > 1){
138 if(rottype > 0){ 142 //determine that rotation will be single or double
139 r.cur = singleRotate(cur,OP_LEFT); 143 Node<K,V> right = _cur.right;
140 return r; 144 int rottype = right.rdepth - right.ldepth;
141 }else{ 145 if(rottype >= 0){
142 r.cur = doubleRotate(cur,OP_LEFTRIGHT); 146 r.cur = singleRotate(_cur,OP_RIGHT);
143 return r; 147 }else{
144 } 148 r.cur = doubleRotate(_cur,OP_RIGHTLEFT);
145 } 149 }
146 150 }
147 r.cur = cur; 151 }
148 return r; 152
149 }else{ 153 //find.
150 //find 154
151 if(cur.left == NULL_NODE && cur.right == NULL_NODE){ 155 //見つかったので，ノードの代わりのノードを検索する．
152 //delete 156 RemoveResult<K,V> r = findNearestNode(_cur.left);
153 return new RemoveResult<K,V>(NULL_NODE,cur); 157 if(r != null){
154 } 158
155 159 }
156 if(cur.left != NULL_NODE && cur.right == NULL_NODE){ 160
157 //replace left 161 //見つかった場合は自身を削除対象とする
158 return new RemoveResult<K,V>(cur.left,cur); 162
159 } 163
160 164 return null;
161 if(cur.left == NULL_NODE && cur.right != NULL_NODE){ 165 }
162 //replace right 166
163 return new RemoveResult<K,V>(cur.right,cur); 167 public RemoveResult<K,V> findNearestNode(Node<K,V> _cur)
164 } 168 {
165 169 if(_cur == NULL_NODE){
166 //both nodes are not null 170 return null;
167 RemoveResult<K,V> r = findSubstituteNode(cur.left); 171 }
168 cur.key = r.target.key; 172
169 cur.value = r.target.value; 173 return null;
170 cur.right = r.cur; 174 }
171 cur.rdepth = Math.max(cur.ldepth,cur.rdepth) + 1; 175
172 176 public static class RemoveResult<K,V>
173 int diff = cur.rdepth - cur.ldepth; 177 {
174 if(diff > 1){ 178 public Node<K,V> removed;
175 r.cur = doubleRotate(cur,OP_LEFTRIGHT); 179 public Node<K,V> cur;
176 } 180
177 181 public RemoveResult(Node<K,V> _removed,Node<K,V> _cur)
178 return r;
179 }
180 }
181
182 private RemoveResult<K,V> findSubstituteNode(Node<K,V> cur)
183 {
184 if(cur.right != NULL_NODE){
185 RemoveResult<K,V> result = findSubstituteNode(cur.right);
186 cur.right = result.cur;
187 cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth) + 1;
188
189 int diff = cur.ldepth - cur.rdepth;
190 if(diff > 1){
191 result.cur = singleRotate(cur.left,OP_LEFT);
192 return result;
193 }
194
195 result.cur = cur;
196 return result;
197 }
198
199 RemoveResult<K,V> result = new RemoveResult<K,V>(cur.left,cur);
200 return result;
201 }
202
203 private static class RemoveResult<K,V>
204 {
205 Node<K,V> cur;
206 Node<K,V> target;
207
208 public RemoveResult(Node<K,V> cur,Node<K,V> target)
209 { 182 {
210 this.cur = cur; 183 removed = _removed;
211 this.target = target; 184 cur = _cur;
212 } 185 }
213 } 186 }
214 187
215 private static final int OP_LEFT = 1; 188 private static final int OP_LEFT = 1;
216 private static final int OP_RIGHT = 2; 189 private static final int OP_RIGHT = 2;