Есть программа реализации АВЛ-дерева, но по какой-то причине не выполняется балансировка. Как исправить? Вот программа: #include
#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() //Инициализация
{
head = NULL;
}

void freeMemory() //Освобождение памяти
{
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) //Добавление элемента в порядке возрастания
{
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) //Удаление элемента перед каждым вхождением заданного
{
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) //Поиск заданного элемента по значению
{
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() //Печать
{
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) //Разность двух списков
{
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 != ‘Б’ || x.f2 / 1000 == 0 || x.f2 / 10000 != 0)
{
return;
}
else if (p == NULL) // слова нет в дереве; включить его
{
p = new Node;
h = 1;
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) // выросла левая ветвь
{
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) // выросла правая ветвь
{
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)
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 != ‘Б’ || x.f2 / 1000 == 0 || x.f2 / 10000 != 0)
{
cout << “Key is not in tree” << endl;
h = 0;
}
else if (x.f2 < p->key.f2)
{
delet(x, p->left, h);
if (h)
balance1(p, h);
}
else if (x.f2 > p->key.f2)
{
delet(x, p->right, h);
if (h)
balance2(p, h);
}
else
{
if (p->left == NULL && p->right == NULL)
{
delete p;
p = NULL;
h = 1;
}
else if (p->left != NULL && p->right == NULL)
{
Node* temp = p->left;
delete p;
p = temp;
h = 1;
}
else if (p->left == NULL && p->right != NULL)
{
Node* temp = p->right;
delete p;
p = temp;
h = 1;
}
else
{
p->list.freeMemory();
Node* temp = p->left;
Node* parent = p;
while (temp->right != NULL)
{
parent = temp;
temp = temp->right;
}
if (parent != p)
parent->right = temp->left;
else
parent->left = temp->left;
p->key = temp->key;
p->list = temp->list;
delete temp;
h = 1;
}
}
}

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