Binary Search Tree link to parent

[dannielum]

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...

 

[Chinchilla]

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

 

[John Carson]

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.