Download code

Jump to: navigation, search

Back to Red-black_tree_(Java)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

RBTree.java

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Red-black_tree_(Java)?oldid=19200
 14 */
 15 
 16 enum Color { RED, BLACK }
 17 
 18 class Node<K extends Comparable<? super K>,V>
 19 {
 20     public K key;
 21     public V value;
 22     public Node<K,V> left;
 23     public Node<K,V> right;
 24     public Node<K,V> parent;
 25     public Color color;
 26 
 27     public Node(K key, V value, Color nodeColor, Node<K,V> left, Node<K,V> right) {
 28         this.key = key;
 29         this.value = value;
 30         this.color = nodeColor;
 31         this.left = left;
 32         this.right = right;
 33         if (left  != null)  left.parent = this;
 34         if (right != null) right.parent = this;
 35         this.parent = null;
 36     }
 37     public Node<K,V> grandparent() {
 38         assert parent != null; // Not the root node
 39         assert parent.parent != null; // Not child of root
 40         return parent.parent;
 41     }
 42     public Node<K,V> sibling() {
 43         assert parent != null; // Root node has no sibling
 44         if (this == parent.left)
 45             return parent.right;
 46         else
 47             return parent.left;
 48     }
 49     public Node<K,V> uncle() {
 50         assert parent != null; // Root node has no uncle
 51         assert parent.parent != null; // Children of root have no uncle
 52         return parent.sibling();
 53     }
 54 }
 55 
 56 public class RBTree<K extends Comparable<? super K>,V>
 57 {
 58     public static final boolean VERIFY_RBTREE = true;
 59     private static final int INDENT_STEP = 4;
 60 
 61     public Node<K,V> root;
 62 
 63     public RBTree() {
 64         root = null;
 65         verifyProperties();
 66     }
 67     public void verifyProperties() {
 68         if (VERIFY_RBTREE) {
 69             verifyProperty1(root);
 70             verifyProperty2(root);
 71             // Property 3 is implicit
 72             verifyProperty4(root);
 73             verifyProperty5(root);
 74         }
 75     }
 76     private static void verifyProperty1(Node<?,?> n) {
 77         assert nodeColor(n) == Color.RED || nodeColor(n) == Color.BLACK;
 78         if (n == null) return;
 79         verifyProperty1(n.left);
 80         verifyProperty1(n.right);
 81     }
 82     private static void verifyProperty2(Node<?,?> root) {
 83         assert nodeColor(root) == Color.BLACK;
 84     }
 85     private static Color nodeColor(Node<?,?> n) {
 86         return n == null ? Color.BLACK : n.color;
 87     }
 88     private static void verifyProperty4(Node<?,?> n) {
 89         if (nodeColor(n) == Color.RED) {
 90             assert nodeColor(n.left)   == Color.BLACK;
 91             assert nodeColor(n.right)  == Color.BLACK;
 92             assert nodeColor(n.parent) == Color.BLACK;
 93         }
 94         if (n == null) return;
 95         verifyProperty4(n.left);
 96         verifyProperty4(n.right);
 97     }
 98     private static void verifyProperty5(Node<?,?> root) {
 99         verifyProperty5Helper(root, 0, -1);
100     }
101 
102     private static int verifyProperty5Helper(Node<?,?> n, int blackCount, int pathBlackCount) {
103         if (nodeColor(n) == Color.BLACK) {
104             blackCount++;
105         }
106         if (n == null) {
107             if (pathBlackCount == -1) {
108                 pathBlackCount = blackCount;
109             } else {
110                 assert blackCount == pathBlackCount;
111             }
112             return pathBlackCount;
113         }
114         pathBlackCount = verifyProperty5Helper(n.left,  blackCount, pathBlackCount);
115         pathBlackCount = verifyProperty5Helper(n.right, blackCount, pathBlackCount);
116         return pathBlackCount;
117     }
118     private Node<K,V> lookupNode(K key) {
119         Node<K,V> n = root;
120         while (n != null) {
121             int compResult = key.compareTo(n.key);
122             if (compResult == 0) {
123                 return n;
124             } else if (compResult < 0) {
125                 n = n.left;
126             } else {
127                 assert compResult > 0;
128                 n = n.right;
129             }
130         }
131         return n;
132     }
133     public V lookup(K key) {
134         Node<K,V> n = lookupNode(key);
135         return n == null ? null : n.value;
136     }
137     private void rotateLeft(Node<K,V> n) {
138         Node<K,V> r = n.right;
139         replaceNode(n, r);
140         n.right = r.left;
141         if (r.left != null) {
142             r.left.parent = n;
143         }
144         r.left = n;
145         n.parent = r;
146     }
147 
148     private void rotateRight(Node<K,V> n) {
149         Node<K,V> l = n.left;
150         replaceNode(n, l);
151         n.left = l.right;
152         if (l.right != null) {
153             l.right.parent = n;
154         }
155         l.right = n;
156         n.parent = l;
157     }
158     private void replaceNode(Node<K,V> oldn, Node<K,V> newn) {
159         if (oldn.parent == null) {
160             root = newn;
161         } else {
162             if (oldn == oldn.parent.left)
163                 oldn.parent.left = newn;
164             else
165                 oldn.parent.right = newn;
166         }
167         if (newn != null) {
168             newn.parent = oldn.parent;
169         }
170     }
171     public void insert(K key, V value) {
172         Node<K,V> insertedNode = new Node<K,V>(key, value, Color.RED, null, null);
173         if (root == null) {
174             root = insertedNode;
175         } else {
176             Node<K,V> n = root;
177             while (true) {
178                 int compResult = key.compareTo(n.key);
179                 if (compResult == 0) {
180                     n.value = value;
181                     return;
182                 } else if (compResult < 0) {
183                     if (n.left == null) {
184                         n.left = insertedNode;
185                         break;
186                     } else {
187                         n = n.left;
188                     }
189                 } else {
190                     assert compResult > 0;
191                     if (n.right == null) {
192                         n.right = insertedNode;
193                         break;
194                     } else {
195                         n = n.right;
196                     }
197                 }
198             }
199             insertedNode.parent = n;
200         }
201         insertCase1(insertedNode);
202         verifyProperties();
203     }
204     private void insertCase1(Node<K,V> n) {
205         if (n.parent == null)
206             n.color = Color.BLACK;
207         else
208             insertCase2(n);
209     }
210     private void insertCase2(Node<K,V> n) {
211         if (nodeColor(n.parent) == Color.BLACK)
212             return; // Tree is still valid
213         else
214             insertCase3(n);
215     }
216     void insertCase3(Node<K,V> n) {
217         if (nodeColor(n.uncle()) == Color.RED) {
218             n.parent.color = Color.BLACK;
219             n.uncle().color = Color.BLACK;
220             n.grandparent().color = Color.RED;
221             insertCase1(n.grandparent());
222         } else {
223             insertCase4(n);
224         }
225     }
226     void insertCase4(Node<K,V> n) {
227         if (n == n.parent.right && n.parent == n.grandparent().left) {
228             rotateLeft(n.parent);
229             n = n.left;
230         } else if (n == n.parent.left && n.parent == n.grandparent().right) {
231             rotateRight(n.parent);
232             n = n.right;
233         }
234         insertCase5(n);
235     }
236     void insertCase5(Node<K,V> n) {
237         n.parent.color = Color.BLACK;
238         n.grandparent().color = Color.RED;
239         if (n == n.parent.left && n.parent == n.grandparent().left) {
240             rotateRight(n.grandparent());
241         } else {
242             assert n == n.parent.right && n.parent == n.grandparent().right;
243             rotateLeft(n.grandparent());
244         }
245     }
246     public void delete(K key) {
247         Node<K,V> n = lookupNode(key);
248         if (n == null)
249             return;  // Key not found, do nothing
250         if (n.left != null && n.right != null) {
251             // Copy key/value from predecessor and then delete it instead
252             Node<K,V> pred = maximumNode(n.left);
253             n.key   = pred.key;
254             n.value = pred.value;
255             n = pred;
256         }
257 
258         assert n.left == null || n.right == null;
259         Node<K,V> child = (n.right == null) ? n.left : n.right;
260         if (nodeColor(n) == Color.BLACK) {
261             n.color = nodeColor(child);
262             deleteCase1(n);
263         }
264         replaceNode(n, child);
265 
266         verifyProperties();
267     }
268     private static <K extends Comparable<? super K>,V> Node<K,V> maximumNode(Node<K,V> n) {
269         assert n != null;
270         while (n.right != null) {
271             n = n.right;
272         }
273         return n;
274     }
275     private void deleteCase1(Node<K,V> n) {
276         if (n.parent == null)
277             return;
278         else
279             deleteCase2(n);
280     }
281     private void deleteCase2(Node<K,V> n) {
282         if (nodeColor(n.sibling()) == Color.RED) {
283             n.parent.color = Color.RED;
284             n.sibling().color = Color.BLACK;
285             if (n == n.parent.left)
286                 rotateLeft(n.parent);
287             else
288                 rotateRight(n.parent);
289         }
290         deleteCase3(n);
291     }
292     private void deleteCase3(Node<K,V> n) {
293         if (nodeColor(n.parent) == Color.BLACK &&
294             nodeColor(n.sibling()) == Color.BLACK &&
295             nodeColor(n.sibling().left) == Color.BLACK &&
296             nodeColor(n.sibling().right) == Color.BLACK)
297         {
298             n.sibling().color = Color.RED;
299             deleteCase1(n.parent);
300         }
301         else
302             deleteCase4(n);
303     }
304     private void deleteCase4(Node<K,V> n) {
305         if (nodeColor(n.parent) == Color.RED &&
306             nodeColor(n.sibling()) == Color.BLACK &&
307             nodeColor(n.sibling().left) == Color.BLACK &&
308             nodeColor(n.sibling().right) == Color.BLACK)
309         {
310             n.sibling().color = Color.RED;
311             n.parent.color = Color.BLACK;
312         }
313         else
314             deleteCase5(n);
315     }
316     private void deleteCase5(Node<K,V> n) {
317         if (n == n.parent.left &&
318             nodeColor(n.sibling()) == Color.BLACK &&
319             nodeColor(n.sibling().left) == Color.RED &&
320             nodeColor(n.sibling().right) == Color.BLACK)
321         {
322             n.sibling().color = Color.RED;
323             n.sibling().left.color = Color.BLACK;
324             rotateRight(n.sibling());
325         }
326         else if (n == n.parent.right &&
327                  nodeColor(n.sibling()) == Color.BLACK &&
328                  nodeColor(n.sibling().right) == Color.RED &&
329                  nodeColor(n.sibling().left) == Color.BLACK)
330         {
331             n.sibling().color = Color.RED;
332             n.sibling().right.color = Color.BLACK;
333             rotateLeft(n.sibling());
334         }
335         deleteCase6(n);
336     }
337     private void deleteCase6(Node<K,V> n) {
338         n.sibling().color = nodeColor(n.parent);
339         n.parent.color = Color.BLACK;
340         if (n == n.parent.left) {
341             assert nodeColor(n.sibling().right) == Color.RED;
342             n.sibling().right.color = Color.BLACK;
343             rotateLeft(n.parent);
344         }
345         else
346         {
347             assert nodeColor(n.sibling().left) == Color.RED;
348             n.sibling().left.color = Color.BLACK;
349             rotateRight(n.parent);
350         }
351     }
352     public void print() {
353         printHelper(root, 0);
354     }
355 
356     private static void printHelper(Node<?,?> n, int indent) {
357         if (n == null) {
358             System.out.print("<empty tree>");
359             return;
360         }
361         if (n.right != null) {
362             printHelper(n.right, indent + INDENT_STEP);
363         }
364         for (int i = 0; i < indent; i++)
365             System.out.print(" ");
366         if (n.color == Color.BLACK)
367             System.out.println(n.key);
368         else
369             System.out.println("<" + n.key + ">");
370         if (n.left != null) {
371             printHelper(n.left, indent + INDENT_STEP);
372         }
373     }
374     public static void main(String[] args) {
375         RBTree<Integer,Integer> t = new RBTree<Integer,Integer>();
376         t.print();
377 
378         java.util.Random gen = new java.util.Random();
379 
380         for (int i = 0; i < 5000; i++) {
381             int x = gen.nextInt(10000);
382             int y = gen.nextInt(10000);
383 
384             t.print();
385             System.out.println("Inserting " + x + " -> " + y);
386             System.out.println();
387 
388             t.insert(x, y);
389             assert t.lookup(x).equals(y);
390         }
391         for (int i = 0; i < 60000; i++) {
392             int x = gen.nextInt(10000);
393 
394             t.print();
395             System.out.println("Deleting key " + x);
396             System.out.println();
397 
398             t.delete(x);
399         }
400     }
401 }
402 


hijacker
hijacker
hijacker
hijacker