Есть программа для работы с АВЛ-деревом. Всё работает корректно, кроме удаления корневого элемента. Почему? Вот программа: #include <iostream>
#include<fstream>
#include<string>
#include<cmath>
using namespace std;

class ListNode //элемент списка
{
public:
    int data;
    ListNode* prev, * next;
public:
    ListNode(int data)
    {
        this->data = data;
        this->prev = this->next = NULL;
    }
};
class LinkedList //список
{
public:
    ListNode* head;

public:
    LinkedList() //1.Инициализация
    {
        head = NULL;
    }

    void freeMemory() //2.Освобождение памяти 
    {
        if (head == NULL)
            return;

        ListNode* current = head;

        ListNode* nextNode;

        do
        {
            nextNode = current->next;
            delete current;
            current = nextNode;
        } while (current != head);
        head = NULL;
    }

    void addSorted(int data) //3.Добавление элемента в порядке возрастания
    {
        ListNode* newNode = new ListNode(data);

        if (head == NULL) //если список пустой
        {
            head = newNode;
            newNode->next = newNode->prev = newNode;
        }
        else if (data < head->data) //если новый элемент меньше головы списка
        {

            newNode->next = head;
            newNode->prev = head->prev;
            head->prev->next = newNode;
            head->prev = newNode;
            head = newNode;
        }
        else if (data > head->prev->data) //если новый элемент больше хвоста списка
        {
            newNode->next = head;
            newNode->prev = head->prev;
            head->prev->next = newNode;
            head->prev = newNode;
            head->prev = newNode;
        }
        else //если новый элемент располагается где-то в середине списка
        {
            ListNode* current = head->next;

            while (current != head && current->data < data) //поиск элемента, значение которого больше нового
            {
                current = current->next;
            }

            newNode->next = current;
            newNode->prev = current->prev;
            current->prev->next = newNode;
            current->prev = newNode;
        }
    }

    void removeBefore(int data) //4.Удаление элемента перед каждым вхождением заданного
    {
        if (head == NULL)
        {
            return;
        }


        if (head->data == data)
        {
            ListNode* nodeToRemove = head->prev;
            nodeToRemove->prev->next = head;
            head->prev = nodeToRemove->prev;
            delete nodeToRemove;
        }

        ListNode* current = head->next;

        while (current != head)
        {
            if (current->data == data)
            {
                ListNode* nodeToRemove = current->prev;
                nodeToRemove->prev->next = current;
                current->prev = nodeToRemove->prev;
                delete nodeToRemove;
            }

            current = current->next;
        }
    }

    bool search(int data) //5.Поиск заданного элемента по значению
    {
        if (head == NULL)
            return false;

        ListNode* current = head;

        do
        {
            if (current->data == data)
                return true;

            current = current->next;
        } while (current != head);

        return false;
    }

    void print() //6.Печать
    {
        if (head == NULL)
            return;

        ListNode* current = head;

        do
        {
            cout << current->data << ' ';
            current = current->next;
        } while (current != head);

        cout << endl;
    }

    LinkedList difference(LinkedList list1, LinkedList list2) //7.Дополнительная операция – разность двух списков
    {
        if (head != NULL)
        {
            LinkedList result;

            ListNode* current = list1.head;

            do
            {
                if (list2.search(current->data) == false)
                    result.addSorted(current->data);
                current = current->next;
            } while (current != list1.head);
            return result;
        }
    }
};

struct Key
{
    char f1;
    int f2;
};

struct Node
{
    Key key;
    LinkedList list;
    Node* left;
    Node* right;
    int balance;
};

void add(Key x, Node*& p, int linenumber, short h) // поиск и добавление элемента
{
    if (x.f1 != 'Б')
    {
        return;
    }
    else if (p == NULL) // слова нет в дереве; включить его
    {
        p = new Node;
        p->key = x;
        p->list.addSorted(linenumber);
        p->balance = 0;
        p->left = NULL;
        p->right = NULL;
    }
    else if (x.f2 < p->key.f2)
    {
        add(x, p->left, linenumber, h);
        if (h != 0) // выросла левая ветвь
        {
            switch (p->balance)
            {
            case 1:
                p->balance = 0;
                h = 0;
                break;
            case 0:
                p->balance = -1;
                break;
            case -1: // балансировка
                Node * p1 = p->left;
                if (p1->balance == -1) // L-поворот
                {
                    p->left = p1->right;
                    p1->right = p;
                    p->balance = 0;
                    p = p1;
                }
                else // LR-поворот
                {
                    Node* p2 = p1->right;
                    p1->right = p2->left;
                    p2->left = p1;
                    p->left = p2->right;
                    p2->right = p;
                    if (p2->balance == -1)
                        p->balance = 1;
                    else
                        p->balance = 0;
                    if (p2->balance == 1)
                        p1->balance = -1;
                    else
                        p1->balance = 0;
                    p = p2;
                }
                p->balance = 0;
                h = 0;
                break;
            }
        }
    }
    else if (x.f2 > p->key.f2)
    {
        add(x, p->right, linenumber, h);
        if (h != 0) // выросла правая ветвь
        {
            switch (p->balance)
            {
            case -1:
                p->balance = 0;
                h = 0;
                break;
            case 0:
                p->balance = 1;
                break;
            case 1: // балансировка
                Node * p1 = p->right;
                if (p1->balance == 1) //R-поворот
                {
                    p->right = p1->left;
                    p1->left = p;
                    p->balance = 0;
                    p = p1;
                }
                else // RL-поворот
                {
                    Node* p2 = p1->left;
                    p1->left = p2->right;
                    p2->right = p1;
                    p->right = p2->left;
                    p2->left = p;
                    if (p2->balance == 1)
                        p->balance = -1;
                    else
                        p->balance = 0;
                    if (p2->balance == -1)
                        p1->balance = 1;
                    else
                        p1->balance = 0;
                    p = p2;
                }
                p->balance = 0;
                h = 0;
                break;
            }
        }
    }
    else
    {
    p->list.addSorted(linenumber);
    h = 0;
    }
}

void balance1(Node* p, short h)
{
    Node* p1, * p2;
    short b1, b2;
    switch (p->balance)
    {
    case -1:
        p->balance = 0;
        break;
    case 0:
        p->balance = 1;
        h = 0;
        break;
    case 1: // балансировка
        p1 = p->right;
        b1 = p1->balance;
        if (b1 >= 0) // R-поворот
        {
            p->right = p1->left;
            p1->left = p;
            if (b1 == 0)
            {
                p->balance = 1;
                p1->balance = -1;
                h = 0;
            }
            else
            {
                p->balance = 0;
                p1->balance = 0;
            }
            p = p1;
        }
        else // RL-поворот
        {
            p2 = p1->left;
            b2 = p2->balance;
            p1->left = p2->right;
            p2->right = p1;
            p->right = p2->left;
            p2->left = p;
            if (b2 == 1)
                p->balance = -1;
            else
                p->balance = 0;
            if (b2 == -1)
                p1->balance = 1;
            else
                p1->balance = 0;
            p = p2;
            p2->balance = 0;
        }
    }
}
void balance2(Node* p, short h)
{
    Node* p1, * p2;
    short b1, b2;
    switch (p->balance)
    {
    case 1:
        p->balance = 0;
        break;
    case 0:
        p->balance = 0;
        h = 0;
        break;
    case -1:
        p1 = p->left;
        b1 = p1->balance;
        if (b1 <= 0) // L-поворот
        {
            p->left = p1->right;
            p1->right = p;
            if (b1 == 0)
            {
                p->balance = -1;
                p1->balance = 1;
                h = 0;
            }
            else
            {
                p->balance = 0;
                p1->balance = 0;
            }
            p = p1;
        }
        else // LR-поворот
        {
            p2 = p1->right;
            b2 = p2->balance;
            p1->right = p2->left;
            p2->left = p1;
            p->left = p2->right;
            p2->right = p;
            if (b2 == -1)
                p->balance = 1;
            else
                p->balance = 0;
            if (b2 == 1)
                p1->balance = -1;
            else
                p1->balance = 0;
            p = p2;
            p2->balance = 0;
        }
    }
}
Node* del(Node* r, Node* q, short h)
{
    if (r->right != NULL)
    {
        r->right = del(r->right, q, h);
        if (h != 0)
            balance2(r, h);
        return r;
    }
    else
    {
        q->key = r->key;
        Node* left = r->left;
        delete r;
        h = 1;
        return left;
    }
}
void delet(Key x, Node*& p, short h) // удаление элемента, выше вспомогательные подпрограммы
{
    Node* q;
    if (p == NULL || x.f1 != 'Б')
    {
        cout << "Key is not in tree" << endl;
        h = 0;
    }
    else if (x.f2 < p->key.f2)
    {
        delet(x, p->left, h);
        if (h != 0)
            balance1(p, h);
    }
    else if (x.f2 > p->key.f2)
    {
        delet(x, p->right, h);
        if (h != 0)
            balance2(p, h);
    }
    else
    {
        q = p;
        if (q->right == NULL)
        {
            p = q->left;
            delete q;
            h = 1;
        }
        else if (q->left == NULL)
        {
            p = q->right;
            delete q;
            h = 1;
        }
        else
        {
            del(q->left, q, h);
            if (h != 0)
                balance1(p, h);
        }
    }
}

void search(Key x, Node*& p, short h) // поиск элемента
{
    Node* q;
    if (p == NULL || x.f1 != 'Б')
    {
        cout << "В дереве нет такого элемента" << endl;
        h = 0;
    }
    else if (x.f2 < p->key.f2)
    {
        search(x, p->left, h);
    }
    else if (x.f2 > p->key.f2)
    {
        search(x, p->right, h);
    }
    else
    {
        cout << "Элемент содержится в строке(ах) входного файла ";
        p->list.print();
    }
}

ofstream out("outdata.txt");
void walktree(Node* t, short h) // обход дерева справа налево и вывод в файл
{

    if (t != NULL)
    {
        walktree(t->right, h + 1);
        out << t->key.f1 << t->key.f2 << endl;
        walktree(t->left, h + 1);
    }
}

void printtree(Node* t, short h) // обход дерева справа налево и вывод в файл
{
    if (t != NULL)
    {
        printtree(t->left, h + 1);
        for (int i = 1; i <= h; i++)
            cout << "   ";
        cout << t->key.f1 << t->key.f2 << endl;
        printtree(t->right, h + 1);
    }
}

void deletetree(Node* t, short h) // печать дерева
{

    if (t != NULL)
    {
        deletetree(t->right, h + 1);
        delete t;
        deletetree(t->left, h + 1);
    }
}

ifstream in("data.txt");
void initialize(Node*& p)
{
    Key key;

    string line;

    int linenumber = 0;
    if (in.is_open())
    {
        while (getline(in, line))
        {
            ++linenumber;
            key.f1 = line[0];
            key.f2 = 0;
            for (int i = 1; i < 5; i++)
            {
                key.f2 += (line[i] - '0') * pow(10, 4 - i);
            }
            add(key, p, linenumber, 0);
        }
    }
}

int main()
{
    setlocale(LC_ALL, "rus");

    Node* root = NULL;

    initialize(root);


    walktree(root, 0);

    delet({ 'Б', 9122 }, root, 0);
    printtree(root, 0);

    in.close();
    out.close();
    return 0;
}