Yeah, I read the page, and it is a repeat of the book, which isn't super-hard to understand. I've checked my tree functions, and I don't see any of them leaving any dangling references, so I'm just stumped. It, however, must be a non-null pointer problem, because I got an idea, and did this: if I call myTree.display() immediately after the deleteRandom() call, where I did have a value in the tree, when I use depth-first traversal to cout << node->key on every node in the tree, in the supposedly-deleted node's spot is an address value ex: 468834, instead of a value 1-10000, which my rand() function is set up to produce ( I mean that before deleteRandom() is call, tree could be, for example, 8 16 32 14 21, and then after deleteRandom called, and 16 deleted, display() will produce 8 468834 32 14 21. What could that mean? Very interesting, whatever it is. Here's how I have it set up: in int main(), (code attached as .cpp file if it will make more sense that way)
Code:
else if(tolower(insOrDel) == 'd')
{
for(int u = 0; u < 100; u++)
{
myTree.deleteRandom();
myTree.display(); //I stuck this in to debug - see above
}
myTree.display();
cout << "There are " << myTree.countEls() << " elements in the tree" << endl;
myTree.getIPL();
}
deleteRandom() called from int main:
Code:
void BinSearchTree<T>::deleteRandom()
{
vector<int> myVector;
Stack<BinSearchNode<T>*> pushToVector;
BinSearchNode<T> *p = root;
if(p != 0)
{
pushToVector.push(p);
while(!pushToVector.empty())
{
p = pushToVector.pop();
myVector.push_back(p->key);
if(p->right != 0)
pushToVector.push(p->right);
if(p->left != 0)
pushToVector.push(p->left);
}
}
int elToDelete = rand()%myVector.size();
cout << myVector[(elToDelete-1)] << " deleted" << endl;
void BinSearchTree<T>::deleteRandom()
{
vector<int> myVector;
Stack<BinSearchNode<T>*> pushToVector;
BinSearchNode<T> *p = root;
if(p != 0)
{
pushToVector.push(p);
while(!pushToVector.empty())
{
p = pushToVector.pop();
myVector.push_back(p->key);
if(p->right != 0)
pushToVector.push(p->right);
if(p->left != 0)
pushToVector.push(p->left);
}
}
int elToDelete = rand()%myVector.size();
cout << myVector[(elToDelete-1)] << " deleted" << endl;
The problem also occurs when I choose a 100-count symmetrical delete (alternate deleting predecessors and successors) from int main() :
Code:
template<class T>
void BinSearchTree<T>::deleteRandomSymmetrically()
{
vector<int> myVector;
if(!myVector.empty())
{
myVector.clear();
}
Stack<BinSearchNode<T>*> pushToVector;
BinSearchNode<T> *p = root;
if(p != 0)
{
pushToVector.push(p);
while(!pushToVector.empty())
{
p = pushToVector.pop();
myVector.push_back(p->key);
if(p->right != 0)
pushToVector.push(p->right);
if(p->left != 0)
pushToVector.push(p->left);
}
}
int elToDelete = rand()%myVector.size();
int keySearch = myVector[(elToDelete-1)];
if(z == 1)
{
z++;
Queue<BinSearchNode<T>*> myQueue;
BinSearchNode<T> *q = root;
if(q != 0)
{
myQueue.enqueue(q);
while(!myQueue.empty())
{
q = myQueue.dequeue();
if(q->key == keySearch) //if q = rand generated el
{
if(q->right != 0)
{
BinSearchNode<T> *y = q->right;
BinSearchNode<T> *x = Min(y);
deleteByCopying(x);//was Min(q->Right)
display();
return;
}
else if(q->right = 0)
{
deleteByCopying(q);
}
}
}
}
}
else if(z ==2)
{
z--;
Queue<BinSearchNode<T>*> mySecondQueue;
BinSearchNode<T> *q = root;
if(q != 0)
{
mySecondQueue.enqueue(q);
while(!mySecondQueue.empty())
{
q = mySecondQueue.dequeue();
if(q->key == keySearch) //if q = rand generated el
{
if(q->left != 0)
{
deleteByCopying(Max(q->right));
display();
return;
}
else if(q->left = 0)
{
deleteByCopying(q);
}
}
}
}
}
}