BST code is not working with large number

问题:

I have a very frustrated situation with my BST code:

vector<int> order;
BinarySearchTree tree;
for (int i=0; i<1000; ++i) {
  int j = rand()%1000;
  order.push_back(j);
}
for (int i = 0; i < 1000; ++i) {
  tree.insert(order[i]);
}
while(!tree.isEmpty()) {
  cout << tree.min() << endl;
  tree.remove(tree.min());
}

the code is working perfectly fine with small number of i, say 10, or 100. However, it is stop working when i is 1000.

the insert function is as follows

void BinarySearchTree::insert(int d)
{
  tree_node* t = new tree_node;
  tree_node* parent;
  t->data = d;
  t->left = NULL;
  t->right = NULL;
  parent = NULL;

  // is this a new tree?
  if(isEmpty()) root = t;
  else
  {
    //Note: ALL insertions are as leaf nodes
    tree_node* curr;
    curr = root;
    // Find the Node's parent
    while(curr)
    {
      parent = curr;
      if(t->data > curr->data) curr = curr->right;
      else curr = curr->left;
    }

    if(t->data <= parent->data)
      parent->left = t;
    else
      parent->right = t;
  }
}

In response to the comments, i am going to post all the code. :)

void BinarySearchTree::remove(int d)
{
  //Locate the element
  bool found = false;
  if(isEmpty())
  {
    cout<<" This Tree is empty! "<<endl;
    return;
  }

  tree_node* curr;
  tree_node* parent;
  curr = root;
  //parent = root;

  while(curr != NULL)
  {
    if(curr->data == d)
    {
      found = true;
      break;
    }
    else
    {
      parent = curr;
      if(d>curr->data) curr = curr->right;
      else curr = curr->left;
    }
  }
  if(!found)
  {
    cout<<" Data not found! "<<endl;
    return;
  }


  // 3 cases :
  // 1. We're removing a leaf node
  // 2. We're removing a node with a single child
  // 3. we're removing a node with 2 children

  // Node with single child
  if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
    && curr->right == NULL))
  {
    if(curr->left == NULL && curr->right != NULL)
    {
      if (curr == root) {
        root = curr->right;
        delete curr;
      }
      else {
        if(parent->left == curr)
        {
          parent->left = curr->right;
          delete curr;
        }
        else
        {
          parent->right = curr->right;
          delete curr;
        }
      }
    }
    else // left child present, no right child
    {
      if (curr==root) {
        root = curr->left;
        delete curr;
      }
      else {
        if(parent->left == curr)
        {
          parent->left = curr->left;
          delete curr;
        }
        else
        {
          parent->right = curr->left;
          delete curr;
        }
      }
    }
    return;
  }

  //We're looking at a leaf node
  if( curr->left == NULL && curr->right == NULL)
  {
    if (curr == root) {
      root = NULL;
      delete curr;
      return;
    }
    else {
      if(parent->left == curr) parent->left = NULL;
      else parent->right = NULL;
      delete curr;
      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;
      delete 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;
        delete lcurr;
        lcurrp->left = NULL;
      }
      else
      {
        tree_node* tmp;
        tmp = curr->right;
        curr->data = tmp->data;
        curr->right = tmp->right;
        delete tmp;
      }

    }
    return;
  }

}

and the min() function

int BinarySearchTree::min()
{
  tree_node *p=root;
  while (p->left != NULL)
    p=p->left;
  return (p->data);
}

回答1:

Looks like the last four lines have negated logic of the for loop. The for loop says: new val is larger go right else left. The tree placement says: new val is larger place left else place right.

Also I don't see your remove code, but the it may be affected by the wrong ordering.

Also try initializing rand before using it:

srand (time(NULL));

回答2:

You need to improve on your random function. Try using int j = rand() instead.

EDIT: you have duplicate minimum values. With the code below you remove the top most node with minimum value.

while(curr != NULL)
  {
    if(curr->data == d)
    {
      found = true;
      break;
    }
    else
    {
      parent = curr;
      if(d>curr->data) curr = curr->right;
      else curr = curr->left;
    }
  }

try the following code instead.

 tree_node* left_most_duplicate;

while (curr != NULL)
{
    if (d>curr->data) curr = curr->right;
    else curr = curr->left;
    if (curr->data == d)
    {
        parent = curr;
        left_most_duplicate = curr;
        found = true;
        break;
    }
}
curr = left_most_duplicate;