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