15,565,661 members
Articles / Programming Languages / C
Tip/Trick
Posted 4 Sep 2013

70.5K views
24 bookmarked

# Fast Binary Search Trees (BST) using Arrays

Rate me:
This tip explains the usage of arrays for creating Fast 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.

C++
`#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.

C++
```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.

C++
```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.

C++
```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.

C++
```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.

C++
```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

Written By
Architect
India
A programmer by heart since 1998. Written code in C++, Java, JavaScript, Python & Ruby, Worked on Stack Development to Web Development. Data Specialist with SQL and NoSQL DBs

 First Prev Next
 Quite good idea. Member 70399929-Mar-17 4:00 Member 703999 29-Mar-17 4:00
 shared memory bling28-Apr-16 9:39 bling 28-Apr-16 9:39
 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. itsdkg16-May-15 20:49 itsdkg 16-May-15 20:49
 Yes, but use this for the mentioned purpose..its not a balancing algorithm.. No plain BST can be balanced.. Balancing algorithms are AVL etc.
 Re: Sadly this Tree is not friendly to deletes. Will get very unbalanced. FrankLaPiana28-Apr-16 13:30 FrankLaPiana 28-Apr-16 13:30
 [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 itsdkg11-Sep-13 18:29 itsdkg 11-Sep-13 18:29
 example main Member 100596696-Sep-13 7:32 Member 10059669 6-Sep-13 7:32
 Re: example main itsdkg11-Sep-13 18:31 itsdkg 11-Sep-13 18:31
 Code ? _Flaviu4-Sep-13 23:50 _Flaviu 4-Sep-13 23:50
 Re: Code ? itsdkg5-Sep-13 0:14 itsdkg 5-Sep-13 0:14
 Last Visit: 31-Dec-99 19:00     Last Update: 3-Feb-23 23:56 Refresh 1