AVL-tree node misses content of an included structure and I cannot find why

Question

Consider the following AVL-tree implementation. Each node contains a list of numbers.The key is named workload, but consider it as a plain double variable. If a key is equal to the key of an already existing node, the number gets pushed into the list. Every time I pop a number from a list, I perform a check, if the node's list is empty -> remove the node. But, after the element with key=3 gets removed completely, the list of the node with key=4 is suddenly empty. I've been trying to solve it for over 10 hours now, it's actually the first time I ever needed to ask something here. Pardon me if I miss a few things.

#include<iostream> 
#include <list>
using namespace std;

class BST
{
    struct node
    {
        double workload;
        list<int> numbers;
        node* left;
        node* right;
        int height;
    };

    node* root;
    unsigned long long size;
    bool empty;

    void makeEmpty(node* t)
    {
        if(t == NULL)
            return;
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }

    node* insert(double workload,int number, node* t)
    {

        if(t == NULL)
        {
            t = new node;
            t->workload = workload;
            t->numbers.push_back(number);
            t->height = 0;
            t->left = t->right = NULL;
        }
        else if(t->workload == workload){
            t->numbers.push_back(number);
        }
        else if(workload < t->workload)
        {
            t->left = insert(workload, number, t->left);
            if(height(t->left) - height(t->right) == 2)
            {
                if(workload < t->left->workload)
                    t = singleRightRotate(t);
                else
                    t = doubleRightRotate(t);
            }
        }
        else if(workload > t->workload)
        {
            t->right = insert(workload, number, t->right);
            if(height(t->right) - height(t->left) == 2)
            {
                if(workload > t->right->workload)
                    t = singleLeftRotate(t);
                else
                    t = doubleLeftRotate(t);
            }
        }

        //if x == t->workload instead of using int workload. its a list and we push into it.
        t->height = max(height(t->left), height(t->right))+1;
        return t;
    }

    node* singleRightRotate(node* &t)
    {
        node* u = t->left;
        t->left = u->right;
        u->right = t;
        t->height = max(height(t->left), height(t->right))+1;
        u->height = max(height(u->left), t->height)+1;
        return u;
    }

    node* singleLeftRotate(node* &t)
    {
        node* u = t->right;
        t->right = u->left;
        u->left = t;
        t->height = max(height(t->left), height(t->right))+1;
        u->height = max(height(t->right), t->height)+1 ;
        return u;
    }

    node* doubleLeftRotate(node* &t)
    {
        t->right = singleRightRotate(t->right);
        return singleLeftRotate(t);
    }

    node* doubleRightRotate(node* &t)
    {
        t->left = singleLeftRotate(t->left);
        return singleRightRotate(t);
    }

    node* findMin(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }

    node* findMax(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    node* find(node* t,double workload){
        if (t->workload == workload){
            return t;
        }
        else if(workload < t->workload && t->left!=NULL)
            return find(t->left,workload);
        else if(workload > t->workload && t->right!=NULL)
            return find(t->right,workload);
        else{
            cout << "Null node encountered" << endl;
            return t;
        }
    }
    node* remove(double x, node* t)
    {
        node* temp;

        // Element not found
        if(t == NULL)
            return NULL;

        // Searching for element
        if(x < t->workload)
            t->left = remove(x, t->left);
        else if(x > t->workload)
            t->right = remove(x, t->right);

        // Element found
        // With 2 children
        else if(t->left && t->right)
        {
            temp = findMin(t->right);
            t->workload = temp->workload;
            t->right = remove(t->workload, t->right);
        }
        // With one or zero child
        else
        {
            temp = t;
            if(t->left == NULL)
                t = t->right;
            else if(t->right == NULL)
                t = t->left;
            delete temp;
        }
        if(t == NULL)
            return t;

        t->height = max(height(t->left), height(t->right))+1;

        // If node is unbalanced
        // If left node is deleted, right case
        if(height(t->left) - height(t->right) == -2)
        {
            // right right case
            if(height(t->right->right) - height(t->right->left) == 1)
                return singleLeftRotate(t);
            // right left case
            else
                return doubleLeftRotate(t);
        }
        // If right node is deleted, left case
        else if(height(t->right) - height(t->left) == 2)
        {
            // left left case
            if(height(t->left->left) - height(t->left->right) == 1){
                return singleRightRotate(t);
            }
            // left right case
            else
                return doubleRightRotate(t);
        }
        return t;
}



    int height(node* t)
    {
        return (t == NULL ? -1 : t->height);
    }

    int getBalance(node* t)
    {
        if(t == NULL)
            return 0;
        else
            return height(t->left) - height(t->right);
    }

    void inorder(node* t)
    {
        if(t == NULL)
            return;
        inorder(t->left);
        cout << t->workload<< " ";
        inorder(t->right);
    }

    //Reverse inorder (Sorted highest to lowest)
    void rinorder(node* t)
    {
        if(t == NULL)
            return;
        rinorder(t->right);
        cout << t->workload << " ";
        rinorder(t->left);
    }

    void preorder(node* t) 
    { 
        if (t == NULL) 
            return; 
        cout << t->workload << " "; 
        preorder(t->left);  
        preorder(t->right); 
    } 

    void postorder(node* t) 
    { 
        if (t == NULL) 
            return; 
        postorder(t->left);  
        postorder(t->right);
        cout << t->workload << " ";
    } 


public:
    BST()
    {
        root = NULL;
    }

    void insert(double workload, int number)
    {
        root = insert(workload, number, root);
    }

    void remove(double workload)
    {
        root = remove(workload, root);
    }

    void displayrin()
    {   
        cout << "Rinorder: ";
        rinorder(root);
        cout << endl;
    }

    void displayin()
    {   
        cout << "Inorder: ";
        inorder(root);
        cout << endl;
    }
        void displaypost()
    {
        cout << "Postorder: ";
        postorder(root);
        cout << endl;
    }
        void displaypre()
    {
        cout << "Preorder: ";
        preorder(root);
        cout << endl;
    }
    double getMax(){
        return findMax(root)->workload;
    }

    int getMaxNum(){
        return find(root,getMax())->numbers.front();
    }

    int getNum(double workload){
        return find(root,workload)->numbers.front();
    }

    //We pop a Num from a node
    void popnumber(double workload){
        node *t = find(root,workload);
            if(t!=NULL){
                if(!t->numbers.empty()){
                    t->numbers.pop_front();
                    //If the Num list of the node is empty, remove node
                    if(t->numbers.empty()){
                        remove(t->workload);
                    }
                }
            }

    }
};

int main()
{
    BST t;
    //key value pairs
    t.insert(2,1);
    t.insert(3,1);
    t.insert(3,2);
    t.insert(4,7);
    cout << t.getNum(4) << endl;
    cout << t.getNum(3)<<endl;
    t.popnumber(3);
    cout << t.getNum(3)<<endl;
    t.popnumber(3);
    t.displayin();
    t.displaypost();
    t.displaypre();
    t.displayrin();
    cout << t.getNum(4) << endl;
    cout << "The max is : " << t.getMax() << endl;
    cout << "The top Num of the Max is : " << t.getMaxNum() << endl;

    return 0;
}

Answer 1

As mentioned in the comments, the problem is in the "Element found With 2 children" section of remove.

To remove the element, you find the next element in the tree. Your implementation then wants to copy the contents of the found node (temp). You copy the workload value, so that both t and temp have the same workload value (4). You do not copy the numbers list. The t node has a workload of 4 and an empty numbers list, while temp has a workload of 4 and a numbers list consisting of one element, 7. You then delete temp, losing the list.

One fix would be to copy (or move) numbers from temp to t before removing it from the tree. Adding a MoveData method to node that would move the data fields (while not altering the tree specific fields) would make it easier to add new data fields.

Another fix would be to change how you're doing the data update. If you update all pointers (and other tree related fields like height), then you don't have to worry about the data (and any pointers/iterators to the nodes would not be invalidated).