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