| 174 | } |
| 175 | |
| 176 | void util_avl_remove(struct util_avl_struct *node, struct util_avl_root *root) |
| 177 | { |
| 178 | struct util_avl_struct **nodeplace; |
| 179 | |
| 180 | if (root->root_node == NULL) |
| 181 | return; |
| 182 | |
| 183 | if (node->parent != NULL) |
| 184 | { |
| 185 | nodeplace = NODE_PLACE(node); |
| 186 | } |
| 187 | else |
| 188 | { |
| 189 | nodeplace = &root->root_node; |
| 190 | } |
| 191 | |
| 192 | /* deletion */ |
| 193 | if (node->avl_right == NULL) |
| 194 | { |
| 195 | *nodeplace = node->avl_left; |
| 196 | if (node->avl_left != NULL) |
| 197 | node->avl_left->parent = node->parent; |
| 198 | node = node->parent; |
| 199 | } |
| 200 | else |
| 201 | { |
| 202 | struct util_avl_struct *rchild = node->avl_right; |
| 203 | if (rchild->avl_left == NULL) |
| 204 | { |
| 205 | *nodeplace = rchild; |
| 206 | rchild->avl_left = node->avl_left; |
| 207 | if (rchild->avl_left != NULL) |
| 208 | rchild->avl_left->parent = rchild; |
| 209 | rchild->parent = node->parent; |
| 210 | util_avl_rebalance(rchild, root); |
| 211 | node = rchild->parent; |
| 212 | } |
| 213 | else |
| 214 | { |
| 215 | struct util_avl_struct *successor = rchild->avl_left; |
| 216 | struct util_avl_struct *sparent = rchild; |
| 217 | while (successor->avl_left != NULL) |
| 218 | { |
| 219 | sparent = successor; |
| 220 | successor = successor->avl_left; |
| 221 | } |
| 222 | *nodeplace = successor; |
| 223 | sparent->avl_left = successor->avl_right; |
| 224 | successor->avl_left = node->avl_left; |
| 225 | successor->avl_right = node->avl_right; |
| 226 | |
| 227 | if (successor->avl_left != NULL) |
| 228 | successor->avl_left->parent = successor; |
| 229 | successor->avl_right->parent = successor; |
| 230 | |
| 231 | if (sparent->avl_left != NULL) |
| 232 | sparent->avl_left->parent = sparent; |
| 233 | successor->parent = node->parent; |