# a totally self balanced tree for unsigned integers...

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

1. ### Chris M. ThomassonGuest

Chris M. Thomasson, Feb 14, 2014

2. ### Chris M. ThomassonGuest

"Chris M. Thomasson" wrote in message

[...]

Here is the link to the relevant code:

notice my name in TREE_NAME?

Grrr!!!
____________________________________________________
typedef unsigned int tree_key;

#define BITS 4

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;

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_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)

t = *proot;
key >>= TREE_BITS;

#else

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

else
{
proot = &t->nodes;
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

3. ### Ian CollinsGuest

Chris M. Thomasson wrote:

<stuff>

Why are you responding to an old post in the wrong group?

Ian Collins, Feb 14, 2014
4. ### Chris M. ThomassonGuest

"Ian Collins" wrote in message news:...

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