1.1 --- a/src/bst.c	Wed Sep 26 18:59:22 2012 -0500
     1.2 +++ b/src/bst.c	Thu Sep 27 10:57:41 2012 -0500
     1.3 @@ -10,11 +10,15 @@
     1.4  
     1.5  void bst_node_walk_postorder(struct bst_node * node, void (*op)(struct bst_node * n));
     1.6  
     1.7 -void * bst_node_search(struct bst * bst, struct bst_node * node, void * data);
     1.8 +void * bst_data_search(struct bst * bst, struct bst_node * node, void * data);
     1.9  void * bst_node_minimum(struct bst_node * node);
    1.10  void * bst_node_maximum(struct bst_node * node);
    1.11  void bst_node_free(struct bst_node * node);
    1.12  
    1.13 +struct bst_node * bst_node_search(struct bst * bst, struct bst_node * node, void * data);
    1.14 +
    1.15 +struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b);
    1.16 +
    1.17  ////////////////////////////////////////////////////////////////////////////////
    1.18  struct bst *
    1.19  bst_new(bool (*le)(void * a, void * b),
    1.20 @@ -175,12 +179,12 @@
    1.21     if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )
    1.22        return NULL;
    1.23  
    1.24 -   return bst_node_search(bst, bst->root, data);
    1.25 +   return bst_data_search(bst, bst->root, data);
    1.26     }
    1.27  
    1.28  ////////////////////////////////////////////////////////////////////////////////
    1.29  // Recursive
    1.30 -void * bst_node_search(struct bst * bst, struct bst_node * node, void * data)
    1.31 +void * bst_data_search(struct bst * bst, struct bst_node * node, void * data)
    1.32     {
    1.33     if (NULL == node)
    1.34        return NULL;
    1.35 @@ -189,9 +193,9 @@
    1.36        return node->data;
    1.37  
    1.38     if (bst->le(data, node->data))
    1.39 -      return bst_node_search(bst, node->left, data);
    1.40 +      return bst_data_search(bst, node->left, data);
    1.41     else
    1.42 -      return bst_node_search(bst, node->right, data);
    1.43 +      return bst_data_search(bst, node->right, data);
    1.44     }
    1.45  
    1.46  ////////////////////////////////////////////////////////////////////////////////
    1.47 @@ -360,3 +364,89 @@
    1.48     return it->curr->data;
    1.49     }
    1.50  
    1.51 +////////////////////////////////////////////////////////////////////////////////
    1.52 +void *
    1.53 +bst_find(struct bst_iterator * it, void * data)
    1.54 +   {
    1.55 +   if ( (NULL == it) || (NULL == it->bst) || (NULL == it->bst->root) || (NULL == data) )
    1.56 +      return NULL;
    1.57 +
    1.58 +   return bst_node_search(it->bst, it->bst->root, data);
    1.59 +   }
    1.60 +
    1.61 +////////////////////////////////////////////////////////////////////////////////
    1.62 +// Recursive
    1.63 +struct bst_node *
    1.64 +bst_node_search(struct bst * bst, struct bst_node * node, void * data)
    1.65 +   {
    1.66 +   if (NULL == node)
    1.67 +      return NULL;
    1.68 +
    1.69 +   if (bst->eq(data, node->data))
    1.70 +      return node;
    1.71 +
    1.72 +   if (bst->le(data, node->data))
    1.73 +      return bst_node_search(bst, node->left, data);
    1.74 +   else
    1.75 +      return bst_node_search(bst, node->right, data);
    1.76 +   }
    1.77 +
    1.78 +////////////////////////////////////////////////////////////////////////////////
    1.79 +struct bst_node *
    1.80 +bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b)
    1.81 +   {
    1.82 +   if ( (NULL == a) || (NULL == b) )
    1.83 +      return NULL;
    1.84 +
    1.85 +   if (NULL == a->parent)
    1.86 +      bst->root = b;
    1.87 +   else if (a == a->parent->left)
    1.88 +      a->parent->left = b;
    1.89 +   else
    1.90 +      a->parent->right = b;
    1.91 +
    1.92 +   if (NULL != b)
    1.93 +      b->parent = a->parent;
    1.94 +
    1.95 +   return a;
    1.96 +   }
    1.97 +
    1.98 +////////////////////////////////////////////////////////////////////////////////
    1.99 +void *
   1.100 +bst_remove(struct bst_iterator * it)
   1.101 +   {
   1.102 +   if ( (NULL == it) || (NULL == it->curr) )
   1.103 +      return NULL;
   1.104 +
   1.105 +   struct bst_node * y;
   1.106 +
   1.107 +   if (NULL == it->curr->left)
   1.108 +      {
   1.109 +      bst_transplant(it->bst, it->curr, it->curr->right);
   1.110 +      y = it->curr->right;
   1.111 +      }
   1.112 +   else if (NULL == it->curr->right)
   1.113 +      {
   1.114 +      bst_transplant(it->bst, it->curr, it->curr->left);
   1.115 +      y = it->curr->left;
   1.116 +      }
   1.117 +   else
   1.118 +      {
   1.119 +      y = bst_node_minimum(it->curr->right);
   1.120 +      if (NULL != y->parent)
   1.121 +	 {
   1.122 +	 bst_transplant(it->bst, y, y->right);
   1.123 +	 y->right = it->curr->right;
   1.124 +	 y->right->parent = y;
   1.125 +	 }
   1.126 +      bst_transplant(it->bst, it->curr, y);
   1.127 +      y->left = it->curr->left;
   1.128 +      y->left->parent = y;
   1.129 +      }
   1.130 +
   1.131 +   void * data = it->curr->data;
   1.132 +   free(it->curr);
   1.133 +   it->curr = y;
   1.134 +   return data;
   1.135 +   }
   1.136 +

     2.1 --- a/src/bst.h	Wed Sep 26 18:59:22 2012 -0500
     2.2 +++ b/src/bst.h	Thu Sep 27 10:57:41 2012 -0500
     2.3 @@ -48,4 +48,7 @@
     2.4  struct bst_iterator * bst_prev(struct bst_iterator * it);
     2.5  void * bst_value(struct bst_iterator * it);
     2.6  
     2.7 +void * bst_find(struct bst_iterator * it, void * data);
     2.8 +void * bst_remove(struct bst_iterator * it);
     2.9 +
    2.10  #endif

     3.1 --- a/src/bst_test.c	Wed Sep 26 18:59:22 2012 -0500
     3.2 +++ b/src/bst_test.c	Thu Sep 27 10:57:41 2012 -0500
     3.3 @@ -126,6 +126,31 @@
     3.4     free(it);
     3.5  
     3.6  
     3.7 +   ////////////////////////////////////////
     3.8 +   printf("========================================\nRemoving third element\n");
     3.9 +   it = bst_begin(bst);
    3.10 +   if (NULL == it)
    3.11 +      {
    3.12 +      perror("bst_begin");
    3.13 +      exit(EXIT_FAILURE);
    3.14 +      }
    3.15 +   bst_next(it);
    3.16 +   bst_next(it);
    3.17 +   void * d = bst_remove(it);
    3.18 +   if (NULL == d)
    3.19 +      printf("Unable to remove element!\n");
    3.20 +   else
    3.21 +      free(d);
    3.22 +   free(it);
    3.23 +   it = bst_begin(bst);
    3.24 +   do
    3.25 +      printf("%d\n", *((int *) bst_value(it)));
    3.26 +   while (bst_next(it));
    3.27 +   free(it);
    3.28 +
    3.29 +
    3.30 +
    3.31 +   ////////////////////////////////////////
    3.32     bst_walk_inorder(bst, free_data);
    3.33     bst_delete(bst);
    3.34