What does that binary search tree instruction mean?

[fyra]

Hi everyone. I'm tying to understand the instruction below. I wish someone could explain me what it means:

tree->destroy(((AvlNode*)(*position)->data)->data);



// destroy the left branch of the binary search tree starting from the specified node
static void destroy_left(BisTree* tree, BiTreeNode* node)
{
    BiTreeNode **position;

    // can't remove from an empty tree
    if(bitree_size(tree) == 0)
       return 1;

    // determine where to destroy nodes
    if(node == NULL)
      position = &tree->root;
    else 
      position = &node->left;

    // destroy the nodes
    if(*position != NULL)
    {
       destroy_left(tree,  *position);
       destroy_right(tree, *position);

       if(tree->destroy != NULL)
       {
           // release the data of the AVL node
           tree->destroy(((AvlNode*)(*position)->data)->data);
       }     
    }
}



/*****************************************************************************
*                                                                            *
*  ------------------------------- bistree.h ------------------------------  *
*                                                                            *
*****************************************************************************/

#ifndef BISTREE_H
#define BISTREE_H

#include "bitree.h"

/*****************************************************************************
*                                                                            *
*  Define balance factors for AVL trees.                                     *
*                                                                            *
*****************************************************************************/

#define            AVL_LFT_HEAVY         1
#define            AVL_BALANCED          0
#define            AVL_RGT_HEAVY        -1

/*****************************************************************************
*                                                                            *
*  Define a structure for nodes in AVL trees.                                *
*                                                                            *
*****************************************************************************/

typedef struct AvlNode_ {

void               *data;
int                hidden;
int                factor;

} AvlNode;

/*****************************************************************************
*                                                                            *
*  Implement binary search trees as binary trees.                            *
*                                                                            *
*****************************************************************************/

typedef BiTree BisTree;

/*****************************************************************************
*                                                                            *
*  --------------------------- Public Interface ---------------------------  *
*                                                                            *
*****************************************************************************/

void bistree_init(BisTree *tree, int (*compare)(const void *key1, const void
   *key2), void (*destroy)(void *data));

void bistree_destroy(BisTree *tree);

int bistree_insert(BisTree *tree, const void *data);

int bistree_remove(BisTree *tree, const void *data);

int bistree_lookup(BisTree *tree, void **data);

#define bistree_size(tree) ((tree)->size)

#endif

[Nutster]

What specifically do you need help in understanding this code?

[fyra]

only the instruction below. I know (*position)->data refers to the data of the AvlTree (after the typecast) but why do I need to refer data again? What is this second data? sorry if I wasn't specific before. Your signature is cool.

tree->destroy(((AvlNode*)(*position)->data)->data);

here is the function which contains the instruction:

static void destroy_left(BisTree* tree, BiTreeNode* node) {
    BiTreeNode **position;

    // can't remove from an empty tree
    if (bitree_size(tree) == 0)
        return 1;

    // determine where to destroy nodes
    if (node == NULL)
        position = &tree->root;
    else
        position = &node->left;

    // destroy the nodes
    if (*position != NULL) {
        destroy_left(tree, *position);
        destroy_right(tree, *position);

        if (tree->destroy != NULL) {
            // ????
            tree->destroy(((AvlNode*) (*position)->data)->data);
        }
        // free the AVL node
        free((*position)->data);
        // free its position
        free(*position);
        // set position to NULL
        *position = NULL;
        // update the size of the tree
        tree->size--;
    }
}

[Nutster]

What is tree_destroy? It looks like a function pointer stored within the tree. Also the structure of the tree nodes would be useful in deciphering what is going on here.

BiTreeNode **position; tells us that position is a pointer to a pointer to BiTreeNode. tree->destroy(((AvlNode*) (*position)->data)->data) is looking at position, dereferencing the pointer, look at a BiTreeNode pointer, which is dereference and the data member is referenced. This data member appears to be a pointer itself, so that pointer is followed to another node and it then references that data member, which being a pointer, gets cast to a pointer to AvlNode. The AvlNode pointer is then passed to the destroy function of the tree.

What else it does? I can not tell without more information as stated above.

[fyra]

    tree->destroy(((AvlNode*)(*position)->data)->data);

I think I understood. Is it because of polymorphism? *(position)->data refers to the binary tree node not the AVL node itself. Even making a typecast to a AVL node, we still wouldn't get the data of it. Instead, the data would be the Binary tree data. Therefore, we need to use the member operator again to associate the correct data (the AVL node data) with it.

I base myself on the fact that the binary search tree is a type of a binary tree as you could see in the header I posted before.

the headers of the binary tree and BST follow bellow:

/*****************************************************************************
*                                                                            *
*  ------------------------------- bitree.h -------------------------------  *
*                                                                            *
*****************************************************************************/

#ifndef BITREE_H
#define BITREE_H

#include <stdlib.h>

/*****************************************************************************
*                                                                            *
*  Define a structure for binary tree nodes.                                 *
*                                                                            *
*****************************************************************************/

typedef struct BiTreeNode_ {

  void  *data;
  struct BiTreeNode_* left; 
  struct BiTreeNode_* right;

} BiTreeNode;

/*****************************************************************************
*                                                                            *
*  Define a structure for binary trees.                                      *
*                                                                            *
*****************************************************************************/

typedef struct BiTree_ {

int                size;

int                (*compare)(const void *key1, const void *key2);
void               (*destroy)(void *data);

BiTreeNode         *root;

} BiTree;

/*****************************************************************************
*                                                                            *
*  --------------------------- Public Interface ---------------------------  *
*                                                                            *
*****************************************************************************/

void bitree_init(BiTree *tree, void (*destroy)(void *data));

void bitree_destroy(BiTree *tree);

int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data);

int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data);

void bitree_rem_left(BiTree *tree, BiTreeNode *node);

void bitree_rem_right(BiTree *tree, BiTreeNode *node);

int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data);

#define bitree_size(tree) ((tree)->size)

#define bitree_root(tree) ((tree)->root)

#define bitree_is_eob(node) ((node) == NULL)

#define bitree_is_leaf(node) ((node)->left == NULL && (node)->right == NULL)

#define bitree_data(node) ((node)->data)

#define bitree_left(node) ((node)->left)

#define bitree_right(node) ((node)->right)

#endif




/*****************************************************************************
*                                                                            *
*  ------------------------------- bistree.h ------------------------------  *
*                                                                            *
*****************************************************************************/

#ifndef BISTREE_H
#define BISTREE_H

#include "bitree.h"

/*****************************************************************************
*                                                                            *
*  Define balance factors for AVL trees.                                     *
*                                                                            *
*****************************************************************************/

#define            AVL_LFT_HEAVY         1
#define            AVL_BALANCED          0
#define            AVL_RGT_HEAVY        -1

/*****************************************************************************
*                                                                            *
*  Define a structure for nodes in AVL trees.                                *
*                                                                            *
*****************************************************************************/

typedef struct AvlNode_ {

void               *data;
int                hidden;
int                factor;

} AvlNode;

/*****************************************************************************
*                                                                            *
*  Implement binary search trees as binary trees.                            *
*                                                                            *
*****************************************************************************/

typedef BiTree BisTree;

/*****************************************************************************
*                                                                            *
*  --------------------------- Public Interface ---------------------------  *
*                                                                            *
*****************************************************************************/

void bistree_init(BisTree *tree, int (*compare)(const void *key1, const void
   *key2), void (*destroy)(void *data));

void bistree_destroy(BisTree *tree);

int bistree_insert(BisTree *tree, const void *data);

int bistree_remove(BisTree *tree, const void *data);

int bistree_lookup(BisTree *tree, void **data);

#define bistree_size(tree) ((tree)->size)

#endif

[Nutster]

This is C code, not C++ or something else object-oriented, so polymorphism does not actually apply.

So, the BiTreeNode has a couple of pointers to other nodes, which is typical for a binary tree. It also has a void pointer, which can point to anything; it must be typecast before it can be used. It could point to a double, another node of a binary tree (unusual, but allowed), or some other structure.

I was correct; destroy is a function pointer. When you create the tree, you have to set the function pointer to point to the actual function.

BiTree bt_stuff;

bt_stuff->destroy = bitree_destroy;

bitree_destroy probably calls free() on its argument. So pass it a pointer, and it deallocates what is being pointed at, but that is just a guess.

[fyra]

This is C code, not C++ or something else object-oriented, so polymorphism does not actually apply.

even when you write:

typedef BiTree Bistree;

Can't it be considered as polymorphism?

[Nutster]

No, this is just renaming a type; typedef mean type definition. You are creating a new type based on other type information.

Polymorphism is a mechanism in object-oriented languages where a pointer to a given class can actually refer to not only an object of the given class but to an object of any of its derived classes as well and do this in a type-safe manner. In some object-oriented languages, like VB.Net, the pointer is hidden, but it is still there.

The closest thing in C to this is the use of void * which is basically a pointer to anything and requires typecasting to work, and is most definitely not type-safe. In this binary tree implementation, data is accessed via the void *data, which then gets typecast to its actual data type. If I used the wrong datatype for the typecast, like a double or even a different struct, things get very messed up and we won't know it until the program aborts or you at least get very strange results. The compiler and even the run-time can't help us determine that we have made this kind of mistake.

Oh, I just realized. In my last posting, I said:

bt_stuff->destroy = bitree_destroy;

It should really be:

bt_stuff.destroy = bitree_destroy;

bt_stuff is not a pointer.