| 1 | #include "avl.h" |
|---|
| 2 | #include "avl-private.h" |
|---|
| 3 | #include <stdlib.hfa> |
|---|
| 4 | |
|---|
| 5 | // swaps the data within two tree nodes |
|---|
| 6 | forall(otype K | Comparable(K), otype V) |
|---|
| 7 | void node_swap(tree(K, V) * t, tree(K, V) * t2){ |
|---|
| 8 | swap( t->key, t2->key); |
|---|
| 9 | swap( t->value, t2->value); |
|---|
| 10 | } |
|---|
| 11 | |
|---|
| 12 | // go left as deep as possible from within the right subtree |
|---|
| 13 | forall(otype K | Comparable(K), otype V) |
|---|
| 14 | tree(K, V) * find_successor(tree(K, V) * t){ |
|---|
| 15 | tree(K, V) * find_successor_helper(tree(K, V) * t){ |
|---|
| 16 | // go left as deep as possible, return the last node |
|---|
| 17 | if (empty(t->left)){ |
|---|
| 18 | return t; |
|---|
| 19 | } else { |
|---|
| 20 | return find_successor_helper(t->left); |
|---|
| 21 | } |
|---|
| 22 | } |
|---|
| 23 | return find_successor_helper(t->right); |
|---|
| 24 | } |
|---|
| 25 | |
|---|
| 26 | // cleanup - don't want to deep delete, so set children to NULL first. |
|---|
| 27 | forall(otype K | Comparable(K), otype V) |
|---|
| 28 | void deleteSingleNode(tree(K, V) * t) { |
|---|
| 29 | t->left = NULL; |
|---|
| 30 | t->right = NULL; |
|---|
| 31 | delete(t); |
|---|
| 32 | } |
|---|
| 33 | |
|---|
| 34 | // does the actual remove operation once we've found the node in question |
|---|
| 35 | forall(otype K | Comparable(K), otype V) |
|---|
| 36 | tree(K, V) * remove_node(tree(K, V) * t){ |
|---|
| 37 | // is the node a leaf? |
|---|
| 38 | if (empty(t->left) && empty(t->right)){ |
|---|
| 39 | // yes, just delete this node |
|---|
| 40 | delete(t); |
|---|
| 41 | return NULL; |
|---|
| 42 | } else if (empty(t->left)){ |
|---|
| 43 | // if the left is empty, there is only one child -> move right up |
|---|
| 44 | node_swap(t, t->right); |
|---|
| 45 | tree(K, V) * tmp = t->right; |
|---|
| 46 | |
|---|
| 47 | // relink tree |
|---|
| 48 | t->left = tmp->left; |
|---|
| 49 | t->right = tmp->right; |
|---|
| 50 | |
|---|
| 51 | setParent(t->left, t); |
|---|
| 52 | setParent(t->right, t); |
|---|
| 53 | deleteSingleNode(tmp); |
|---|
| 54 | return t; |
|---|
| 55 | } else if (empty(t->right)){ |
|---|
| 56 | // if the right is empty, there is only one child -> move left up |
|---|
| 57 | node_swap(t, t->left); |
|---|
| 58 | tree(K, V) * tmp = t->left; |
|---|
| 59 | |
|---|
| 60 | // relink tree |
|---|
| 61 | t->left = tmp->left; |
|---|
| 62 | t->right = tmp->right; |
|---|
| 63 | |
|---|
| 64 | setParent(t->left, t); |
|---|
| 65 | setParent(t->right, t); |
|---|
| 66 | deleteSingleNode(tmp); |
|---|
| 67 | return t; |
|---|
| 68 | } else { |
|---|
| 69 | // swap with the successor |
|---|
| 70 | tree(K, V) * s = find_successor(t); |
|---|
| 71 | tree(K, V) * parent = s->parent; |
|---|
| 72 | |
|---|
| 73 | if (parent->left == s){ |
|---|
| 74 | parent->left = s->right; |
|---|
| 75 | } else { |
|---|
| 76 | assert(parent->right == s); |
|---|
| 77 | parent->right = s->right; |
|---|
| 78 | } |
|---|
| 79 | setParent(s->right, parent); |
|---|
| 80 | node_swap(t, s); |
|---|
| 81 | deleteSingleNode(s); |
|---|
| 82 | return t; |
|---|
| 83 | } |
|---|
| 84 | } |
|---|
| 85 | |
|---|
| 86 | // finds the node that needs to be removed |
|---|
| 87 | forall(otype K | Comparable(K), otype V) |
|---|
| 88 | tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){ |
|---|
| 89 | if (empty(t)){ |
|---|
| 90 | // did not work because key was not found |
|---|
| 91 | // set the status variable and return |
|---|
| 92 | *worked = 1; |
|---|
| 93 | } else if (t->key == key) { |
|---|
| 94 | t = remove_node(t); |
|---|
| 95 | } else if (t->key < key){ |
|---|
| 96 | t->right = remove_helper(t->right, key, worked); |
|---|
| 97 | } else { |
|---|
| 98 | // t->key > key |
|---|
| 99 | t->left = remove_helper(t->left, key, worked); |
|---|
| 100 | } |
|---|
| 101 | // try to fix after deleting |
|---|
| 102 | if (! empty(t)) { |
|---|
| 103 | t = tryFix(t); |
|---|
| 104 | } |
|---|
| 105 | return t; |
|---|
| 106 | } |
|---|
| 107 | |
|---|
| 108 | forall(otype K | Comparable(K), otype V) |
|---|
| 109 | int remove(tree(K, V) ** t, K key){ |
|---|
| 110 | int worked = 0; |
|---|
| 111 | tree(K, V) * newTree = remove_helper(*t, key, &worked); |
|---|
| 112 | *t = newTree; |
|---|
| 113 | return worked; |
|---|
| 114 | } |
|---|
| 115 | |
|---|
| 116 | // Local Variables: // |
|---|
| 117 | // tab-width: 4 // |
|---|
| 118 | // End: // |
|---|
