source: src/tests/avltree/avl3.c @ 3dcd347a

aaron-thesisarm-ehcleanup-dtorsctordeferred_resndemanglergc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 3dcd347a was 3dcd347a, checked in by Thierry Delisle <tdelisle@…>, 5 years ago

moved some more tests to new test folder

  • Property mode set to 100644
File size: 2.9 KB
Line 
1#include "avl.h"
2#include "avl-private.h"
3
4// from stdlib
5forall(otype T)
6void swap(T *, T *);
7
8// swaps the data within two tree nodes
9forall(otype K | Comparable(K), otype V)
10void 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
16forall(otype K | Comparable(K), otype V)
17tree(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.
30forall(otype K | Comparable(K), otype V)
31void 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
38forall(otype K | Comparable(K), otype V)
39tree(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
90forall(otype K | Comparable(K), otype V)
91tree(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
111forall(otype K | Comparable(K), otype V)
112int 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}
Note: See TracBrowser for help on using the repository browser.