Help using _tsearch

[MaurizioF]

Can _tsearch be used to build a binary tree of structures ?
I'd like to use it to quickly search among objects of the following type :

typedef struct {
  COLORREF color;
  HBRUSH brush;
} BrushRef , *PBrushRef;

In this case, color (an integer) should be my key, and brush the associated  payload.
I don't understand what _tsearch returns, and where to put my brushes

The doc says :

To just search the tree, without adding a missing key, use the _tfind function.
Returns:
A pointer to the node on success, otherwise a null pointer.

Does this mean that the key is automatically inserted ?
than why does it returns a  null pointer ?
To what does the pointer points when it's not null ?
(What is a node ?)
How can I insert a key and a value in the tree ?

Any suggestion or example ?
Regards
Maurizio.

[czerny]

I have played a little with Pelles binary tree implementation. But I need a little help. Look the following code:

Code: [Select]

#include <stdio.h>
#include <stdlib.h>
#include <search.h>

typedef unsigned long DWORD;

static void *root = NULL;

int cmp(const void *elem1, const void *elem2)
{
printf("root %p\n", root);
printf("cmp1 %p\n", elem1);
printf("cmp2 %p\n", elem2);

DWORD v1 = *(DWORD*)elem1; // here elem is a DWORD*
DWORD v2 = *(DWORD*)elem2;
printf("v1 %d, v2 %d\n", v1, v2);
return v1 - v2;
}

void show(const void *elem, _VISIT visit, int level)
{
DWORD* v = *(DWORD**)elem; // here elem is a DWORD**
printf("v %d\n", *v);
printf("visit %d\n", visit);
printf("level %d\n", level);
}

int main(int argc, char *argv[])
{
DWORD* key;
void* x;

key = malloc(sizeof(DWORD));
printf("key1 %p\n", key);
*key = 20;
x = _tsearch(key, (void**)&root, cmp);
printf("elem1 %p\n", x);

key = malloc(sizeof(DWORD));
printf("key2 %p\n", key);
*key = 200;
x = _tsearch(key, (void**)&root, cmp);
printf("elem2 %p\n", x);

_twalk(root, show);

return 0;
}
The parameters elem, elem1 and elem2 in the cmp and show functions are all void* but they do not point to the same type of data. In the example they sometimes point to DWORD* or to DWORD**. That's strange!
What do you think?

The next problem is, how to delete the tree. One could use _walk to traverse the tree. But a node is visited more than once (_VISIT). What is the right moment to delete the node. I thought, if (visit == _leaf) but that's not deleting every node.

An other minor flaw is, that the root pointer then has to be a global, because the walk function does not support user data.

[czerny]

Has anybody here ever used Pelles binary tree code?

[frankie]

This is some sample code:

Code: [Select]

#include <search.h>
#define nKeys ((int)(sizeof(keys)/sizeof(int)))

int __cdecl MyCmp(const void *elem1, const void *elem2)
{
return *((int *)(elem1)) - *((int *)(elem2));
}

static int min =  10000;
static int max = -10000;
char *sVisit[] = {"preorder ",
"postorder",
"endorder ",
"leaf     "};

void __cdecl FindMinMax(const void *elem, _VISIT visit, int level)
{
printf("\n[el=% .4d, visit=%s, lev=%d]", **((int **)elem), sVisit[visit], level);
if ((visit == _leaf ||visit == _preorder) && elem)
{
if (**((int **)elem)>= max)
max = **((int **)elem);
if (**((int **)elem)<= min)
min = **((int **)elem);
}
}

void PrintData(int *keys, void **proot, int n)
{
printf("Checking data... ");
for (int i=0; i<n; i++)
{
void *node = _tfind((void *)&keys[i], proot, MyCmp);
if (node)
printf("%d ", **((int **)node));
}
printf("\n");
}

int main(int argc, char *argv[])
{
int keys[] = { 5, -1, 3, -14, 8, 10, 9, 6 };

void *root = NULL;


printf("Inserting data... ");
for (int i=0; i<nKeys; i++)
{
if (_tsearch((void *)&keys[i], &root, MyCmp))
printf ("%d ", keys[i]);
else
printf("\nError!\n");
}
printf("\n");

PrintData(keys, &root, nKeys);

printf("Deleting data... ");
printf ("%d ", **((int **)_tdelete ((void *)&keys[0], &root, MyCmp)));
printf ("%d ", **((int **)_tdelete ((void *)&keys[1], &root, MyCmp)));
printf("\n");

PrintData(keys, &root, nKeys);

printf("Walking data... ");
_twalk(root, FindMinMax);
printf("\n");
printf("Minimum element is %d\n", min);
printf("Maximum element is %d\n", max);
}
EDIT: Improved version

[czerny]

And you too have to use sometimes (int*) and sometimes (int**). That looks odd to me.

[frankie]

It's not odd. The choice of a void pointer allows you to have as element whatever you want, a simple type as an int aor acomplex structure. It's away to generalize the 'object' taht you manage with the btree. 
About pointer and pointers of pointers it depends on what the function returns: the leaf that is a pointer to the element or a node that is a pointer to the structure holding the pointer to the element. Of course the structure is hidden to you.

[czerny]

Sure, a void pointer can point to whatever. But they all are named 'elem' here. If one is been named 'node' and the other 'key', than it would be clear.

[frankie]

I updated the sample...

[czerny]

Code: [Select]

Inserting data... 5 -1 3 -14 8 10 9 6
Checking data... 5 -1 3 -14 8 10 9 6
Deleting data... 8 3
You have deleted the first two keys. Why is 8 and 3 returned?

Code: [Select]

Checking data... 3 -14 8 10 9 6
Walking data...
[el= 0003, visit=preorder , lev=0]
[el=-0014, visit=leaf     , lev=1]
[el= 0003, visit=postorder, lev=0]
[el= 0008, visit=preorder , lev=1]
[el= 0006, visit=leaf     , lev=2]
[el= 0008, visit=postorder, lev=1]
[el= 0010, visit=preorder , lev=2]
[el= 0009, visit=leaf     , lev=3]
[el= 0010, visit=postorder, lev=2]
[el= 0010, visit=endorder , lev=2]
[el= 0008, visit=endorder , lev=1]
[el= 0003, visit=endorder , lev=0]
Minimum element is -14
Maximum element is 10
Why is 3 at level 0 and not 2?
Why is -14 at level 1 and not 2?
Shouldn't 3 be a leaf?
What should 'endorder' be? I have never heard before.
How is it possible to traverse a tree in preorder, postorder or inorder traversal?

[frankie]

Code: [Select]

Inserting data... 5 -1 3 -14 8 10 9 6
Checking data... 5 -1 3 -14 8 10 9 6
Deleting data... 8 3
You have deleted the first two keys. Why is 8 and 3 returned?

I have  not deleted 8 and 3, but I deleted 5 and -1  .
The help for _tdelete says "The argument key points to the element to be deleted. If the node is found, it will be deleted from the tree and returned from _tdelete.", so it should return the deleted key right? Wrong!!! @#!#@@!   
The function return a pointer to the parent node of the removed one!

Code: [Select]

Checking data... 3 -14 8 10 9 6
Walking data...
[el= 0003, visit=preorder , lev=0]
[el=-0014, visit=leaf     , lev=1]
[el= 0003, visit=postorder, lev=0]
[el= 0008, visit=preorder , lev=1]
[el= 0006, visit=leaf     , lev=2]
[el= 0008, visit=postorder, lev=1]
[el= 0010, visit=preorder , lev=2]
[el= 0009, visit=leaf     , lev=3]
[el= 0010, visit=postorder, lev=2]
[el= 0010, visit=endorder , lev=2]
[el= 0008, visit=endorder , lev=1]
[el= 0003, visit=endorder , lev=0]
Minimum element is -14
Maximum element is 10
Why is 3 at level 0 and not 2?
Why is -14 at level 1 and not 2?
Shouldn't 3 be a leaf?

That's absolutely correct. To avoid any problem I rewrote the example:

Code: [Select]

#include<stdio.h>
#include<stdlib.h>
#include <search.h>
#define nKeys ((int)(sizeof(_keys)/sizeof(int)))

int __cdecl MyCmp(const void *elem1, const void *elem2)
{
//printf("comparing %d - %d\n", *((int *)(elem1)), *((int *)(elem2)));
return *((int *)(elem1)) - *((int *)(elem2));
}

static int min =  10000;
static int max = -10000;
char *sVisit[] = {"preorder ",
"postorder",
"endorder ",
"leaf     "};

void __cdecl PrintWalk(const void *elem, _VISIT visit, int level)
{
printf("[el=% .4d, visit=%s, lev=%d]\n", **((int **)elem), sVisit[visit], level);
}

void __cdecl WalkInOrder(const void *elem, _VISIT visit, int level)
{
if (visit==_leaf || visit==_postorder)
printf("[el=% .4d, visit=%s, lev=%d]\n", **((int **)elem), sVisit[visit], level);
}

void __cdecl WalkPreOrder(const void *elem, _VISIT visit, int level)
{
if (visit==_leaf || visit==_preorder)
printf("[el=% .4d, visit=%s, lev=%d]\n", **((int **)elem), sVisit[visit], level);
}

void __cdecl WalkPostOrder(const void *elem, _VISIT visit, int level)
{
if (visit==_leaf || visit==_endorder)
printf("[el=% .4d, visit=%s, lev=%d]\n", **((int **)elem), sVisit[visit], level);
}

void __cdecl FindMinMax(const void *elem, _VISIT visit, int level)
{
PrintWalk(elem, visit, level);
if ((visit == _leaf ||visit == _preorder) && elem)
{
if (**((int **)elem)>= max)
max = **((int **)elem);
if (**((int **)elem)<= min)
min = **((int **)elem);
}
}

void PrintData(int *keys, void **proot, int n)
{
printf("Checking data... ");
for (int i=0; i<n; i++)
{
void *node = _tfind((void *)&keys[i], proot, MyCmp);
if (node)
printf("%d ", **((int **)node));
}
printf("\n");
}

int main(int argc, char *argv[])
{
int _keys[] = { 5, -1, 3, -14, 8, 10, 9, 6 };
int *keys[nKeys] = { NULL };

void *root = NULL;

for (int i=0; i<nKeys; i++)
keys[i] = &_keys[i];

printf("Inserting data... ");
for (int i=0; i<nKeys; i++)
{
if (_tsearch((void *)keys[i], &root, MyCmp))
printf ("%d ", *keys[i]);
else
printf("\nError!\n");
}
printf("\n");

printf ("\nUnordered data\n");
_twalk(root, PrintWalk);
printf ("\nOrdered data\n");
_twalk(root, WalkInOrder);
printf ("\nPreordered data\n");
_twalk(root, WalkPreOrder);
printf ("\nPostordered data\n");
_twalk(root, WalkPostOrder);


printf("\nDeleting data...\n");
void *p = _tdelete ((void *)keys[0], &root, MyCmp);
printf ("% .2d deleted (return value points to %d and root points to %d)\n", *keys[0], **((int **)p), **((int **)root));
p = _tdelete ((void *)keys[1], &root, MyCmp);
printf ("% .2d deleted (return value points to %d and root points to %d)\n", *keys[1], **((int **)p), **((int **)root));
printf("\n");

printf ("\nUnordered data\n");
_twalk(root, PrintWalk);
printf ("\nOrdered data\n");
_twalk(root, WalkInOrder);
printf ("\nPreordered data\n");
_twalk(root, WalkPreOrder);
printf ("\nPostordered data\n");
_twalk(root, WalkPostOrder);

printf("\nWalking data...\n");
_twalk(root, FindMinMax);
printf("\n");
printf("Minimum element is %d\n", min);
printf("Maximum element is %d\n", max);
}
I added a diagram below to show how the tree is built. It is correct. Check it against the program printout.

What should 'endorder' be? I have never heard before.

See below

How is it possible to traverse a tree in preorder, postorder or inorder traversal?

Preorder means that the walk is entering a node with two childerns and moves on left branch descending on values lower than the root value.
Leaf means that this node is an ending node (no childrens).
Postorder means that it is backtracking on the upper node before to move on right branch (greater values), so the actual value is in order with previous values.
Endorder means that it is backtracking to root.

I modified the code to show how the ordered list of elements work.
EDIT: I added the three traversing: inorder, preorder, postorder.

[czerny]

Why is 3 at level 0 and not 2?
Why is -14 at level 1 and not 2?
Shouldn't 3 be a leaf?

That's absolutely correct. To avoid any problem I rewrote the example:

My error! I forgot to remove the two deleted nodes from the tree.

[czerny]

The next problem, I was not aware off is, that the tree is not build in a natural way. In a natural way, the 5 who is first inserted gets the root and will be the root until the 5 shall be deleted. Pelle uses an other insert stategy. May be some way of outobalancing the tree. I don't know! At the end the tree is a sorted binary tree. That's what counts.

[frankie]

The next problem, I was not aware off is, that the tree is not build in a natural way. In a natural way, the 5 who is first inserted gets the root and will be the root until the 5 shall be deleted. Pelle uses an other insert stategy. May be some way of outobalancing the tree. I don't know! At the end the tree is a sorted binary tree. That's what counts.

This should be a self-balanced tree, where the root changes to balance the tree at each isertion/deletion. There should be a trigger level that moves the root to keep both branches almost balanced.
That is the reason because you pass the address of the pointer to root and not the root itself, because in this way the called routine can change the node to which the root points.