Exponential tree implementation

Question

I was trying to implement exponential tree from documentation, but here is one place in the code which is not clear for me how to implement it:

#include<iostream>
using namespace std;
struct node
{
    int level;
    int count;
    node **child;
    int data[];

};
int binary_search(node *ptr,int element)
{
    if(element>ptr->data[ptr->count-1]) return ptr->count;
    int start=0;
    int end=ptr->count-1;
    int mid=start+(end-start)/2;
    while(start<end)
    {
        if(element>ptr->data[mid]) { start=mid+1;}
        else
        {
            end=mid;
        }

        mid=start+(end-start)/2;

    }

    return mid;
}
void insert(node *root,int element)
{
    node *ptr=root,*parent=NULL;
    int i=0;
    while(ptr!=NULL)
    {

        int level=ptr->level,count=ptr->count;
        i=binary_search(ptr,element);
        if(count<level){
            for(int j=count;j<=i-1;j--)
                ptr->data[j]=ptr->data[j-1];
        }
            ptr->data[i]=element;
            ptr->count=count+1;
            return ;

        }

    parent=ptr,ptr=ptr->child[i];

    //Create a new Exponential Node at ith child of parent and
//insert element in that

    return ;

}
int main()
{


return 0;
}

Here is a link for the paper I'm referring to: http://www.ijcaonline.org/volume24/number3/pxc3873876.pdf This place is in comment, how can I create a new exponential node at level i? Like this?

parent->child[i]=new node;
insert(parent,element);

score 2 · Answer 1 · edited May 23 '17 at 12:20

The presence of the empty array at the end of the structure indicates this is C style code rather than C++ (it's a C Hack for flexible arrays). I'll continue with C style code as idiomatic C++ code would prefer use of standard containers for the child and data members.

Some notes and comments on the following code:

There were a number of issues with the pseudo-code in the linked paper to a point where it is better to ignore it and develop the code from scratch. The indentation levels are unclear where loops end, all the loop indexes are not correct, the check for finding an insertion point is incorrect, etc....
I didn't include any code for deleting the allocated memory so the code will leak as is.
Zero-sized arrays may not be supported by all compilers (I believe it is a C99 feature). For example VS2010 gives me warning C4200 saying it will not generate the default copy/assignment methods.
I added the createNode() function which gives the answer to your original question of how to allocate a node at a given level.
A very basic test was added and appears to work but more thorough tests are needed before I would be comfortable with the code.
Besides the incorrect pseudo-code the paper has a number of other errors or at least questionable content. For example, concerning Figure 2 it says "which clearly depicts that the slope of graph is linear" where as the graph is clearly not linear. Even if the author meant "approaching linear" it is at least stretching the truth. I would also be interested in the set of integers they used for testing which doesn't appear to be mentioned at all. I assumed they used a random set but I would like to see at least several sets of random numbers used as well as several predefined sets such as an already sorted or inversely sorted set.

.

int binary_search(node *ptr, int element)
{
    if (ptr->count == 0) return 0;
    if (element > ptr->data[ptr->count-1]) return ptr->count;   

    int start = 0;
    int end = ptr->count - 1;
    int mid = start + (end - start)/2;

    while (start < end)
    {
        if (element > ptr->data[mid]) 
            start = mid + 1;
        else
            end = mid;

        mid = start + (end - start)/2;
    }

    return mid;
}


node* createNode (const int level)
{
    if (level <= 0) return NULL;

        /* Allocate node with 2**(level-1) integers */
    node* pNewNode = (node *) malloc(sizeof(node) + sizeof(int)*(1 << (level - 1))); 
    memset(pNewNode->data, 0, sizeof(int) * (1 << (level - 1 )));

        /* Allocate 2**level child node pointers */
    pNewNode->child = (node **) malloc(sizeof(node *)* (1 << level));
    memset(pNewNode->child, 0, sizeof(int) * (1 << level));

    pNewNode->count = 0;
    pNewNode->level = level;

    return pNewNode;
}


void insert(node *root, int element)
{
    node *ptr = root;
    node *parent = NULL;
    int i = 0;

    while (ptr != NULL)
    {
        int level = ptr->level;
        int count = ptr->count;
        i = binary_search(ptr, element);

        if (count < (1 << (level-1)))
        {
            for(int j = count; j >= i+1; --j)
                ptr->data[j] = ptr->data[j-1];

            ptr->data[i] = element;
            ++ptr->count;
            return;
        }

        parent = ptr;
        ptr = ptr->child[i];
    }

    parent->child[i] = createNode(parent->level + 1);
    insert(parent->child[i], element);    
}


void InOrderTrace(node *root)
{
    if (root == NULL) return;

    for (int i = 0; i < root->count; ++i)
    {
        if (root->child[i]) InOrderTrace(root->child[i]);
        printf ("%d\n", root->data[i]);
    }

    if (root->child[root->count]) InOrderTrace(root->child[root->count]);
}


void testdata (void)
{
    node* pRoot = createNode(1);

    for (int i = 0; i < 10000; ++i)
    {
        insert(pRoot, rand());
    }

    InOrderTrace(pRoot);
}

Exponential tree implementation

1 Answers1