12,067,351 members (55,030 online)
Tip/Trick
alternative version

25.5K views
14 bookmarked
Posted

# Fast Binary Search Trees (BST) using Arrays

, 5 Sep 2013 CPOL
 Rate this:
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

## Share

 Architect 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.

## You may also be interested in...

 First Prev Next
 Sadly this Tree is not friendly to deletes. Will get very unbalanced. Spundun Bhatt12-Feb-15 13:08 Spundun Bhatt 12-Feb-15 13:08
 Re: Sadly this Tree is not friendly to deletes. Will get very unbalanced. Deepak Kumar Gupta16-May-15 20:49 Deepak Kumar Gupta 16-May-15 20:49
 [My vote of 2] Fast but inefficient YvesDaoust9-Sep-13 0:33 YvesDaoust 9-Sep-13 0:33
 Re: [My vote of 2] Fast but inefficient Deepak Kumar Gupta11-Sep-13 18:29 Deepak Kumar Gupta 11-Sep-13 18:29
 example main Member 100596696-Sep-13 7:32 Member 10059669 6-Sep-13 7:32
 Re: example main Deepak Kumar Gupta11-Sep-13 18:31 Deepak Kumar Gupta 11-Sep-13 18:31
 Code ? Flaviu24-Sep-13 23:50 Flaviu2 4-Sep-13 23:50
 Re: Code ? Deepak Kumar Gupta5-Sep-13 0:14 Deepak Kumar Gupta 5-Sep-13 0:14
 Last Visit: 31-Dec-99 19:00     Last Update: 8-Feb-16 4:13 Refresh 1