Generic Self-Balancing Binary Search Tree in C

Code can be found here

Examples can be found here

An example using a user defined type, complete with predicate and print functions can be found here

Functionalities

• Insertion

• Removal

• Finding

• Copying

• Union

• Deallocation

• Iterators

  • Bidirectional (Move in the inorder fashion)
  • Interfaces Supported:
    • begin
    • end
    • has_next
    • get_next
    • has_prev
    • get_prev
    • equals
    • dereference

Usage of BST

Inclusion

#include "bst.h"

Declaration and Initialization

Bst t;
init_bst(&t);

Insertion

For insertion, a predicate function must be provided. Here is an example of a predicate function for the type int

bool less_int(const void * x, const void *y)
{
  return *(int*)x < *(int*)y;
}

// assuming type int
int a = 10;
bst_insert(&t, &a, less_int);

Here, t is of type Bst, a can be of any type, less_int is the predicate function that determines the inherent association between data in the tree.

To insert an array of elements:

Syntax: bst_array_insert(<tree>, <array>, <length_of_array>, <predicate>);

int len = 6;
int elts[] = {1, 2, 0, 8, -7, 15};

bst_array_insert(&tree, elts, len, less_int);

Removal

For removal, a predicate function must be provided.

int a = 10;
bst_remove(&t, &a, less_int);

Here, t is of type Bst, a can be of any type, less_int is the predicate function that determines the inherent association between data in the tree.

Finding

For finding, a predicate function must be provided.

#include "bst_iterator.h"

int a = 10;
bst_iterator it = bst_find(&t, &a, less_int);

Here, it is of type bst_iterator, t is of type Bst, a can be of any type, less_int is the predicate function that determines the inherent association between data in the tree.

Copying

// assume tree is of type Bst

Bst tree_copy;
init_bst(&tree_copy);

bst_copy(&tree_copy, &tree);

Union

Syntax: bst_union(<destination>, <tree1>, <tree2>, <predicate>);

Bst unified;
init_bst(&unified);

bst_union(&unified, &tree_1, &tree_2, less_double);

Here, tree_1 and tree_2 are of type Bst, less_int is the predicate function that determines the inherent association between data in the tree.

Traversal

A function must be provided for printing the generic data contained in the tree. An example of such a function for the type int is as follows:

void print_int(const void *ptr)
{
  printf("%d\t", *(int*)ptr);
}

The supported methods of traversal are:

inorder(&t, print_int);
preorder(&t, print_int);
postorder(&t, print_int);

Deallocation

This is a very important step to stop to avoid memory leaks

deallocate_bst(&t);

Usage of BST Iterators

Inclusion

#include "bst_iterator.h"

Begin

bst_iterator it = begin(&t);

End

bst_iterator it = end(&t);

Forward Iteration

Check and go forward

bst_iterator it = begin(&t);
if (has_next(it)) {
	it = get_next(it);
}

Check and go backward

bst_iterator it = end(&t);
if (has_prev(it)) {
	it = get_prev(it);
}

Iterator Equality

bst_iterator it1 = begin(&t);
bst_iterator it2 = begin(&t);

if (equals(it1, it2)) {
	printf("Equal\n");
}

Iterator Dereferencing

Dereferencing the iterator returns the generic data. Typecasting is required. One way to print the dereferenced value is as follows:

void print_int(const void *ptr)
{
  printf("%d\t", *(int*)ptr);
}

bst_iterator it = begin(&t);

if (dereference(it)) {
	print_int(dereference(it));
}