BST代码不适用于大量

Question

我对我的BST代码感到非常沮丧：

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());
}

该代码可以很好地处理少量的i，比如10或100。然而，当我1000岁的时候，它就停止工作了。

插入函数如下

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;
  }
}

作为对评论的回应，我将发布所有代码。：）

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;
  }
}

和min（）函数

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

Answer 1

看起来最后四行否定了for循环的逻辑。for循环表示：新val较大，向右或向左。树的位置显示：新val是左边较大的地方，其他地方是右边。

此外，我没有看到您的删除代码，但它可能会受到错误排序的影响。

在使用rand之前也尝试初始化它：

srand (time(NULL));

Answer 2

您需要改进您的随机函数。请尝试使用int j=rand（）。

编辑：您有重复的最小值。使用下面的代码，可以删除具有最小值的最顶部节点。

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

请尝试以下代码。

 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;