Help... Binary Search Tree 
Author Message
 Help... Binary Search Tree

Hey everyone,
                Does anyone have the source code of a binary search tree
that includes the initilization, insert and delete functions?  Your help is
much appreciated.

thanks.



Mon, 29 Apr 2002 03:00:00 GMT  
 Help... Binary Search Tree

Quote:

>                 Does anyone have the source code of a binary search tree
> that includes the initilization, insert and delete functions?  Your help is
> much appreciated.

Ironically enough, yes I do.  Hopefully someone will point out
any bugs in the code below, because it's only been tested
superficially with the included test routines.

--bin.h----------------------------------------------------------
/* bin - manipulates binary trees.
   Derived from libavl for manipulation of binary trees.
   Copyright (C) 1998, 1999 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.


   Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
   through more mundane means. */

#if !bin_h
#define bin_h 1

struct bin_tree;

struct bin_tree *bin_create(void);
int bin_search(const struct bin_tree *tree, int item);
int bin_insert(struct bin_tree *tree, int item);
int bin_delete(struct bin_tree *tree, int item);
void bin_walk(const struct bin_tree *tree);
void bin_traverse(const struct bin_tree *tree);
void bin_destroy(struct bin_tree *tree);
int bin_count(const struct bin_tree *tree);

#endif /* bin.h */

--bin.c----------------------------------------------------------
/* bin - manipulates binary trees.
   Derived from libavl for manipulation of binary trees.
   Copyright (C) 1998, 1999 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.


   as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA through
   more mundane means. */

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "bin.h"

struct bin_node {
  int data;
  struct bin_node *left;
  struct bin_node *right;

Quote:
};

struct bin_tree {
  struct bin_node *root;
  int count;

Quote:
};

struct bin_tree *
bin_create(void)
{
  struct bin_tree *tree = malloc(sizeof *tree);
  if (tree == NULL)
    return NULL;
  tree->root = NULL;
  tree->count = 0;
  return tree;

Quote:
}

int
bin_search(const struct bin_tree *tree, int item)
{
  const struct bin_node *node;

  assert(tree != NULL);
  node = tree->root;
  for (;;) {
    if (node == NULL)
      return 0;
    else if (item == node->data)
      return 1;
    else if (item > node->data)
      node = node->right;
    else
      node = node->left;
  }

Quote:
}

int
bin_insert(struct bin_tree *tree, int item)
{
  struct bin_node *node, **new;

  assert(tree != NULL);
  new = &tree->root;
  node = tree->root;
  for (;;) {
    if (node == NULL) {
      node = *new = malloc(sizeof *node);
      if (node == NULL)
        return 0;
      node->data = item;
      node->left = node->right = NULL;
      tree->count++;
      return 1;
    }
    else if (item == node->data)
      return 2;
    else if (item > node->data) {
      new = &node->right;
      node = node->right;
    }
    else {
      new = &node->left;
      node = node->left;
    }
  }

Quote:
}

int
bin_delete(struct bin_tree *tree, int item)
{
  struct bin_node **q, *t;

  assert(tree != NULL);
  q = &tree->root;
  t = tree->root;
  for (;;) {
    if (t == NULL)
      return 0;
    else if (item == t->data)
      break;
    else if (item > t->data) {
      q = &t->right;
      t = t->right;
    }
    else {
      q = &t->left;
      t = t->left;
    }
  }

  if (t->right == NULL)
    *q = t->left;
  else {
    struct bin_node *r = t->right;
    if (r->left == NULL) {
      r->left = t->left;
      *q = r;
    }
    else {
      struct bin_node *s = r->left;
      while (s->left != NULL) {
        r = s;
        s = r->left;
      }
      r->left = s->right;
      s->left = t->left;
      s->right = t->right;
      *q = s;
    }
  }

  tree->count--;
  free(t);
  return 1;

Quote:
}

static void
walk(const struct bin_node *node)
{
  if (node == NULL)
    return;
  walk(node->left);
  printf("%d ", node->data);
  walk(node->right);

Quote:
}

void
bin_walk(const struct bin_tree *tree)
{
  assert(tree != NULL);
  walk(tree->root);

Quote:
}

void
bin_traverse(const struct bin_tree *tree)
{
  struct bin_node *stack[32];
  int count;

  struct bin_node *node;

  assert(tree != NULL);
  count = 0;
  node = tree->root;
  for (;;) {
    while (node != NULL) {
      stack[count++] = node;
      node = node->left;
    }
    if (count == 0)
      return;
    node = stack[--count];
    printf("%d ", node->data);
    node = node->right;
  }

Quote:
}

static void
destroy(struct bin_node *node)
{
  if (node == NULL)
    return;
  destroy(node->left);
  destroy(node->right);
  free(node);

Quote:
}

void
bin_destroy(struct bin_tree *tree)
{
  assert(tree != NULL);
  destroy(tree->root);
  free(tree);

Quote:
}

int
bin_count(const struct bin_tree *tree)
{
  assert(tree != NULL);
  return tree->count;

Quote:
}

/* Print the structure of node NODE of an binary tree, which is LEVEL
   levels from the top of the tree.  Uses different delimiters to
   visually distinguish levels. */
void
print_structure(struct bin_node *node, int level)
{
  assert(level <= 100);

  if (node == NULL) {
    printf(" nil");
    return;
  }
  printf(" %c%d", "([{`/"[level % 5], node->data);
  if (node->left || node->right) {
    print_structure(node->left, level + 1);
    if (node->right)
      print_structure(node->right, level + 1);
  }
  printf("%c", ")]}'\\"[level % 5]);

Quote:
}

/* Examine NODE in a binary tree.  *COUNT is increased by the number
   of nodes in the tree, including the current one.  If the node is
   the root of the tree, PARENT should be INT_MIN, otherwise it should
   be the parent node value.  If this node is a left child of its
   parent node, DIR should be -1.  Otherwise, if it is not the root,
   it is a right child and DIR must be +1.  Sets *OKAY to 0 if an
   error is found. */
void
recurse_tree(struct bin_node *node, int *count, int parent,
             int dir, int *okay)
{
  if (node == NULL)
    return;

  assert(count != NULL);
  (*count)++;

  recurse_tree(node->left, count, node->data, -1, okay);
  recurse_tree(node->right, count, node->data, +1, okay);

  if (parent != INT_MIN) {
    assert(dir == -1 || dir == +1);
    if (dir == -1 && node->data > parent) {
      printf(" Node %d is smaller than its left child %d.\n",
             parent, node->data);
      *okay = 0;
    }
    else if (dir == +1 && node->data < parent) {
      printf(" Node %d is larger than its right child %d.\n",
             parent, node->data);
      *okay = 0;
    }
  }

Quote:
}

/* Checks that TREE's structure is kosher and verifies that the values
   in ARRAY are actually in the tree.  There must be as many elements
   in ARRAY as there are nodes in the tree.  Exits the program if an
   error was encountered. */
void
verify_tree(struct bin_tree *tree, int array[])
{
  int count = 0;
  int okay = 1;

  recurse_tree(tree->root, &count, INT_MIN, 0, &okay);
  if (count != tree->count) {
    printf(" Tree has %d nodes, but tree count is %d.\n",
           count, tree->count);
    okay = 0;
  }

  if (okay) {
    int i;

    for (i = 0; i < tree->count; i++)
      if (!bin_search(tree, array[i])) {
        printf("Tree does not contain expected value %d.\n",
               array[i]);
        okay = 0;
      }
  }

  if (!okay) {
    printf("Error(s) encountered, aborting execution.\n");
    exit(EXIT_FAILURE);
  }

Quote:
}

/* Arrange the N elements of ARRAY in random order. */
void
shuffle(int *array, int n)
{
  int i;

  for (i = 0; i < n; i++) {
    int j = i + rand() % (n - i);
    int t = array[j];
    array[j] = array[i];
    array[i] = t;
  }

Quote:
}

/* Size of tree used for testing. */
#define TREE_SIZE 16

/* Simple stress test procedure for the binary tree routines.  Does
   the following:

   * Generate a random number seed.  By default this is generated from
   the current time.  You can also pass an integer seed value on the
   command line if you want to test the same case.  The seed value is
   displayed.

   * Create a tree and insert the integers from 0 up to TREE_SIZE - 1
   into it, in random order.  Verifies and displays the tree structure
   after each insertion.

   * Removes each integer from the tree, in a different random order.
   Verifies and displays the tree structure after each deletion.

   * Destroys the tree.

   This is pretty good test code if you write some of your own binary
   tree routines.  If you do so you will probably want to modify the
   code below so that it increments the random seed and goes on to new
   test cases automatically. */
int
main(int argc, char **argv)
{
  int array[TREE_SIZE];
  struct bin_tree *tree;
  int i;

  {
    int seed;

    if (argc == 2)
      seed = atoi(argv[1]);
    else
      seed = time(0) * 257 % 32768;
...

read more »



Mon, 29 Apr 2002 03:00:00 GMT  
 Help... Binary Search Tree

Quote:

> I generally make a point of reading your posts since I value what you have
> to say, I wonder however whether this post is really on topic enough to
> warrant such a large posting.

> I know in the past you have simply pointed people to a web page which
> contains the code you posted.
> Did you have a specific reason for not doing this again this time?

It's code that hasn't been put on a webpage or ftp site anywhere
yet.  I felt that it might be interesting to newbies, since we
get requests about binary trees at a fairly good clip around
here.  At any rate, I marked it [LONG!] because I figured some
people might not want to read it simply because of length.

It's unlikely that I'll ever post it again, if that helps.
--
"In My Egotistical Opinion, most people's C programs should be indented six
 feet downward and covered with dirt." -- Blair P. Houghton



Mon, 29 Apr 2002 03:00:00 GMT  
 Help... Binary Search Tree
Hi Ben,

<disclaimer>
I hope this doesn't come across as a 'grumpy' post, but I just /had/ to say
something :)>
</disclaimer>

I generally make a point of reading your posts since I value what you have
to say, I wonder however whether this post is really on topic enough to
warrant such a large posting.

I know in the past you have simply pointed people to a web page which
contains the code you posted.
Did you have a specific reason for not doing this again this time?

Alternatively, surely a better place to post this would have been
alt.source.wanted or somewhere under the comp.sources hierarchy?  I know of
many occasions in the past where a redirection to alt.sources.wanted has
been given.

I realise that you have included a 'please point out any problems in this
code' request, but isn't the normal response to this 'please produce the
shortest possible working program which exhibits the problem....'?

Bryan


Quote:

> >                 Does anyone have the source code of a binary search tree
> > that includes the initilization, insert and delete functions?  Your help
is
> > much appreciated.

> Ironically enough, yes I do.  Hopefully someone will point out
> any bugs in the code below, because it's only been tested
> superficially with the included test routines.

8-< snip of long(?) source code


Tue, 30 Apr 2002 03:00:00 GMT  
 Help... Binary Search Tree
Bad etiquette or not, I very much appreciated your post.  THANK YOU!!!

Just one question, what's the worst case (Big-Oh) for a BST compared to
using a ordinary binary search?  I have an ordered array of about 2000
items that I am using to locate a search item.  I get pretty good
response, but I was wondering if there is much improvement using a BST.
 Obviously, to code it is significantly more than a normal search
routine.  Any guidelines are appreciated.

TIA...

Sent via Deja.com http://www.deja.com/
Before you buy.



Mon, 13 May 2002 03:00:00 GMT  
 Help... Binary Search Tree

Quote:

> Just one question, what's the worst case (Big-Oh) for a BST compared to
> using a ordinary binary search?  I have an ordered array of about 2000
> items that I am using to locate a search item.  I get pretty good
> response, but I was wondering if there is much improvement using a BST.
>  Obviously, to code it is significantly more than a normal search
> routine.  Any guidelines are appreciated.

The asymptotic performance of a well-balanced binary search tree
versus a binary search of an ordered table is the same.  Further
questions along this line should be directed to comp.programming,
since it is off-topic for comp.lang.c.  Followups set.
--
"In My Egotistical Opinion, most people's C programs should be indented six
 feet downward and covered with dirt." -- Blair P. Houghton


Mon, 13 May 2002 03:00:00 GMT  
 Help... Binary Search Tree

Quote:

>Bad etiquette or not, I very much appreciated your post.  THANK YOU!!!

>Just one question, what's the worst case (Big-Oh) for a BST compared to
>using a ordinary binary search?

[This discussion belongs in comp.programming, since this isn't related to C.
I apologize for the off topic discussion; and hope that the followup-to is
respected.]

The answer is that the BST worst case search is O(N) whereas the
binary search worst case is O(log N).  The BST worst case can be fixed
by rebalancing algorithms like AVL or red-black. Techniques can also be used
to make the worst case unlikely, such as randomizing, or using splay operations
to ``clump'' the tree toward the root.

  I have an ordered array of about 2000

Quote:
>items that I am using to locate a search item.  I get pretty good
>response, but I was wondering if there is much improvement using a BST.

Unless you also need efficient insertions and deletions as well, I wouldn't
bother switching. If comparisons are relatively expensive, a hashing technique
might be superior to either trees or binary search. A balanced binary tree of
2000 nodes will have 11 levels (the lowest one being partially filled, short 47
nodes).  Nearly half the nodes are in the bottom row. This means,
statistically, that nearly half of all random searches will require 11
comparisons. That's IF the tree is balanced. Of the remaining ones, nearly half
will require 10 comparisons.  Hashing could reduce the average case to one hash
and one comparison, which could be faster than 10 or 11 comparisons depending
on the speed of the comparison and that of the hashing function.


Mon, 13 May 2002 03:00:00 GMT  
 
 [ 11 post ] 

 Relevant Pages 

1. help in binary search tree

2. Help: Binary Search Trees

3. help binary search tree

4. Help >>On Height Of a Binary Search Tree

5. Binary Search Trees

6. Binary Search Trees

7. Binary search tree

8. binary search tree problem

9. Binary Search Tree using dynamic memory allocation (URGENT request for example)

10. searching for a structure in a binary tree

11. What is the algorithm of binary search tree?

12. Binary search tree doesn't work properly

 

 
Powered by phpBB® Forum Software