Re: Binary search trees

On Oct 30, 9:30 am, j_depp...@xxxxxxxxx wrote:
I would like to know what would be the best way to count the nodes
accessed while searching for an item in a binary search tree. I have
to keep a tally for each item I search for. I have included my search
method from my program using C++
<code/>
void BinarySearchTree::find(int d)
{
//Locate the element
bool found = false;

size_t nodes_visited = 0;
// From here forward, every time you do an if(nodecheck) or else()
increment nodes_visited.

if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
tree_node* curr;
tree_node* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == d)
{
found = true;
cout << " Item " << d << " found" << endl;

break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout << " " << d <<" Data not found! "<<endl;
return;
}
if((curr->left == NULL && curr->right != NULL)|| (curr->left !=
NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
parent->left = curr->right;
else
parent->right = curr->right;
}
else // left child present, no right child
{
if(parent->left == curr)
parent->left = curr->left;
else
parent->right = curr->left;

}
return;
}

//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr)
parent->left = NULL;
else parent->right = NULL;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element

if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
}

}
return;
}

</code>

Thank you. I hope my question was clear enough.


.

Relevant Pages

  • Binary search trees
    ... tree_node* curr; ... else // left child present, ... tree_node* lcurr; ... tree_node* lcurrp; ...
    (comp.programming)
  • Re: [BUG]: Crash with CONFIG_FAIR_CGROUP_SCHED=y
    ... assumes that parent and child will be part of the same group (which ... Yeah ..I feel safe with an explicit!curr check, ... Please read the FAQ at http://www.tux.org/lkml/ ...
    (Linux-Kernel)