Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/tests/avltree/avl3.c

    rcb811ac rdb67b11  
    33#include <stdlib>
    44
     5// from stdlib
     6forall(otype T)
     7void swap(T *, T *);
     8
    59// swaps the data within two tree nodes
    610forall(otype K | Comparable(K), otype V)
    711void 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);
    1014}
    1115
    … …  
    1317forall(otype K | Comparable(K), otype V)
    1418tree(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);
     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);
    2428}
    2529
    … …  
    2731forall(otype K | Comparable(K), otype V)
    2832void deleteSingleNode(tree(K, V) * t) {
    29         t->left = NULL;
    30         t->right = NULL;
    31         delete(t);
     33  t->left = NULL;
     34  t->right = NULL;
     35  delete(t);
    3236}
    3337
    … …  
    3539forall(otype K | Comparable(K), otype V)
    3640tree(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;
     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;
    4650
    47                 // relink tree
    48                 t->left = tmp->left;
    49                 t->right = tmp->right;
     51    // relink tree
     52    t->left = tmp->left;
     53    t->right = tmp->right;
    5054
    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;
     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;
    5963
    60                 // relink tree
    61                 t->left = tmp->left;
    62                 t->right = tmp->right;
     64    // relink tree
     65    t->left = tmp->left;
     66    t->right = tmp->right;
    6367
    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;
     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;
    7276
    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         }
     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  }
    8488}
    8589
    … …  
    8791forall(otype K | Comparable(K), otype V)
    8892tree(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;
     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;
    106110}
    107111
    108112forall(otype K | Comparable(K), otype V)
    109113int 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  int worked = 0;
     115  tree(K, V) * newTree = remove_helper(*t, key, &worked);
     116  *t = newTree;
     117  return worked;
    114118}
    115 
    116 // Local Variables: //
    117 // tab-width: 4 //
    118 // End: //
Note: See TracChangeset for help on using the changeset viewer.