Mercurial > hg > Members > shoshi > AADS

comparison src/tree/AVLTreeMap.java @ 1:15920e9b562d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added MulticastQueue.java the BlockingMulticastQueue
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Tue, 09 Aug 2011 11:13:36 +0900
parents a9cb12a7f995
children 36f2373f867b
comparison
equal deleted inserted replaced
0:a9cb12a7f995 1:15920e9b562d
1 package tree; 1 package tree;
2
3 import java.util.LinkedList;
4 import java.util.Random;
5 2
6 public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V> 3 public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V>
7 { 4 {
8 private Node<K,V> root; 5 private Node<K,V> root;
9 private final Node<K,V> NULL_NODE = new Node<K,V>(null,null,-1,-1,null,null); 6 private final Node<K,V> NULL_NODE = new Node<K,V>(null,null,-1,-1,null,null);
10 7
11 public static void main(String args[]) 8 public static void main(String args[])
12 { 9 {
13 AVLTreeMap<Integer,String> map = new AVLTreeMap<Integer,String>(); 10 AVLTreeMap<Integer,String> map = new AVLTreeMap<Integer,String>();
14 11
15 Random r = new Random(); 12 map.put(10,"10");
16 LinkedList<Integer> keys = new LinkedList<Integer>(); 13 map.put(20,"20");
17 for(int i = 0;i < 30000;i ++){ 14 map.put(30,"20");
18 int num = r.nextInt(); 15 map.put(5,"5");
19 keys.add(num); 16 map.put(7,"7");
20 map.put(num,Integer.toString(num));
21 }
22
23 for(Integer key : keys){
24 String value = map.get(key);
25 if(!key.toString().equals(value)){
26 System.out.println("gehoge");
27 }
28 }
29
30 System.out.println("hoge");
31 } 17 }
32 18
33 public AVLTreeMap() 19 public AVLTreeMap()
34 { 20 {
35 root = null; 21 root = null;
57 cur.rdepth = 1; 43 cur.rdepth = 1;
58 return cur; 44 return cur;
59 } 45 }
60 46
61 cur.right = _put(cur.right,key,value); 47 cur.right = _put(cur.right,key,value);
62 cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth); 48 cur.rdepth = Math.max(cur.right.ldepth,cur.right.rdepth) + 1;
63 int diff = cur.rdepth - cur.ldepth; 49 int diff = cur.rdepth - cur.ldepth;
64 50
65 if(diff > 1){ 51 if(diff > 1){
66 //一重回転か二重回転か判断する。 52 //一重回転か二重回転か判断する。
67 //以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。 53 //以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。
70 return singleRotate(cur,OP_RIGHT); 56 return singleRotate(cur,OP_RIGHT);
71 }else{ 57 }else{
72 return doubleRotate(cur,OP_RIGHTLEFT); 58 return doubleRotate(cur,OP_RIGHTLEFT);
73 } 59 }
74 } 60 }
75
76 }else if(result > 0){ 61 }else if(result > 0){
77 //left 62 //left
78 if(cur.left == NULL_NODE){ 63 if(cur.left == NULL_NODE){
79 cur.left = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE); 64 cur.left = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
80 cur.ldepth = 1; 65 cur.ldepth = 1;
99 //find 84 //find
100 cur.value = value; 85 cur.value = value;
101 } 86 }
102 87
103 return cur; 88 return cur;
89 }
90
91 public V remove(K key)
92 {
93 RemoveResult<K,V> r = findRemoveTarget(root,key);
94 root = r.cur;
95 return r.target.value;
96 }
97
98 private RemoveResult<K,V> findRemoveTarget(Node<K,V> cur,K key)
99 {
100 int result = cur.key.compareTo(key);
101 if(result < 0){
102 //right
103 if(cur == NULL_NODE){
104 return new RemoveResult<K,V>(cur,NULL_NODE);
105 }
106
107 RemoveResult<K,V> r = findRemoveTarget(cur.right,key);
108 cur.right = r.cur;
109 cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth) + 1;
110
111 int diff = cur.rdepth - cur.ldepth;
112 if(diff > 1){
113 int rottype = result * cur.right.key.compareTo(key);
114 if(rottype > 0){
115 r.cur = singleRotate(cur,OP_RIGHT);
116 return r;
117 }else{
118 r.cur = doubleRotate(cur,OP_RIGHTLEFT);
119 return r;
120 }
121 }
122
123 r.cur = cur;
124 return r;
125 }else if(result > 0 ){
126 //left
127 if(cur == NULL_NODE){
128 return new RemoveResult<K,V>(cur,NULL_NODE);
129 }
130
131 RemoveResult<K,V> r = findRemoveTarget(cur.left,key);
132 cur.left = r.cur;
133 cur.ldepth = Math.max(cur.left.rdepth,cur.left.ldepth) + 1;
134
135 int diff = cur.rdepth - cur.ldepth;
136 if(diff > 1){
137 int rottype = result * cur.left.key.compareTo(key);
138 if(rottype > 0){
139 r.cur = singleRotate(cur,OP_LEFT);
140 return r;
141 }else{
142 r.cur = doubleRotate(cur,OP_LEFTRIGHT);
143 return r;
144 }
145 }
146
147 r.cur = cur;
148 return r;
149 }else{
150 //find
151 if(cur.left == NULL_NODE && cur.right == NULL_NODE){
152 //delete
153 return new RemoveResult<K,V>(NULL_NODE,cur);
154 }
155
156 if(cur.left != NULL_NODE && cur.right == NULL_NODE){
157 //replace left
158 return new RemoveResult<K,V>(cur.left,cur);
159 }
160
161 if(cur.left == NULL_NODE && cur.right != NULL_NODE){
162 //replace right
163 return new RemoveResult<K,V>(cur.right,cur);
164 }
165
166 //both nodes are not null
167 RemoveResult<K,V> r = findSubstituteNode(cur.left);
168 cur.key = r.target.key;
169 cur.value = r.target.value;
170 cur.right = r.cur;
171 cur.rdepth = Math.max(cur.ldepth,cur.rdepth) + 1;
172
173 int diff = cur.rdepth - cur.ldepth;
174 if(diff > 1){
175 r.cur = doubleRotate(cur,OP_LEFTRIGHT);
176 }
177
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 {
210 this.cur = cur;
211 this.target = target;
212 }
104 } 213 }
105 214
106 private static final int OP_LEFT = 1; 215 private static final int OP_LEFT = 1;
107 private static final int OP_RIGHT = 2; 216 private static final int OP_RIGHT = 2;
108 217
165 } 274 }
166 275
167 return cur.value; 276 return cur.value;
168 } 277 }
169 278
170 @Override
171 public V remove(K key)
172 {
173
174 }
175
176 private Node<K,V> _remove(K key)
177 {
178
179 }
180
181 private static class Node<K,V> 279 private static class Node<K,V>
182 { 280 {
183 K key; 281 K key;
184 V value; 282 V value;
185 283
284 int rdepth;
285 int ldepth;
286
186 Node<K,V> left; 287 Node<K,V> left;
187 Node<K,V> right; 288 Node<K,V> right;
188 289
189 int ldepth;
190 int rdepth;
191
192 public Node(K key,V value,int rdepth,int ldepth,Node<K,V> left,Node<K,V> right) 290 public Node(K key,V value,int rdepth,int ldepth,Node<K,V> left,Node<K,V> right)
193 { 291 {
292 this.right = right;
293 this.left = left;
294 this.ldepth = ldepth;
295 this.rdepth = rdepth;
194 this.key = key; 296 this.key = key;
195 this.value = value; 297 this.value = value;
196 this.ldepth = ldepth;
197 this.rdepth = rdepth;
198 this.left = left;
199 this.right = right;
200 } 298 }
201 299
202 @Override 300 @Override
203 public String toString() 301 public String toString()
204 { 302 {