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