Mercurial > hg > Members > shoshi > AADS

comparison src/tree/AVLTreeMap.java @ 0:a9cb12a7f995

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
hg init
author misaka
date Wed, 06 Jul 2011 15:19:52 +0900
parents
children 15920e9b562d
comparison
equal deleted inserted replaced
-1:000000000000 0:a9cb12a7f995
1 package tree;
2
3 import java.util.LinkedList;
4 import java.util.Random;
5
6 public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V>
7 {
8 private Node<K,V> root;
9 private final Node<K,V> NULL_NODE = new Node<K,V>(null,null,-1,-1,null,null);
10
11 public static void main(String args[])
12 {
13 AVLTreeMap<Integer,String> map = new AVLTreeMap<Integer,String>();
14
15 Random r = new Random();
16 LinkedList<Integer> keys = new LinkedList<Integer>();
17 for(int i = 0;i < 30000;i ++){
18 int num = r.nextInt();
19 keys.add(num);
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 }
32
33 public AVLTreeMap()
34 {
35 root = null;
36 }
37
38 @Override
39 public void put(K key,V value)
40 {
41 if(root == null){
42 root = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
43 return;
44 }
45
46 root = _put(root,key,value);
47 }
48
49 public Node<K,V> _put(Node<K,V> cur,K key,V value)
50 {
51 int result = cur.key.compareTo(key);
52
53 if(result < 0){
54 //right
55 if(cur.right == NULL_NODE){
56 cur.right = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
57 cur.rdepth = 1;
58 return cur;
59 }
60
61 cur.right = _put(cur.right,key,value);
62 cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth);
63 int diff = cur.rdepth - cur.ldepth;
64
65 if(diff > 1){
66 //一重回転か二重回転か判断する。
67 //以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。
68 int rottype = result * cur.right.key.compareTo(key);
69 if(rottype > 0){
70 return singleRotate(cur,OP_RIGHT);
71 }else{
72 return doubleRotate(cur,OP_RIGHTLEFT);
73 }
74 }
75
76 }else if(result > 0){
77 //left
78 if(cur.left == NULL_NODE){
79 cur.left = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
80 cur.ldepth = 1;
81 return cur;
82 }
83
84 cur.left = _put(cur.left,key,value);
85 cur.ldepth = Math.max(cur.left.ldepth,cur.left.rdepth) + 1;
86 int diff = cur.ldepth - cur.rdepth;
87
88 if(diff > 1){
89 //一重回転か二重回転か判断する。
90 //以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。
91 int rottype = result * cur.left.key.compareTo(key);
92 if(rottype > 0){
93 return singleRotate(cur,OP_LEFT);
94 }else{
95 return doubleRotate(cur,OP_LEFTRIGHT);
96 }
97 }
98 }else{
99 //find
100 cur.value = value;
101 }
102
103 return cur;
104 }
105
106 private static final int OP_LEFT = 1;
107 private static final int OP_RIGHT = 2;
108
109 public Node<K,V> singleRotate(Node<K,V> target,int type)
110 {
111 switch(type){
112 case OP_LEFT:
113 Node<K,V> left = target.left;
114 target.left = left.right;
115 left.right = target;
116
117 target.ldepth = Math.max(target.left.rdepth,target.left.ldepth) + 1;
118 left.rdepth = Math.max(left.right.rdepth,left.right.ldepth) + 1;
119 return left;
120 case OP_RIGHT:
121 Node<K,V> right = target.right;
122 target.right = right.left;
123 right.left = target;
124
125 target.rdepth = Math.max(target.right.rdepth,target.right.ldepth) + 1;
126 right.ldepth = Math.max(right.left.ldepth,right.left.rdepth) + 1;
127 return right;
128 default:
129 throw new IllegalArgumentException("invalid rotation type");
130 }
131 }
132
133 private static final int OP_LEFTRIGHT = 1;
134 private static final int OP_RIGHTLEFT = 2;
135
136 public Node<K,V> doubleRotate(Node<K,V> target,int type)
137 {
138 switch(type){
139 case OP_LEFTRIGHT:
140 target.left = singleRotate(target.left,OP_RIGHT);
141 return singleRotate(target,OP_LEFT);
142 case OP_RIGHTLEFT:
143 target.right = singleRotate(target.right,OP_LEFT);
144 return singleRotate(target,OP_RIGHT);
145 default:
146 throw new IllegalArgumentException("invalid rotation type.");
147 }
148 }
149
150 @Override
151 public V get(K key)
152 {
153 Node<K,V> cur = root;
154
155 while(cur != NULL_NODE){
156 int result = cur.key.compareTo(key);
157 if(result < 0){
158 cur = cur.right;
159 }else if(result > 0){
160 cur = cur.left;
161 }else{
162 //find
163 break;
164 }
165 }
166
167 return cur.value;
168 }
169
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>
182 {
183 K key;
184 V value;
185
186 Node<K,V> left;
187 Node<K,V> right;
188
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)
193 {
194 this.key = key;
195 this.value = value;
196 this.ldepth = ldepth;
197 this.rdepth = rdepth;
198 this.left = left;
199 this.right = right;
200 }
201
202 @Override
203 public String toString()
204 {
205 return "[" + key + ":" + value + "]";
206 }
207 }
208 }