Click here to Skip to main content
Click here to Skip to main content

Tagged as

Fast Binary Search Trees (BST) using Arrays

, 5 Sep 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
This tip explains the usage of arrays for creating binary search trees.

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Deepak Kumar Gupta
Architect
India India
I love programming and started (in 1995)even before I got some professional education on the same. Since then I've worked on IP network stack (written IPv6 stack and next generation TCP Stack), VoIP, IP Security (IKE / IPSec).
My preferred programming language is C++ and I always explore the ways to improve the A.I based systems using enhanced algorithms and data structures.

Comments and Discussions

 
Question[My vote of 2] Fast but inefficient PinmemberYvesDaoust9-Sep-13 0:33 
AnswerRe: [My vote of 2] Fast but inefficient PinmemberDeepak Kumar Gupta11-Sep-13 18:29 
Questionexample main PinmemberMember 100596696-Sep-13 7:32 
AnswerRe: example main PinmemberDeepak Kumar Gupta11-Sep-13 18:31 
QuestionCode ? PinmemberFlaviu24-Sep-13 23:50 
AnswerRe: Code ? PinmemberDeepak Kumar Gupta5-Sep-13 0:14 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.1411023.1 | Last Updated 5 Sep 2013
Article Copyright 2013 by Deepak Kumar Gupta
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid