a totally self balanced tree for unsigned integers...

Discussion in 'C++' started by Chris M. Thomasson, Feb 14, 2014.

  1. Chris M. Thomasson, Feb 14, 2014
    #1
    1. Advertisements

  2. "Chris M. Thomasson" wrote in message

    [...]

    Here is the link to the relevant code:

    https://groups.google.com/forum/#!msg/comp.programming/tjlLW7fFmsE/fXdyD9QcG2cJ

    notice my name in TREE_NAME?

    Grrr!!!
    ____________________________________________________
    typedef unsigned int tree_key;


    #define BITS 4
    #define MASK ~(UINT_MAX << BITS)
    #define NODES (MASK + 1)


    struct tree
    {
    struct tree* nodes[NODES];
    tree_key key;
    };


    struct tree*
    tree_find(struct tree* root,
    tree_key origin_key)
    {
    tree_key key = origin_key;

    while (root)
    {
    if (root->key == origin_key) break;

    root = root->nodes[key & MASK];

    key >>= BITS;
    }

    return root;
    }


    Is that something like what you are thinking of Ben?


    Here is source code for a quick test program that implements the new
    algorithm:


    #include <stdio.h>
    #include <assert.h>
    #include <stdlib.h>
    #include <string.h>
    #include <limits.h>
    #include <time.h>

    #define QUOTEX(t)#t
    #define QUOTE(t)QUOTEX(t)


    #define HASH_DEPTH 1


    #define HASH(k) ((k) & (HASH_DEPTH - 1))

    #define TREE_BITS 4
    #define TREE_MASK ~(UINT_MAX << TREE_BITS)
    #define TREE_NODES (TREE_MASK + 1)


    #define TREE_SEARCH_ALGO_BINARY 0
    #define TREE_SEARCH_ALGO_BIT 1

    #define TREE_SEARCH_ALGO TREE_SEARCH_ALGO_BIT


    #if (TREE_SEARCH_ALGO == TREE_SEARCH_ALGO_BINARY)
    # undef TREE_NODES
    # define TREE_NODES 2
    # define TREE_NAME "Normal Binary Tree\n\n\n"
    #else
    # define TREE_NAME "Chris' %lu-Ary %lu-Bit Trie?\n\n\n", \
    TREE_NODES, TREE_BITS
    #endif


    typedef unsigned int tree_key;


    static unsigned long int g_tree_search_count = 0;
    static unsigned long int g_tree_search_count_max = 0;
    static unsigned long int g_tree_search_count_min = 0;

    struct tree
    {
    struct tree* nodes[TREE_NODES + 2];
    tree_key key;
    };


    struct hash
    {
    struct tree* buckets[HASH_DEPTH];
    };

    #define HASH_INIT { { NULL } }


    struct tree*
    tree_sys_find(struct tree*** pproot,
    tree_key origin_key)
    {
    tree_key key = origin_key;

    unsigned long int count = 0;
    struct tree** proot = *pproot;
    struct tree* t = *proot;
    while (t)
    {
    ++count;

    if (t->key == origin_key)
    {
    break;
    }


    #if (TREE_SEARCH_ALGO == TREE_SEARCH_ALGO_BIT)

    proot = &t->nodes[key & TREE_MASK];
    t = *proot;
    key >>= TREE_BITS;

    #else

    if (origin_key < t->key)
    {
    proot = &t->nodes[0];
    t = *proot;
    }

    else
    {
    proot = &t->nodes[1];
    t = *proot;
    }

    #endif

    }

    *pproot = proot;

    g_tree_search_count += count;

    if (count > g_tree_search_count_max)
    {
    g_tree_search_count_max = count;
    }
    else
    {
    g_tree_search_count_min = count;
    }

    return t;
    }


    int
    tree_insert(struct tree** proot,
    struct tree* tnew)
    {
    if (! tree_sys_find(&proot, tnew->key))
    {
    memset(tnew->nodes, '\0', sizeof(tnew->nodes));
    *proot = tnew;
    }
    return 0;
    }


    struct tree*
    tree_find(struct tree** proot,
    tree_key key)
    {
    return tree_sys_find(&proot, key);
    }

    void
    tree_iterate(struct tree* root)
    {
    if (root)
    {
    size_t i;

    for (i = 0; i < TREE_NODES; ++i)
    {
    tree_iterate(root->nodes);
    }

    printf("tree_iterate: %lu\n", root->key);
    }
    }


    int
    hash_insert(struct hash* h,
    struct tree* tnew)
    {
    return tree_insert(&h->buckets[HASH(tnew->key)], tnew);
    }

    struct tree*
    hash_find(struct hash* h,
    tree_key key)
    {
    return tree_find(&h->buckets[HASH(key)], key);
    }

    #define DEPTH 1000000


    int main(void)
    {
    size_t i;
    struct tree* tn;
    static struct tree nodes[DEPTH];

    static struct hash hash_init = HASH_INIT;
    struct hash h = hash_init;

    srand((unsigned int)time(NULL));


    printf("Testing Algorithm: " TREE_NAME);


    puts("\nRandomized Insertion\n"
    "----------------------------------------");


    g_tree_search_count = 0;
    g_tree_search_count_max = 0;
    g_tree_search_count_min = ULONG_MAX;
    for (i = 0; i < DEPTH; ++i)
    {
    nodes.key = rand();
    hash_insert(&h, nodes + i);
    }
    for (i = 0; i < DEPTH; ++i)
    {
    tn = hash_find(&h, nodes[DEPTH - i - 1].key);
    if (! tn)
    {
    assert(tn);
    abort();
    }

    if (tn->key != nodes[DEPTH - i - 1].key)
    {
    assert(tn->key == nodes[DEPTH - i - 1].key);
    abort();
    }
    }
    printf("inserts/finds: %lu\n"
    "hash depth: %lu\n"
    "average: %lu\n"
    "maximum: %lu\n"
    "minimum: %lu\n",
    DEPTH,
    HASH_DEPTH,
    (g_tree_search_count / 2) / DEPTH,
    g_tree_search_count_max,
    g_tree_search_count_min);

    puts("\n\n\nSequential Worst-Case Insertion\n"
    "----------------------------------------");
    ____________________________________________________
    [...]
     
    Chris M. Thomasson, Feb 14, 2014
    #2
    1. Advertisements

  3. Chris M. Thomasson

    Ian Collins Guest

    Chris M. Thomasson wrote:

    <stuff>

    Why are you responding to an old post in the wrong group?
     
    Ian Collins, Feb 14, 2014
    #3
  4. "Ian Collins" wrote in message news:...
    Sorry about that Ian.

    FWIW, I have to convert my old C code to C++.

    I will go ahead and post it here when I am done. AFAICT, it's a
    pretty useful tree algorithm.
     
    Chris M. Thomasson, Feb 15, 2014
    #4
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.