C++ Binary Search Tree array implementation

[Frank_5]

//Description: Binary Search Tree with array implementation, it has inorder, postorder and pre order traversals.
//Note: it is not advisable to use array in binary search tree because it consumes a lot of memory in the long run
// instead use linked list this is just a reference to understand more about BST. Good luck and Happy coding
// Frank Mendez



#include<iostream>
using namespace std;


public:
    int size;
    int* array;

    void insertElement(int x);
    void searchElement(int x);
    void inOrder(int currentIndex);
    void preOrder(int currentIndex);
    void postOrder(int currentIndex);
    void parent(int x);
    int extendSize(int x);

    BinarySearchTree (int size) {
        this -> size = extendSize(size);
        //cout << this -> size << endl;
        this -> array = new int[this -> size];
        for(int x = 0; x < this -> size; x++){
            array[x] = NULL;
        }
    }
};

int BinarySearchTree::extendSize(int x) {
    int value = 0;
    for(int y = 0; y < x + 1; y++) {
        value = (2 * value) + 2;
    }
    return value;
}

void BinarySearchTree::insertElement(int x) {
    int currentIndex = 0;
    cout << "Adding: " << x;
    while(true) {
        if(array[currentIndex] == NULL){
            array[currentIndex] = x;
            cout << " Inserted at index: " << currentIndex << endl;
            break;
        }else if(array[currentIndex] <= x) {
            if(array[currentIndex] == x){
                cout << "ERROR!-- Repeating element" << endl;
                break;
            }else
            cout << " Right ";
            currentIndex = (2 * currentIndex + 2);
        }else if(array[currentIndex] >= x) {
             if(array[currentIndex] == x){
                cout << "ERROR!-- Repeating element" << endl;
                break;
            }else
            cout << " Left ";
            currentIndex = (2 * currentIndex + 1);
        }

    }
}

void BinarySearchTree::searchElement(int x){
    int currentIndex = 0;
    while (true) {
            if (array[currentIndex] == NULL) {
            cout << "Not Found" << endl;
            break;
            }
            if (array[currentIndex] == x) {
            cout << "Found at index: " << currentIndex << endl;
            break;
            }
            else if(array[currentIndex] < x) {
            currentIndex = (2 * currentIndex + 2);
        }
            else if(array[currentIndex] > x) {
            currentIndex = (2 * currentIndex + 1);
        }

    }

}

void BinarySearchTree::parent(int x){
    while (x != 0) {
        x = (x-1) / 2;
        cout << "---";
    }

}

void BinarySearchTree::inOrder(int currentIndex){
    if(array[currentIndex] != NULL) {
            inOrder(2 * currentIndex + 1);
            parent(currentIndex);
            cout << array[currentIndex] << endl;
            inOrder(2 * currentIndex + 2);

    }
}

void BinarySearchTree::postOrder(int currentIndex) {
    if(array[currentIndex] != NULL){
        postOrder(2 * currentIndex + 1);
        postOrder(2 * currentIndex + 2);
        parent(currentIndex);
        cout << array[currentIndex] << " " << endl;
    }

}

void BinarySearchTree::preOrder(int currentIndex) {
    if(array[currentIndex] != NULL) {
        preOrder(2 * currentIndex + 1);
        parent(currentIndex);
        cout << array[currentIndex] << " " << endl;
        preOrder(2 * currentIndex + 2);
    }
}

int main () {
    BinarySearchTree frank(5);
    frank.insertElement(4);
    frank.insertElement(6);
    frank.insertElement(9);
    frank.insertElement(3);
    frank.insertElement(2);
    frank.searchElement(1);
    frank.inOrder(0);
};

[rubberman]

And your problem is?

[Lucaci Andrew]

If you have any problems please post your questions.
If you just want to contribute to DaniWeb with Sample codes, please post your code in a Code Snippet thread format.

[mike_2000_17]

If you don't have a question and this is just a code snippet, then just say so, I'd be happy to turn the post into a code snippet.

About the code though, the one thing that really caught my eye was this statement that:

"Note: it is not advisable to use array in binary search tree because it consumes a lot of memory in the long run instead use linked list this is just a reference to understand more about BST."

Well, it is true that this kind of breadth-first layout in an array will require keeping a larger array then absolutely necessary. This is especially true in your implementation because you are not doing any tree-balancing. If there is anything that makes your code unusable in practice, it is the fact that your BST is not being dynamically re-balanced, and this is true regardless of the underlying storage (linked-structure or a contiguous array layout).

However, with a properly balanced tree, storing the values in a contiguous array layout is actually not that bad in terms of memory usage, as it uses, on average, about 50% too much memory. And if your elements are small, this can be much less memory overhead than what a linked-structure requires (for link pointers). Not to mention that most contiguous array implementations, like the classic Dynamic Array, will use an exponential growth strategy that results in a similar kind of memory overhead.

Finally, the main benefit of using a contiguous array layout like this is memory locality (or locality of reference). In fact, I believe that the breadth-first layout is demonstrably the most cache-efficient storage strategy for a BST. While, of course, a linked-list or linked-structure storage strategy is by nature the most cache-inefficient strategy you could possibly choose. In my own personal experience, whenever I have tested the performance difference between using breadth-first layout or a linked-structure for storing a BST, the array layout is exponentially faster than the linked-structure. This is entirely due to reducing cache-misses.

The truth is, linked-structures should never be used for any traversal-intensive implementation. In other words, if your main purpose is to traverse the structure (e.g., to look for an insertion point, to look for an element or range, or to just apply some transformation, etc.), then don't use a linked-structure, that will completely kill your performance, completely.

[rubberman]

Agree with Mike2k entirely! In the deep, dark past (about 20 years ago) I replaced a linked-list structure with a self-balancing sorted array implementation. The performance increase was at least 2 orders or magnitude, and more for inserting sorted data (I used a head/tail optimized algorithm). When the array needed to be enlarged, I would use a realloc() function and increase the size by 2x. This ended up being very optimal in terms of performance and memory usage, even with quite large collections (thousands to millions of objects). So, I created an adaptation of the bsearch() routine that would return the insert location, and then you can move the remainder of the array down one position (memmove()) quite efficiently. I'd post the code here, but it is the property (now) of Applied Materials.

[mike_2000_17]

@rubberman: It is more than a lot more efficient, it is, as I said, exponentially faster. Here is a graph of the performance of nearest-neighbor queries in a DVP-tree (which is a kind of metric-space partitioning tree, which is very similar to a BST, just with more complicated splitting logic). The DVP-tree implementation is identical in both cases, only the tree storage data structure is different (Graph == linked-tree structure, and B-Tree == breadth-first layout in a contiguous array (vector)). As seen, when relying on a linked-structure, it barely matches up with linear search (i.e., it's initially O(log(n)) but ends up at O(n) complexity), and when relying on contiguous storage, it's logarithmic O(log(n)) performance. The difference is purely due to cache thrashing when using a linked-structure. This is why I say it is exponentially faster when you have cache-friendly storage and predictable memory-access patterns.

[surajsokasane]

Your preorder and inorder functions written above are same..! there should be some change in inorder..

it should be:

void BinarySearchTree::inOrder(int currentIndex){
    if(array[currentIndex] != NULL) {
            parent(currentIndex);
            cout << array[currentIndex] << endl;
            inOrder(2 * currentIndex + 1);
            inOrder(2 * currentIndex + 2);
    }
}

am I right??