Changes in src/tests/avltree/avl3.c [cb811ac:db67b11]
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/tests/avltree/avl3.c
rcb811ac rdb67b11 3 3 #include <stdlib> 4 4 5 // from stdlib 6 forall(otype T) 7 void swap(T *, T *); 8 5 9 // swaps the data within two tree nodes 6 10 forall(otype K  Comparable(K), otype V) 7 11 void node_swap(tree(K, V) * t, tree(K, V) * t2){ 8 swap( t>key,t2>key);9 swap( t>value,t2>value);12 swap(&t>key, &t2>key); 13 swap(&t>value, &t2>value); 10 14 } 11 15 … … 13 17 forall(otype K  Comparable(K), otype V) 14 18 tree(K, V) * find_successor(tree(K, V) * t){ 15 16 17 18 19 20 21 22 23 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); 24 28 } 25 29 … … 27 31 forall(otype K  Comparable(K), otype V) 28 32 void deleteSingleNode(tree(K, V) * t) { 29 30 31 33 t>left = NULL; 34 t>right = NULL; 35 delete(t); 32 36 } 33 37 … … 35 39 forall(otype K  Comparable(K), otype V) 36 40 tree(K, V) * remove_node(tree(K, V) * t){ 37 38 39 40 41 42 43 44 45 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; 46 50 47 48 49 51 // relink tree 52 t>left = tmp>left; 53 t>right = tmp>right; 50 54 51 52 53 54 55 56 57 58 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; 59 63 60 61 62 64 // relink tree 65 t>left = tmp>left; 66 t>right = tmp>right; 63 67 64 65 66 67 68 69 70 71 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; 72 76 73 74 75 76 77 78 79 80 81 82 83 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 } 84 88 } 85 89 … … 87 91 forall(otype K  Comparable(K), otype V) 88 92 tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){ 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 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; 106 110 } 107 111 108 112 forall(otype K  Comparable(K), otype V) 109 113 int remove(tree(K, V) ** t, K key){ 110 111 112 113 114 int worked = 0; 115 tree(K, V) * newTree = remove_helper(*t, key, &worked); 116 *t = newTree; 117 return worked; 114 118 } 115 116 // Local Variables: //117 // tabwidth: 4 //118 // End: //
Note: See TracChangeset
for help on using the changeset viewer.