source: src/tests/avltree/avl3.c@ 1ae06fa

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 1ae06fa was db67b11, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

Fix avl_test to use stdlib include instead of 'delete' forward declaration
  • Property mode set to 100644
File size: 2.9 KB
Line 
1#include "avl.h"
2#include "avl-private.h"
3#include <stdlib>
4
5// from stdlib
6forall(otype T)
7void swap(T *, T *);
8
9// swaps the data within two tree nodes
10forall(otype K | Comparable(K), otype V)
11void 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
17forall(otype K | Comparable(K), otype V)
18tree(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.
31forall(otype K | Comparable(K), otype V)
32void 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
39forall(otype K | Comparable(K), otype V)
40tree(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
91forall(otype K | Comparable(K), otype V)
92tree(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
112forall(otype K | Comparable(K), otype V)
113int 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}
Note: See TracBrowser for help on using the repository browser.