Member Avatar for Nicco

Hi there, I'm working on a map for a class assignment and running into trouble. I've tried looking around the web but couldn't find anything that helped. I know how insertion works on a basic level when returning a node pointer but think i'm missing some key ideas when using a double pointer. Below i have the node struct declaration, the create node function, and my attempt at insert. Any help would be very very appreciated. Thanks so much for taking the time to look over this.

Given this:

NODE STRUCT:

struct Node {
  int    key;
  int    value;
  struct Node *left;
  struct Node *right;
  struct Node *parent;
};

and the create node function:

struct Node* create(int key, int value, struct Node* parent,int *perror) 
{
	struct Node* new = (struct Node*)malloc(sizeof(struct Node));
	if (!new) { *perror=E_NO_MEMORY; return 0; }
	new->key = key;
	new->value = value;
	new->left=0;
	new->right=0;
	new->parent=parent;
	*perror=0;
	return new;
}

And my attempt at inserting using recursion:

int insert_recursive(Node_handle* ppRoot, int key, int value) 
{
    Node_handle curr = *ppRoot;
    
    if (curr->parent == NULL)
    {
        int *perror;
        curr->parent = create(key, value, curr, perror);
        return *perror;
    }
    else
    {
        if (curr->key > key)
            return insert_recursive(&(curr->left), key, value);
        else
            return insert_recursive(&(curr->right), key, value);
    }
    
}

I've also tried passing curr->left/*right*/->parent into insert...God Help ME

  • 2 Contributors
  • 4 Replies
  • 2K Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Nicco

Dani AI

Generated

Nice catch, . For anyone who stumbles on this later: the trick with a double pointer is to pass the address of the child link you might replace (root, left, or right). When you finally hit a NULL link, you allocate and assign through that pointer. The parent pointer comes from the node you just descended from.

Here is a compact recursive insert that keeps parent correct and supports a simple duplicate-key policy (overwrite value). It returns 0 on success and sets *err if allocation fails.

int bst_insert(struct Node **link, struct Node *parent,
               int key, int value, int *err)
{
    if (*link == NULL) {
        *link = create(key, value, parent, err);
        return err ? *err : 0;
    }

    if (key < (*link)->key)
        return bst_insert(&(*link)->left, *link, key, value, err);
    if (key > (*link)->key)
        return bst_insert(&(*link)->right, *link, key, value, err);

    /* duplicate key: update value (or return an error if your spec says so) */
    (*link)->value = value;
    if (err) *err = 0;
    return 0;
}

/* usage */
int err = 0;
bst_insert(&root, NULL, key, value, &err);

Common gotchas this fixes (seen in the original attempt):

  • Check *link == NULL, not curr->parent == NULL. You insert when the child link you followed is empty.
  • Write to *link, not curr->parent. Assigning to parent creates the wrong relationship.
  • Do not use an uninitialized int *perror; pass the address of a real int.
  • Decide what to do with duplicates (update or reject) and implement it consistently.
  • Side note echoing : typedef-hiding pointer types tends to obscure what is being passed by address. Keeping struct Node ** visible makes the intent clearer.

Recommended Answers

All 4 Replies

Member Avatar for Nicco

Im sorry Node_handle is a typedef for node*...if there was confusion

Member Avatar for Nicco

Never mind I Figured it out!

Member Avatar for Narue

For the record, hiding a pointer behind a typedef is a fantastic way to confuse both yourself and others.

Member Avatar for Nicco

For the record, hiding a pointer behind a typedef is a fantastic way to confuse both yourself and others.

Yeah This is an assignment for school that was half implemented. So i have to use what i was given. I agree though!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.