c++ - 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)时工作得很好。但是，当 i 为 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));