class RedBlackTree
1: //RedBlackTree.java
3: class RedBlackTree
4: {
5: private RBTNode root;
7: public RedBlackTree()
8: {
9: root = null;
10: }
12: public RBTNode getRoot()
13: {
14: return root;
15: }
17: public int getLength()
18: {
19: if (root == null)
20: {
21: return 0;
22: }
23: return root.count();
24: }
26: // Returns the height of this tree
27: public int getHeight()
28: {
29: return getHeightRecursive(root);
30: }
32: private int getHeightRecursive(RBTNode node)
33: {
34: if (node == null)
35: {
36: return -1;
37: }
38: int leftHeight = getHeightRecursive(node.left);
39: int rightHeight = getHeightRecursive(node.right);
40: return 1 + Math.max(leftHeight, rightHeight);
41: }
43: public void insert(int key)
44: {
45: RBTNode newNode = new RBTNode(key, null, true, null, null);
46: insertNode(newNode);
47: }
49: public void insertNode(RBTNode node)
50: {
51: // Begin with normal BST insertion
52: if (root == null)
53: {
54: // Special case for root
55: root = node;
56: }
57: else
58: {
59: RBTNode currentNode = root;
60: while (currentNode != null)
61: {
62: if (node.key < currentNode.key)
63: {
64: if (currentNode.left == null)
65: {
66: currentNode.setChild(RBTNode.Child.LEFT, node);
67: break;
68: }
69: else
70: {
71: currentNode = currentNode.left;
72: }
73: }
74: else
75: {
76: if (currentNode.right == null)
77: {
78: currentNode.setChild(RBTNode.Child.RIGHT, node);
79: break;
80: }
81: else
82: {
83: currentNode = currentNode.right;
84: }
85: }
86: }
87: }
89: // Color the node red, then balance
90: node.color = RBTNode.Color.RED;
91: insertionBalance(node);
92: }
94: public void insertionBalance(RBTNode node)
95: {
96: // If node is the tree's root, then color node black and return
97: if (node.parent == null)
98: {
99: node.color = RBTNode.Color.BLACK;
100: return;
101: }
103: // If parent is black, then return without any changes
104: if (node.parent.isBlack())
105: {
106: return;
107: }
109: // References to parent, grandparent, and uncle are needed for remaining operations
110: RBTNode parent = node.parent;
111: RBTNode grandparent = node.getGrandparent();
112: RBTNode uncle = node.getUncle();
114: // If parent and uncle are both red, then color parent and uncle black, color grandparent
115: // red, recursively balance grandparent, then return
116: if (uncle != null && uncle.isRed())
117: {
118: parent.color = uncle.color = RBTNode.Color.BLACK;
119: grandparent.color = RBTNode.Color.RED;
120: insertionBalance(grandparent);
121: return;
122: }
124: // If node is parent's right child and parent is grandparent's left child, then rotate left
125: // at parent, update node and parent to point to parent and grandparent, respectively
126: if (node == parent.right && parent == grandparent.left)
127: {
128: rotateLeft(parent);
129: node = parent;
130: parent = node.parent;
131: }
132: // Else if node is parent's left child and parent is grandparent's right child, then rotate
133: // right at parent, update node and parent to point to parent and grandparent, respectively
134: else if (node == parent.left && parent == grandparent.right)
135: {
136: rotateRight(parent);
137: node = parent;
138: parent = node.parent;
139: }
141: // Color parent black and grandparent red
142: parent.color = RBTNode.Color.BLACK;
143: grandparent.color = RBTNode.Color.RED;
145: // If node is parent's left child, then rotate right at grandparent, otherwise rotate left
146: // at grandparent
147: if (node == parent.left)
148: {
149: rotateRight(grandparent);
150: }
151: else
152: {
153: rotateLeft(grandparent);
154: }
155: }
157: // Performs a left rotation at the given node. Returns the
158: // subtree's new root.
159: public RBTNode rotateLeft(RBTNode node)
160: {
161: // Define a convenience pointer to the right child of the
162: // left child.
163: RBTNode rightLeftChild = node.right.left;
165: // Step 1 - the right child moves up to the node's position.
166: // node is temporarily detached from the tree, but will be reattached
167: // later.
168: if (node.parent != null)
169: {
170: node.parent.replaceChild(node, node.right);
171: }
172: else // node is root
173: {
174: root = node.right;
175: root.parent = null;
176: }
178: // Step 2 - the node becomes the left child of what used
179: // to be node's right child, but is now node's parent. This will
180: // detach rightLeftChild from the tree.
181: node.right.setChild(RBTNode.Child.LEFT, node);
183: // Step 3 - reattach rightLeftChild as the right child of node.
184: node.setChild(RBTNode.Child.RIGHT, rightLeftChild);
186: return node.parent;
187: }
189: // Performs a right rotation at the given node. Returns the
190: // subtree's new root.
191: public RBTNode rotateRight(RBTNode node)
192: {
193: // Define a convenience pointer to the left child of the
194: // right child.
195: RBTNode leftRightChild = node.left.right;
197: // Step 1 - the left child moves up to the node's position.
198: // node is temporarily detached from the tree, but will be reattached
199: // later.
200: if (node.parent != null)
201: {
202: node.parent.replaceChild(node, node.left);
203: }
204: else // node is root
205: {
206: root = node.left;
207: root.parent = null;
208: }
210: // Step 2 - the node becomes the right child of what used
211: // to be node's left child, but is now node's parent. This will
212: // detach leftRightChild from the tree.
213: node.left.setChild(RBTNode.Child.RIGHT, node);
215: // Step 3 - reattach leftRightChild as the right child of node.
216: node.setChild(RBTNode.Child.LEFT, leftRightChild);
218: return node.parent;
219: }
221: private void bstRemove(int key)
222: {
223: RBTNode node = search(key);
224: bstRemoveNode(node);
225: }
227: private void bstRemoveNode(RBTNode node)
228: {
229: if (node == null)
230: {
231: return;
232: }
234: // Case 1: Internal node with 2 children
235: if (node.left != null && node.right != null)
236: {
237: // Find successor
238: RBTNode successorNode = node.right;
239: while (successorNode.left != null)
240: {
241: successorNode = successorNode.left;
242: }
244: // Copy successor's key
245: int successorKey = successorNode.key;
247: // Recursively remove successor
248: bstRemoveNode(successorNode);
250: // Set node's key to copied successor key
251: node.key = successorKey;
252: }
254: // Case 2: Root node (with 1 or 0 children)
255: else if (node == root)
256: {
257: if (node.left == null)
258: {
259: root = node.left;
260: }
261: else
262: {
263: root = node.right;
264: }
266: // Make sure the new root, if non-null, has parent set to null
267: if (root != null)
268: {
269: root.parent = null;
270: }
271: }
273: // Case 3: Internal with left child only
274: else if (node.left != null)
275: {
276: node.parent.replaceChild(node, node.left);
277: }
279: // Case 4: Internal with right child OR leaf
280: else
281: {
282: node.parent.replaceChild(node, node.right);
283: }
284: }
286: public boolean isNoneOrBlack(RBTNode node)
287: {
288: if (node == null)
289: {
290: return true;
291: }
292: return node.isBlack();
293: }
295: public boolean isNotNoneAndRed(RBTNode node)
296: {
297: if (node == null)
298: {
299: return false;
300: }
301: return node.isRed();
302: }
304: private void prepareForRemoval(RBTNode node)
305: {
306: if (tryCase1(node))
307: {
308: return;
309: }
311: RBTNode sibling = node.getSibling();
312: if (tryCase2(node, sibling))
313: {
314: sibling = node.getSibling();
315: }
316: if (tryCase3(node, sibling))
317: {
318: return;
319: }
320: if (tryCase4(node, sibling))
321: {
322: return;
323: }
324: if (tryCase5(node, sibling))
325: {
326: sibling = node.getSibling();
327: }
328: if (tryCase6(node, sibling))
329: {
330: sibling = node.getSibling();
331: }
333: sibling.color = node.parent.color;
334: node.parent.color = RBTNode.Color.BLACK;
335: if (node == node.parent.left)
336: {
337: sibling.right.color = RBTNode.Color.BLACK;
338: rotateLeft(node.parent);
339: }
340: else
341: {
342: sibling.left.color = RBTNode.Color.BLACK;
343: rotateRight(node.parent);
344: }
345: }
347: public boolean remove(int key)
348: {
349: RBTNode node = search(key);
350: if (node != null)
351: {
352: removeNode(node);
353: return true;
354: }
355: return false;
356: }
358: public void removeNode(RBTNode node)
359: {
360: if (node.left != null && node.right != null)
361: {
362: RBTNode predecessorNode = node.getPredecessor();
363: int predecessorKey = predecessorNode.key;
364: removeNode(predecessorNode);
365: node.key = predecessorKey;
366: return;
367: }
369: if (node.isBlack())
370: {
371: prepareForRemoval(node);
372: }
373: bstRemove(node.key);
375: // One special case if the root was changed to red
376: if (root != null && root.isRed())
377: {
378: root.color = RBTNode.Color.BLACK;
379: }
380: }
382: // Searches for a node with a matching key. Does a regular
383: // binary search tree search operation. Returns the node with the
384: // matching key if it exists in the tree, or None if there is no
385: // matching key in the tree.
386: public RBTNode search(int desiredKey)
387: {
388: RBTNode currentNode = root;
389: while (currentNode != null)
390: {
391: // Return the node if the key matches
392: if (currentNode.key == desiredKey)
393: {
394: return currentNode;
395: }
397: // Navigate to the left if the search key is
398: // less than the node's key.
399: else if (desiredKey < currentNode.key)
400: {
401: currentNode = currentNode.left;
402: }
404: // Navigate to the right if the search key is
405: // greater than the node's key.
406: else
407: {
408: currentNode = currentNode.right;
409: }
410: }
412: // The key was not found in the tree.
413: return null;
414: }
416: private boolean tryCase1(RBTNode node)
417: {
418: if (node.isRed() || node.parent == null)
419: {
420: return true;
421: }
422: return false; // node case 1
423: }
425: private boolean tryCase2(RBTNode node, RBTNode sibling)
426: {
427: if (sibling.isRed())
428: {
429: node.parent.color = RBTNode.Color.RED;
430: sibling.color = RBTNode.Color.BLACK;
431: if (node == node.parent.left)
432: {
433: rotateLeft(node.parent);
434: }
435: else
436: {
437: rotateRight(node.parent);
438: }
439: return true;
440: }
441: return false; // not case 2
442: }
444: private boolean tryCase3(RBTNode node, RBTNode sibling)
445: {
446: if (node.parent.isBlack() && sibling.areBothChildrenBlack())
447: {
448: sibling.color = RBTNode.Color.RED;
449: prepareForRemoval(node.parent);
450: return true;
451: }
452: return false; // not case 3
453: }
455: private boolean tryCase4(RBTNode node, RBTNode sibling)
456: {
457: if (node.parent.isRed() && sibling.areBothChildrenBlack())
458: {
459: node.parent.color = RBTNode.Color.BLACK;
460: sibling.color = RBTNode.Color.RED;
461: return true;
462: }
463: return false; // not case 4
464: }
466: private boolean tryCase5(RBTNode node, RBTNode sibling)
467: {
468: if (isNotNoneAndRed(sibling.left))
469: {
470: if (isNoneOrBlack(sibling.right))
471: {
472: if (node == node.parent.left)
473: {
474: sibling.color = RBTNode.Color.RED;
475: sibling.left.color = RBTNode.Color.BLACK;
476: rotateRight(sibling);
477: return true;
478: }
479: }
480: }
481: return false; // not case 5
482: }
484: private boolean tryCase6(RBTNode node, RBTNode sibling)
485: {
486: if (isNoneOrBlack(sibling.left))
487: {
488: if (isNotNoneAndRed(sibling.right))
489: {
490: if (node == node.parent.right)
491: {
492: sibling.color = RBTNode.Color.RED;
493: sibling.right.color = RBTNode.Color.BLACK;
494: rotateLeft(sibling);
495: return true;
496: }
497: }
498: }
499: return false; // not case 6
500: }
501: }