1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
4 /** a red-black tree of arbitrary objects */
5 public class RedBlackTree {
7 private static boolean RED = false;
8 private static boolean BLACK = true;
10 // These arrays are indexed by "slot", a totally meaningless number
11 // assigned to each object object[slot] has index index[slot] and
12 // color color[slot]. Note that slot 0 is reserved as "null".
14 /** every object in the tree has an entry here; ordering is completely random */
15 private Object[] objects;
17 /** the color of each object */
18 private boolean[] color;
20 /** the slot of this object's parent */
23 /** the slot of this object's left child */
26 /** the slot of this object's right child */
29 /** the index of each element; ie how many objects are "before" it in the logical ordering */
32 /** the slot of the root element */
35 /** returns the slot of the newly-inserted object */
37 public int insertBefore(int slot, Object newObject) { left = cell; cell.parent = this; cell.fixAfterInsertion(); }
38 public int insertAfterMe(int slot, Object newObject) { right = cell; cell.parent = this; cell.fixAfterInsertion(); }
40 private void setColor(int slot, boolean c) { if (objects[slot] != null) color[slot] = c; }
42 // FIXME: we can drop all this since all the 0th elements are the defaults, right?
43 private boolean color(int slot) { return objects[slot] == null ? BLACK : color[slot]; }
44 private int left(int slot) { return objects[slot] == null ? 0 : left[slot]; }
45 private int right(int slot) { return objects[slot] == null ? 0 : right[slot]; }
47 public void remove(int slot) { remove(slot, index[slot], root); }
49 private void seek(int slot, int idx, int cur, int operation) {
50 if (index[cur] > idx) {
51 remove(slot, idx, left[cur], operation);
52 } else if (index[cur] < idx) {
53 remove(slot, idx, right[cur], operation);
62 public void removeNode() {
64 // handle case where we are only node
65 if (left == null && right == null && parent == null) return;
67 // if strictly internal, swap places with a successor
68 if (left != null && right != null) swapPosition(this, nextSibling());
70 // Start fixup at replacement node (normally a child).
71 // But if no children, fake it by using self
72 if (left == null && right == null) {
74 if (test(BLACK)) fixAfterDeletion();
76 // Unlink (Couldn't before since fixAfterDeletion needs parent ptr)
79 if (this == parent.left)
81 else if (this == parent.right)
87 Box replacement = left;
88 if (replacement == null) replacement = right;
90 // link replacement to parent
91 replacement.parent = parent;
93 if (parent == null) root = replacement;
94 else if (this == parent.left) parent.left = replacement;
95 else parent.right = replacement;
102 if (test(BLACK)) replacement.fixAfterDeletion();
107 // Swap the linkages of two nodes in a tree.
108 void swapPosition(Box x, Box y) {
110 // Too messy. TODO: find sequence of assigments that are always OK
113 boolean xpl = px != null && x == px.left;
118 boolean ypl = py != null && y == py.left;
124 if (px != null) if (xpl) px.left = y; else px.right = y;
128 y.right = rx; if (rx != null) rx.parent = y;
132 y.left = lx; if (lx != null) lx.parent = y;
134 x.left = ly; if (ly != null) ly.parent = x;
135 x.right = ry; if (ry != null) ry.parent = x;
137 } else if (y == px) {
139 if (py != null) if (ypl) py.left = x; else py.right = x;
143 x.right = ry; if (ry != null) ry.parent = x;
147 x.left = ly; if (ly != null) ly.parent = x;
149 y.left = lx; if (lx != null) lx.parent = y;
150 y.right = rx; if (rx != null) rx.parent = y;
153 x.parent = py; if (py != null) if (ypl) py.left = x; else py.right = x;
154 x.left = ly; if (ly != null) ly.parent = x;
155 x.right = ry; if (ry != null) ry.parent = x;
157 y.parent = px; if (px != null) if (xpl) px.left = y; else px.right = y;
158 y.left = lx; if (lx != null) lx.parent = y;
159 y.right = rx; if (rx != null) rx.parent = y;
162 boolean c = x.test(BLACK);
163 if (y.test(BLACK)) x.set(BLACK); else x.clear(BLACK);
164 if (c) y.set(BLACK); else y.clear(BLACK);
166 if (root == x) root = y;
167 else if (root == y) root = x;
173 if (r.left != null) r.left.parent = this;
175 if (parent == null) root = r;
176 else if (parent.left == this) parent.left = r;
177 else parent.right = r;
185 if (l.right != null) l.right.parent = this;
187 if (parent == null) root = l;
188 else if (parent.right == this) parent.right = l;
189 else parent.left = l;
194 void fixAfterInsertion() {
198 while (x != null && x != root && !x.parent.test(BLACK)) {
199 if (parent[x] == left(parent[parent[x]])) {
200 Box y = right(parent[parent[x]]);
201 if (color(y) == RED) {
202 setColor(parent[x], BLACK);
204 setColor(parent[parent[x]], RED);
205 x = parent[parent[x]];
208 if (x == right(parent[x])) {
212 setColor(parent[x], BLACK);
213 setColor(parent[parent[x]], RED);
214 if (parent[parent[x]] != null)
215 parent[parent[x]].rotateRight();
219 Box y = left(parent[parent[x]]);
220 if (color(y) == RED) {
221 setColor(parent[x], BLACK);
223 setColor(parent[parent[x]], RED);
224 x = parent[parent[x]];
227 if (x == left(parent[x])) {
231 setColor(parent[x], BLACK);
232 setColor(parent[parent[x]], RED);
233 if (parent[parent[x]] != null)
234 parent[parent[x]].rotateLeft();
242 void fixAfterDeletion() {
244 while (x != root && color(x) == BLACK) {
245 if (x == left(parent[x])) {
246 Box sib = right(parent[x]);
247 if (color(sib) == RED) {
248 setColor(sib, BLACK);
249 setColor(parent[x], RED);
250 parent[x].rotateLeft();
251 sib = right(parent[x]);
253 if (color(left(sib)) == BLACK && color(right(sib)) == BLACK) {
258 if (color(right(sib)) == BLACK) {
259 setColor(left(sib), BLACK);
262 sib = right(parent[x]);
264 setColor(sib, color(parent[x]));
265 setColor(parent[x], BLACK);
266 setColor(right(sib), BLACK);
267 parent[x].rotateLeft();
272 Box sib = left(parent[x]);
273 if (color(sib) == RED) {
274 setColor(sib, BLACK);
275 setColor(parent[x], RED);
276 parent[x].rotateRight();
277 sib = left(parent[x]);
279 if (color(right(sib)) == BLACK && color(left(sib)) == BLACK) {
284 if (color(left(sib)) == BLACK) {
285 setColor(right(sib), BLACK);
288 sib = left(parent[x]);
290 setColor(sib, color(parent[x]));
291 setColor(parent[x], BLACK);
292 setColor(left(sib), BLACK);
293 parent[x].rotateRight();