Insert or find a given key in the tree and rebalance the tree correctly. Rebalancing restores the red-black aspect of the tree to maintain the invariants: 1. If a node is red, both of its children are black. 2. Each child of a node has the same black height (the number of black nodes betwee
(int node, boolean fromLeft, int parent,
int grandparent, int greatGrandparent)
| 148 | * @return Does parent also need to be checked and/or fixed? |
| 149 | */ |
| 150 | private boolean add(int node, boolean fromLeft, int parent, |
| 151 | int grandparent, int greatGrandparent) { |
| 152 | if (node == NULL) { |
| 153 | if (root == NULL) { |
| 154 | lastAdd = insert(NULL, NULL, false); |
| 155 | root = lastAdd; |
| 156 | wasAdd = true; |
| 157 | return false; |
| 158 | } else { |
| 159 | lastAdd = insert(NULL, NULL, true); |
| 160 | node = lastAdd; |
| 161 | wasAdd = true; |
| 162 | // connect the new node into the tree |
| 163 | if (fromLeft) { |
| 164 | setLeft(parent, node); |
| 165 | } else { |
| 166 | setRight(parent, node); |
| 167 | } |
| 168 | } |
| 169 | } else { |
| 170 | int compare = compareValue(node); |
| 171 | boolean keepGoing; |
| 172 | |
| 173 | // Recurse down to find where the node needs to be added |
| 174 | if (compare < 0) { |
| 175 | keepGoing = add(getLeft(node), true, node, parent, grandparent); |
| 176 | } else if (compare > 0) { |
| 177 | keepGoing = add(getRight(node), false, node, parent, grandparent); |
| 178 | } else { |
| 179 | lastAdd = node; |
| 180 | wasAdd = false; |
| 181 | return false; |
| 182 | } |
| 183 | |
| 184 | // we don't need to fix the root (because it is always set to black) |
| 185 | if (node == root || !keepGoing) { |
| 186 | return false; |
| 187 | } |
| 188 | } |
| 189 | |
| 190 | |
| 191 | // Do we need to fix this node? Only if there are two reds right under each |
| 192 | // other. |
| 193 | if (isRed(node) && isRed(parent)) { |
| 194 | if (parent == getLeft(grandparent)) { |
| 195 | int uncle = getRight(grandparent); |
| 196 | if (isRed(uncle)) { |
| 197 | // case 1.1 |
| 198 | setRed(parent, false); |
| 199 | setRed(uncle, false); |
| 200 | setRed(grandparent, true); |
| 201 | return true; |
| 202 | } else { |
| 203 | if (node == getRight(parent)) { |
| 204 | // case 1.2 |
| 205 | // swap node and parent |
| 206 | int tmp = node; |
| 207 | node = parent; |