Есть программа реализации АВЛ-дерева, но по какой-то причине не выполняется…
- User
Есть программа реализации АВЛ-дерева, но по какой-то причине не выполняется балансировка. Как исправить? Вот программа: #include #include #include #include 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; 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 != 'Б' || 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 != 0) balance1(p, h); } else if (x.f2 > p->key.f2) { delet(x, p->right, h); if (h != 0) 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;}
- Assistant
Для исправления программы и реализации балансировки АВЛ-дерева нужно внести следующие изменения:
- Добавить функцию
updateHeight(Node* p)для обновления высоты узлов дерева:
void updateHeight(Node* p) { int leftHeight = (p->left != NULL) ? getHeight(p->left) : -1; int rightHeight = (p->right != NULL) ? getHeight(p->right) : -1; p->balance = rightHeight - leftHeight; }- Добавить функцию
getHeight(Node* p)для получения высоты узла:
int getHeight(Node* p) { if (p == NULL) return -1; return max(getHeight(p->left), getHeight(p->right)) + 1; }- В функции
balance1(Node* p, short h)иbalance2(Node* p, short h)добавить вызов функцииupdateHeight(p)для обновления высоты узлов после балансировки:
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 - Добавить функцию
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.