Binary Search Tree link to parent

Discussion in 'C++' started by dannielum@gmail.com, Oct 31, 2005.

  1. Guest

    Hi all,
    I am trying to write a Binary Search Tree that each of its node will
    have 3 node pointers: left, right and parent. I need a parent pointer
    for some the purpose of my project. Without the pointer to the parent
    node, the program will be inefficient and slow. It works fine at first.
    However, when I started to build the remove function, it destroys the
    tree when I delete a node. I already changed the parent pointer
    whenever I delete a node, but still doesnt work correctly. This is the
    tree node class:

    /////////////////////////////////////////////////////////////
    template <class Comparable>
    class BinaryNode
    { //Binary Tree Node
    Comparable element; //element
    int frequency; //frequency
    int height; //height

    BinaryNode * left; //left child
    BinaryNode * right; //right child
    BinaryNode * parent; //parent

    /* more functions here */

    friend class BinarySearchTree<Comparable>;
    };

    //////////////////////////////////////////////////////////////

    This is part of the remove function:

    //////////////////////////////////////////////////////////////

    /* more codes here */

    BinaryNode<Comparable> *oldNode = t;

    if (NULL != t->left)
    { //the node has a left subtree
    t->left->parent = t->parent;
    t = t->left;
    }
    else if (NULL != t->right)
    { //the node has a right subtree
    t->right->parent = t->parent;
    t = t->right;
    }
    else
    { //no children
    }

    delete oldNode;

    /* more codes here */
    //////////////////////////////////////////////////////////////

    Can someone tell me how can I solve the problem of deletion? Or is it
    possible? Thanks in advance...
     
    , Oct 31, 2005
    #1
    1. Advertising

  2. Chinchilla Guest

    I can't really tell you what's wrong without knowing more information,
    for starters, what does 't' refer to?

    if 't' is the very top of the tree than your remove function wouldn't
    work because the top doesn't have a "parent".


    if (NULL != t->left)
    { //the node has a left subtree
    t->left->parent = t->parent;
    t = t->left;
    }
    You're connecting the child nodes to t's parent, but not t's parent to
    the child nodes.

    Also, it's more aesthetically pleasing if the data you're comparing is
    on the left side to the data being compared.
    i.e.
    (t->left != NULL) instead of (NULL != t->left)

    -Chinchilla
     
    Chinchilla, Oct 31, 2005
    #2
    1. Advertising

  3. John Carson Guest

    <> wrote in message
    news:
    > Hi all,
    > I am trying to write a Binary Search Tree that each of its node will
    > have 3 node pointers: left, right and parent. I need a parent pointer
    > for some the purpose of my project. Without the pointer to the parent
    > node, the program will be inefficient and slow. It works fine at
    > first. However, when I started to build the remove function, it
    > destroys the tree when I delete a node. I already changed the parent
    > pointer whenever I delete a node, but still doesnt work correctly.
    > This is the tree node class:
    >
    > /////////////////////////////////////////////////////////////
    > template <class Comparable>
    > class BinaryNode
    > { //Binary Tree Node
    > Comparable element; //element
    > int frequency; //frequency
    > int height; //height
    >
    > BinaryNode * left; //left child
    > BinaryNode * right; //right child
    > BinaryNode * parent; //parent
    >
    > /* more functions here */
    >
    > friend class BinarySearchTree<Comparable>;
    > };
    >
    > //////////////////////////////////////////////////////////////
    >
    > This is part of the remove function:
    >
    > //////////////////////////////////////////////////////////////
    >
    > /* more codes here */
    >
    > BinaryNode<Comparable> *oldNode = t;
    >
    > if (NULL != t->left)
    > { //the node has a left subtree
    > t->left->parent = t->parent;
    > t = t->left;
    > }
    > else if (NULL != t->right)
    > { //the node has a right subtree
    > t->right->parent = t->parent;
    > t = t->right;
    > }


    Your code is too incomplete for me to really know what is going on. I am
    guessing that t is a pointer stored in the parent of the node to be deleted
    that points to the node that is to be deleted. I will refer to the parent of
    the node to be deleted as the grandparent.

    What if both t->left and t->right are non-zero? Because of the "else if"
    form, you only hook up the left node to the grandparent and lose the right
    node. Of course, hooking up both is going to be a problem if the grandparent
    started out with two children, because you would be deleting one and adding
    two, giving the grandparent three children.

    > else
    > { //no children
    > }
    >
    > delete oldNode;
    >
    > /* more codes here */
    > //////////////////////////////////////////////////////////////
    >
    > Can someone tell me how can I solve the problem of deletion? Or is it
    > possible? Thanks in advance...



    --
    John Carson
     
    John Carson, Oct 31, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,182
  2. Replies:
    1
    Views:
    355
    red floyd
    Jan 1, 2007
  3. sharan
    Replies:
    4
    Views:
    702
    CBFalconer
    Oct 30, 2007
  4. sharan
    Replies:
    2
    Views:
    849
    SM Ryan
    Oct 31, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,140
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page