Pass argument value by pointer in function in c

Question

I am a newbie in learning c..... So I am trying to create a tree structure from inputs like:

(2, 50) (4, 30) (9, 30) (10, 400) (-5, -40)
(7, 20) (19, 200) (20, 50) (-18, -200) (-2, 29)
(2, 67) (4, 35) (9, 45) (-18, 100)

Firstly, I have defined some data structures and auxiliary function as below:

typedef struct AVLTreeNode
{
    int key;                    //key of this item
    int value;                  //value (int) of this item
    int height;                 //height of the subtree rooted at this node
    struct AVLTreeNode *parent; //pointer to parent
    struct AVLTreeNode *left;   //pointer to left child
    struct AVLTreeNode *right;  //pointer to right child
} AVLTreeNode;

//data type for AVL trees
typedef struct AVLTree
{
    int size;          // count of items in avl tree
    AVLTreeNode *root; // root
} AVLTree;

// create a new AVLTreeNode
AVLTreeNode *newAVLTreeNode(int k, int v)
{
    AVLTreeNode *newNode;
    newNode = malloc(sizeof(AVLTreeNode));
    assert(newNode != NULL);
    newNode->key = k;
    newNode->value = v;
    newNode->height = 0;  // height of this new node is set to 0
    newNode->left = NULL; // this node has no child
    newNode->right = NULL;
    newNode->parent = NULL; // no parent
    return newNode;
}

// create a new empty avl tree
AVLTree *newAVLTree()
{
    AVLTree *T;
    T = malloc(sizeof(AVLTree));
    assert(T != NULL);
    T->size = 0;
    T->root = NULL;
    return T;
}

Then I wrote a function to insert each pair of data into the tree:

int InsertNode(AVLTree *T, int k, int v)
{
    AVLTreeNode *currentNode = T->root;
    AVLTreeNode *parent;
    //if the tree/subtree is empty
    if (currentNode == NULL)
    {
        currentNode = newAVLTreeNode(k, v);
    }
    //keys are equal
    else
    {
        while (currentNode != NULL)
        {
            parent = currentNode;
            if (k == currentNode->key)
            {
                if (v == currentNode->value)
                {
                    return 0;
                }
                else if (v < currentNode->value)
                {
                    currentNode = currentNode->left;
                }
                else if (v > currentNode->value)
                {
                    currentNode = currentNode->right;
                }
            }
            else if (k < currentNode->key)
            {
                currentNode = currentNode->left;
            }
            else if (k > currentNode->key)
            {
                currentNode = currentNode->right;
            }
        }

        currentNode = newAVLTreeNode(k, v);
        currentNode->parent = parent;
    }
    T->size++;
    return 1;
}

I was expecting the values k and v in the function arguments would pass onto T->root->key, and T->root->value respectively, but it doesn't work..... Could someone help me to correct the code and explain to me the reason why my code is wrong please?

It is not the cause of your problem, but do not use `assert()` to check for ordinary failures. `assert()` is for programmatically expressing *invariants* that your program relies upon to hold true, such that if an assertion fails it indicates that your code is buggy. Their value is at least half documentary. Or from a practical perspsective, be aware that depending on compilation options, assertions may be completely removed from the compiled program. — John Bollinger, Mar 27 '21 at 12:49
Thanks for letting me know more about assert(). But I am pretty sure my main problem is in my insertNode() function... — Bobby Li, Mar 27 '21 at 12:59
Yes, as I said, the `assert()` issue is not the cause of your problem. — John Bollinger, Mar 27 '21 at 13:01
I thought assert() is used here to avoid cases like the heap memory has been used up due to memory leak? — Bobby Li, Mar 27 '21 at 13:30
No, that usage is incorrect because, as I said, assertions may not have any manifestation at all in the compiled program. Typically, release builds suppress them by defining the `NDEBUG` macro. The fact that this is even possible should be enough to tell you that you must not use `assert()` to perform any test that must be performed under all circumstances, such as testing the return values of library functions for error codes. — John Bollinger, Mar 27 '21 at 14:38
This answer: https://stackoverflow.com/a/1854338/2402272 also expresses the proper and improper uses of `assert()`. My initial comment expresses the same thing in different words. — John Bollinger, Mar 27 '21 at 14:43

John Bollinger · Accepted Answer · 2021-03-27T13:10:19.933

0

The main problem is that your InsertNode() function simply doesn't. It does construct an AVLTreeNode, traverse the tree to the new node's insertion point, and set its parent pointer, but it never updates a child pointer of the parent node, nor the root pointer of the tree in the case that it is initially empty. In particular, assigning to currentNode does not have this effect.

However, you could make this code work by adjusting it for currentNode to be a double pointer (AVLTreeNode **), so that you can assign indirectly through it to the wanted root or child pointer.

AVLTreeNode **currentNode = &T->root;

// ...

currentNode = &(*currentNode)->left;

// ...

// So that you can ultimately do this:
*currentNode = newAVLTreeNode(k, v);

edited Mar 27 '21 at 13:10

answered Mar 27 '21 at 12:57

John Bollinger

160,171
8
81
157

I thought the currentNode pointer is already pointed at the node for the insertion. I have tried to write currentNode->key = key; currentNode->value = value; in the last two lines. it still doesn't work.... – Bobby Li Mar 27 '21 at 13:10
2

No, @BobbyLi. If `P` and `Q` are both pointer variables, and `P` initially points to an object `o`, then assigning `Q = P` makes `Q` also point to `o`, but it does not make `Q` an *alias* of `P`. That is, subsequently assigning a different value to `Q` does not change `P`. This is entirely analogous to the case with any other type. Of course, however, if two pointers point to the same object, then changes to the pointed to object are visible via both pointers. – John Bollinger Mar 27 '21 at 13:16
For example, `int x = 3; int y = x; y = 2;` leaves `x` holding the value 3, not 2. Similarly, `int *p1 = &o1; int *p2 = p1; p2 = &o2;` leaves `p1` pointing to `o1`, not to `o2`. – John Bollinger Mar 27 '21 at 13:18
Your explanation is very clear. Thank you so much. – Bobby Li Mar 27 '21 at 13:20
1

Yes, @BobbyLi. Naturally, if you change the type of `currentNode` from `AVLTreeNode *` to `AVLTreeNode **` then you have to add an extra dereference everywhere you use it to access the `AVLTreeNode` underneath. The code presented in this answer provides examples, not an exhaustive list of changes. – John Bollinger Mar 28 '21 at 12:13

Pass argument value by pointer in function in c

1 Answers1