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

} 

и функции мин()

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

Answer 1

Вы должны улучшить вашу случайную функцию. Вместо этого попробуйте использовать int j = rand().

EDIT: у вас есть повторяющиеся минимальные значения. С помощью приведенного ниже кода вы удаляете самый верхний узел с минимальным значением.

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; 

Answer 2

Похоже, что последние четыре строки отрицают логику цикла for. Цикл for говорит: новый val больше вправо влево. Размещение на дереве говорит: новый val больше места остальное место место.

Также я не вижу ваш код удаления, но на него может повлиять неправильный порядок.

попробовать также инициализирует ранды перед использованием:

srand (time(NULL));