Change pointer to pointer to reference to pointer

Question

I have a method to insert a node into a binary tree, which uses a pointer to pointer to correctly allocate new nodes in the tree.

As I'm using C++, I think that it's possible to change this pointer to pointer to a reference to pointer, leading to cleaner and C++-ish code. But how to do this and keep the allocation correct?

bool insert(T value) {
    node** buff = &root;

    while ((*buff) != NULL) {
        if (value == (*buff)->value) {
            return false;
        } else if (value < (*buff)->value) {
            buff = &(*buff)->left;
        } else {
            buff = &(*buff)->right;
        }
    }

    *buff = new node(value);
    return true;
}

I don’t see why you need double pointer here. Just drop one indirection. — bolov
– bolov, Commented Jul 9, 2014 at 20:55
I don't know as well, but when I use a single pointer, seems that my allocation is done in an undefined location, like my root always point to NULL, no matter inserting elements in the tree. — aajjbb
– aajjbb, Commented Jul 9, 2014 at 21:02

bolov · Accepted Answer · 2014-07-09 21:28:46Z

not tested, but this is the idea: you insert when you are in parent, not when you descended into null:

bool insert(T value) {
    if (root == nullptr) {
       root = new node(value);
       return true;
    }

    node* buff = root;    
    while(buff->value != value) {        
        if (value < buff->value) {
            if(buff->left == nullptr {
               buff->left = new node(value);
               return true;
            }
            buff = buff->left;
        } else {
            if (buff->right == nullptr) {
               buff->right = new node(value);
               return true;
            }
            buff = buff->right;
        }
    }

    return false;
}

how i would write it:

// returns the node under which the insertion must be done
// or nullptr if the value already exists in the tree
// prereq: tree must be not empty
node* findParentInsertionPoint(T value) {
    if (root == nullptr) {
       throw std::logic_erro("");
    }

    node* n = root;    
    while(n->value != value) {        
        if (value < n->value) {
            if(n->left == nullptr {
               return buff;
            }
            n= n->left;
        } else {
            if (n->right == nullptr) {
               return n;
            }
            n= n->right;
        }
    }
    return nullptr;
}

// inserts a leaf as child of parent
// prereq: parent must be not null
// the corresponding child must be null;
void insertLeafAt(T value, node * parent) {
   if (parent == nullptr) {
      throw std::logic_error("");
   }
   if (value < parent->value) {
      parent->left = new node(value);
   } else {
     parent->right = new node(value);
   }
}

bool insert(T value) {
    if (root == nullptr) {
       root = new node(value);
       return true;
    }

    node* parent = findParentInsertionPoint(value);
    if (parent == nulptr) {
       return false;
    }
    insertLeafAt(T value, parent);
    return true;
}

Jarod42 · Accepted Answer · 2014-07-09 20:21:02Z

0

You cannot reassign a reference, so due to buff = &(*buff)->left;,
you can't change node** buff = &root; to node*& buff = root; (and replacing (*buff) by buff).

answered Jul 9, 2014 at 20:21

Jarod42

228k15 gold badges214 silver badges351 bronze badges

1 Comment

Jarod42 Over a year ago

I would use smart pointer (for free memory management) like std::unique_ptr<node> instead of node*, and so node** buff will become std::unique_ptr<node>* buff. But if you keep pointer for root, then yes.

Collectives™ on Stack Overflow

Change pointer to pointer to reference to pointer

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related