I wrote this code just for fun, but then I found that it's performance is excellent in both speed (faster then std::map) and memory space, and it's very easy to implement. But I lack some mathemetic knowledge and cannot give any prove or theorem. Can someone have a look on my code?

Code:`// #############################################################################`

// # FileName: topdown.c

// # Author: Zhang Li, CS0901, HUST

// #############################################################################

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// * my topdown balanced tree implementation

// *****************************************************************************

typedef struct topdown_tree_node_struct

{

size_t m_size;

size_t m_data;

struct topdown_tree_node_struct* m_child[2];

} topdown_tree_node_type;

static topdown_tree_node_type nullnode = { 0, 0, { &nullnode, &nullnode }};

static topdown_tree_node_type* destroy(topdown_tree_node_type* root)

{

if(root->m_size > 0)

{

destroy(root->m_child[0]);

destroy(root->m_child[1]);

free(root);

}

return &nullnode;

}

static topdown_tree_node_type* topdown_tree_maintain(

topdown_tree_node_type* root)

{

topdown_tree_node_type* r;

topdown_tree_node_type* c;

topdown_tree_node_type* m;

size_t index = (root->m_child[1]->m_size >= root->m_child[0]->m_size);

// balance requirement:

// child_A.size <= child_B.size * 2 + 1

// once the condition is broke, do a single rotation to repair it

while(root->m_child[index]->m_size > root->m_child[!index]->m_size * 2 + 1)

{

// single rotate

r = root;

c = root->m_child[index];

m = root->m_child[index]->m_child[!index];

c->m_child[!index] = r;

r->m_child[index] = m;

r->m_size = 1 + r->m_child[0]->m_size + r->m_child[1]->m_size;

c->m_size = 1 + c->m_child[0]->m_size + c->m_child[1]->m_size;

root = c;

}

return root;

}

static topdown_tree_node_type* topdown_tree_insert(

topdown_tree_node_type* root, size_t data)

{

topdown_tree_node_type* new_node = malloc(sizeof(topdown_tree_node_type));

topdown_tree_node_type* current_node;

size_t child_index = 0;

new_node->m_data = data;

new_node->m_size = 1;

new_node->m_child[0] = &nullnode;

new_node->m_child[1] = &nullnode;

if(root != NULL)

{

// maintain root (to avoid root changing in the insertion part)

current_node = root = topdown_tree_maintain(root);

while(current_node != new_node)

{

// normal binary search tree's insertion operation

child_index = (data > current_node->m_data);

current_node->m_size += 1;

if(current_node->m_child[child_index]->m_size == 0)

{

current_node->m_child[child_index] = new_node;

// break;

}

// maintain

current_node->m_child[child_index] = topdown_tree_maintain(

current_node->m_child[child_index]);

current_node = current_node->m_child[child_index];

}

return root;

}

return new_node;

}

static topdown_tree_node_type* topdown_tree_search(

topdown_tree_node_type* root, size_t data)

{

topdown_tree_node_type* current_node = root;

size_t child_index = 2;

while(current_node->m_size > 0 && current_node->m_data != data)

{

// maintain

child_index = (data > current_node->m_data);

current_node->m_child[child_index] = topdown_tree_maintain(

current_node->m_child[child_index]);

current_node = current_node->m_child[child_index];

}

if(current_node->m_size > 0)

return current_node;

return NULL;

}

static topdown_tree_node_type* topdown_tree_remove(

topdown_tree_node_type* root, topdown_tree_node_type* node)

{

topdown_tree_node_type* current_node = root;

topdown_tree_node_type* parent_node = &nullnode;

size_t index;

// the tree have only one node, directly delete it

if(root->m_size == 1)

{

free(root);

return &nullnode;

}

// decrease size from root to node

while(current_node != node)

{

current_node->m_size -= 1;

parent_node = current_node;

current_node = parent_node->m_child[node->m_data > parent_node->m_data];

}

// normal deletion operation

while(current_node->m_size > 1)

{

current_node->m_size -= 1;

parent_node = current_node;

for(index = 0; index < 2; index++)

{

if(current_node->m_child[index]->m_size > 0)

{

current_node = current_node->m_child[index];

while(current_node->m_child[!index]->m_size > 0)

{

parent_node = current_node;

current_node->m_size -= 1;

current_node = current_node->m_child[!index];

}

}

}

node->m_data = current_node->m_data;

node = current_node;

}

// delete node

free(current_node);

parent_node->m_child[(parent_node->m_child[1] == current_node)] = &nullnode;

return root;

}

// #############################################################################

// # EOF