Fast Binary Search Trees (BST) using Arrays

• Download source - 710 B

Introduction

Creating a tree data structure involves lots of pointer manipulation and memory overhead. In my article, Creating BST using STL vector, I tried to get rid of pointer manipulations. However, the STL based BST data structure makes it slow and unusable for large data. In this tip, I will be showing how to create a fast and efficient binary search tree using C/C++ arrays. The only condition is that we need to know the maximum number of elements this data structure will have in its lifetime.

This implementation is different than normal array index calculation of 2*n + 1 and 2*n + 2 for left and right child. In this example, the elements will be added in sequence and there left and right indexes are stored in BST data structure.

Background

Creating binary search trees using C/C++ arrays is not a new idea, but the algorithm to calculate the left and right sub child makes array size much more than number of elements.

Consider the creation of this BST example:

• Insert (50), since this is the first element, it is added at index [0] and becomes the root element.
• Insert (30) which is left sub child of root and array index will be [2*n + 1] = [2 * 0 + 1] = [1]
• Insert (60) which is right sub child of root and array index will be [2*n + 2] = [2*0 + 2] = [2]
• Insert (15), this will be left sub child of (30) and index will be [2*n + 1] = [2*1 + 1] = [3]
• Insert (70), this will be the right sub child of (60) and index will be [2*n + 2] = [2*2 + 2] = [6]
  
  In this case, an array of size = 7 is required for 5 elements. This will grow as we keep on including elements. Let me also explain that a perfectly balanced binary search tree doesn't waste array elements, so this example will be useful for real life scenarios where order of elements may not result in perfectly balanced binary trees.

Using the Code

First, I will define the maximum array elements our binary search tree can hold.

#define MAX_ELEMS 100

Then I'll define the binary search tree data structures. normal data structures are pointer based with pointer to left and right sub child. Since we're dealing with the array indexes, I will define left and right sub child as array indexes to make this code to be as generic as possible.

struct bst
{
	int data;
	int lindex;
	int rindex;
};

Here I'm defining functions for creating the tree and inserting in left and right child. These functions assume that the node is already created.

void MakeNode(struct bst * tree, int data)
{
	tree->data = data;
	tree->lindex = tree->rindex = -1;
}

void Insertleft( struct bst *tree, int data)
{
	MakeNode(tree, data);
}

void Insertright( struct bst * tree, int data)
{
	MakeNode(tree, data);
}

Now, here is the insert function which will add binary search tree elements one by one in its appropriate place. The index assignments will be done in this function itself.

void Insert(struct bst * tree, int treeIndex, int data)
{
	int baseIndex = 0;
	
	while(baseIndex <= treeIndex)
	{
		if(data <= tree[baseIndex].data)
		{
			if(tree[baseIndex].lindex == -1)
			{
				tree[baseIndex].lindex = treeIndex;
				Insertleft(&tree[treeIndex], data);
				return;
			}
			else
			{
				baseIndex = tree[baseIndex].lindex;
				continue;
			}

		}
		else // data is > tree[baseIndex].data
		{
			if(tree[baseIndex].rindex == -1)
			{
				tree[baseIndex].rindex = treeIndex;
				Insertright(&tree[treeIndex], data);
				return;
			}
			else
			{
				baseIndex = tree[baseIndex].rindex;
				continue;
			}
		}
	}
}

Since we have the trees, we need to traverse the trees also. I'm writing the functions to traverse the trees in in-order, pre-order, and post-order manner.

void Intrav(struct bst * tree, int index)
{
	if(tree[index].lindex != -1)
		Intrav( tree, tree[index].lindex );
	cout<<"DataIn ="<<tree[index].data<<endl;
	if(tree[index].rindex != -1)
		Intrav( tree, tree[index].rindex );
}

void Pretrav(struct bst * tree, int index)
{
	cout<<"DataPre ="<<tree[index].data<<endl;
	if(tree[index].lindex != -1)
		Pretrav( tree, tree[index].lindex );
	if(tree[index].rindex != -1)
		Pretrav( tree, tree[index].rindex );
}

void Posttrav(struct bst * tree, int index)
{
	if(tree[index].lindex != -1)
		Posttrav( tree, tree[index].lindex );
	if(tree[index].rindex != -1)
		Posttrav( tree, tree[index].rindex );
	cout<<"DataPost ="<<tree[index].data<<endl;
}

Here is a simple main function to demonstrate the functionality of the tree. The only thing to take into account is that the array index is incremented after addition of each element.

int main()
{
	struct bst tree[MAX_ELEMS];
	memset(tree, 0, sizeof(tree));
	int treeIndex = 0;

	MakeNode(&tree [treeIndex], 50);
	treeIndex++;
	Insert(tree, treeIndex, 10);
	treeIndex++;
	Insert(tree, treeIndex, 60);
	treeIndex++;
	Insert(tree, treeIndex, 25);
	treeIndex++;
	Insert(tree, treeIndex, 30);
	treeIndex++;
	Insert(tree, treeIndex, 92);
	treeIndex++;
	Insert(tree, treeIndex, 15);
	treeIndex++;
	Insert(tree, treeIndex, 67);
	
	Intrav(tree, 0);
	Pretrav(tree,0);
	Posttrav(tree, 0);

	return 0;
}

Points of Interest

1. A fast BST
2. Less penalty with unbalanced trees as compared to pointer based unbalanced trees
3. Maximum size has to be known in the beginning, however you can tweak with re-alloc based logics

History

• First version