Thread: Maybe I invented a new type of Balanced Binary Search Tree?

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

This is a simple test code:

Code:

// #############################################################################
// # FileName: topdown.c
// # Author:   Zhang Li, CS0901, HUST
// #############################################################################
#include "topdown.h"

int main()
{
    topdown_tree_node_type* root = NULL;
    topdown_tree_node_type* node;
    size_t i;
    size_t test_size = 200000;

    // insert random data
    for(i = 0; i < test_size; i++)
        root = topdown_tree_insert(root, rand() % test_size);

    // insert nearly ordered data
    for(i = 0; i < test_size; i++)
        root = topdown_tree_insert(root, i + rand() % (test_size - i));

    // search/delete
    for(i = 0; i < test_size; i++)
    {
        node = topdown_tree_search(root, i);
        if(node)
        {
            root = topdown_tree_remove(root, node);
        }
    }

    // destroy
    destroy(root);
    return 0;
}
// #############################################################################
// # EOF

Originally Posted by iMalc

It looks to me to be just a different way of doing an AVL tree, as edivenced by the balance requirement:The number of nodes in a subtree is over twice the number of nodes in the other subtree at more or less the same time that the heights of those subtrees differ by more than one.
Therefore the balancing condition is just changed from directly looking for a height imbalance to slightly indirectly looking for a height imbalance. This does mean that instead of only requiring two bits for the height, you potentially require a lot more. However that has negligible practical difference since you usually use more than 2 bits to store the height anyway.

But it's quite faster than a normal avl tree. My balancing operation is top-down and it doesn't require any recursion or parent pointers, so it can save a lot of time and memory space.
The condition 'child_A.size <= child_B.size * 2 + 1' is only satisfied in the insert/search path, That means the height of tree can be O(n) (like splay tree). This implementation provides amorted O(logn) time.

BTW, the size field requires more memory space, but it is very useful in many operations like ranking and selecting, while the avl's height can do little.

AVL tree implementations do not require a parent pointer. Some implementations do, some don't. My own one does not.

Yes, but you use recursion, that will slow down the speed.

My tree will become unbalanced after times of deletion and one search operation will cost O(n), but searching a deep node will restore most nodes' balance, so it gives O(logn) amortised time.
I can also change the maintain() method and keep balance in deletion, but I found that slower and the code become more complex.
If the O(logn) amortised time can be proved, I think this tree structure can be useful for it simplicity and performance.

I don't understand what useful container operation you could be describing with the terms "ranking" and "selecting", perhaps you could elaborate there a little.

Sorry for my poor English. I mean selecting the Nth node from the tree, and given an index, return the corresponding node.