source: src/tests/avltree/avl3.c@ 6dba9f99

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since 6dba9f99 was cb811ac, checked in by Peter A. Buhr <pabuhr@…>, 8 years ago

change stdlib swap to use references, and update swap tests
  • Property mode set to 100644
File size: 2.8 KB
Line 
1#include "avl.h"
2#include "avl-private.h"
3#include <stdlib>
4
5// swaps the data within two tree nodes
6forall(otype K | Comparable(K), otype V)
7void 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
13forall(otype K | Comparable(K), otype V)
14tree(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.
27forall(otype K | Comparable(K), otype V)
28void 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
35forall(otype K | Comparable(K), otype V)
36tree(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
87forall(otype K | Comparable(K), otype V)
88tree(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
108forall(otype K | Comparable(K), otype V)
109int 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: //
Note: See TracBrowser for help on using the repository browser.