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