Такая проблема: при удалении корневого элемента с обоими поддеревьями не выполняется…
- User
Такая проблема: при удалении корневого элемента с обоими поддеревьями не выполняется балансировка. Исправь метод delet так, чтобы в этом случае выполнялась балансировка: class Tree { private: int hashTableSize = 10; std::vector readFromFile(const std::string& filename) { std::vector sorts; std::ifstream file(filename);
if (file.is_open()) { long long int vc; std::string pn; long long int t; int day; int month; int year; char divider = ‘|’;
while (file >> vc >> divider >> pn >> divider >> t >> divider >> day >> month >> year) { VendorCode vendorcode(vc); ProdName productname(pn); TIN tin(t); Date date(day, month, year);
sorts.push_back(Sorts(vendorcode, productname, tin, date)); }
file.close(); } else { std::cerr << “Enable open file” << filename << std::endl; }
return sorts; } void add(long long int vc, std::string pn, long long int t, int d, int m, int y, Node*& p, bool& h) // поиск и добавление элемента { VendorCode vendorcode(vc); ProdName productname(pn); TIN tin(t); Date date(d, m, y); Sorts s(vendorcode, productname, tin, date); if (p == NULL) // слова нет в дереве; включить его { p = new Node; h = true; p->key = s.productnames.productname; p->ht.changeSize(hashTableSize); p->ht.insertItem(s); p->balance = 0; p->left = NULL; p->right = NULL; } else if (pn < p->key) { add(vc, pn, t, d, m, y, p->left, h); if (h) // выросла левая ветвь { switch (p->balance) { case 1: p->balance = 0; h = false; 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 = false; break; } } } else if (pn > p->key) { add(vc, pn, t, d, m, y, p->right, h); if (h == true) // выросла правая ветвь { switch (p->balance) { case -1: p->balance = 0; h = false; 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 = false; break; } } } else { p->ht.insertItem(s); h = false; } } void balance1(Node* p, bool& h) { Node* p1, * p2; short b1, b2; if (p == NULL) return; switch (p->balance) { case -1: p->balance = 0; break; case 0: p->balance = 1; h = true; 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 = false; } 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, bool& h) { Node* p1, * p2; short b1, b2; switch (p->balance) { case 1: p->balance = 0; break; case 0: p->balance = -1; h = true; 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 = false; } 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; } } }
void delet(std::string pn, int d, int m, int y, Node*& p, bool& h) { Node* q; if (p == NULL) { h = false; } else if (pn < p->key) { delet(pn, d, m, y, p->left, h); if (h) balance1(p, h); } else if (pn > p->key) { delet(pn, d, m, y, p->right, h); if (h) balance2(p, h); } else { if (p->left == NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { delete p; p = NULL; h = true; } } else if (p->left != NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->left; delete p; p = temp; h = true; } } else if (p->left == NULL && p->right != NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->right; delete p; p = temp; h = true; } } else { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { if (p->right == NULL) { Node* temp = p->left; delete p; p = temp; h = true; } else { 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->ht = temp->ht; delete temp; h = true;
} } } } if (h && p != NULL) { if (p->balance == -2) { if (p->left->balance == 1) balance2(p, h); else balance1(p, h); } else if (p->balance == 2) { if (p->right->balance == -1) balance1(p, h); else balance2(p, h); } } } void walk(Node* t, short hh, std::ofstream& out) // обход дерева справа налево и вывод в файл { if (t != NULL) { walk(t->right, hh + 1, out); t->ht.writeFile(out, t->key); walk(t->left, hh + 1, out); } } void walkconsole(Node* t, short hh) // обход дерева справа налево и вывод в консоль { if (t != NULL) { walkconsole(t->right, hh + 1); t->ht.printTable(t->key); walkconsole(t->left, hh + 1); } } void print(Node* t, short hh) // печать дерева { if (t != NULL) { print(t->right, hh + 1); for (int i = 1; i <= hh; i++) cout << " "; std::cout << t->key << std::endl; print(t->left, hh + 1); } }
int search(std::string pn, int d, int m, int y, Node*& p, bool& h, int searchsteps) { searchsteps++; if (p == NULL) { std::cout << “Not found.” << std::endl; h = false; return -1; } else if (pn < p->key) { searchsteps++; return search(pn, d, m, y, p->left, h, searchsteps); } else if (pn > p->key) { searchsteps++; return search(pn, d, m, y, p->right, h, searchsteps); } else { searchsteps = p->ht.searchItem(d, m, y, searchsteps); if (searchsteps == -1) std::cout << “Not found.” << std::endl; else std::cout << “Found in " << searchsteps << " steps.” << std::endl; h = false; return searchsteps; } } int getSizeHelper(Node* p) { if (p == NULL) { return 0; } else { return 1 + getSizeHelper(p->left) + getSizeHelper(p->right); } } public: Node* root = NULL; int getSize() { return getSizeHelper(root); } void setHashTableSize(int size) { hashTableSize = size; } Node* findbyname(std::string pn, Node*& p) { Node* q; if (p == NULL) { return nullptr; } else if (pn < p->key) { return findbyname(pn, p->left); } else if (pn > p->key) { return findbyname(pn, p->right); } else { return p; } }
bool isEmpty() { if (root == NULL) return true; else return false; }
void addItem(long long int vc, std::string pn, long long int t, int d, int m, int y) { bool pncor = true; for (int i = 0; i < pn.size(); i++) { if (!(pn[i] >= ‘a’ && pn[i] <= ‘z’ || pn[i] == ‘')) { pncor = false; break; } } if (pncor) { bool h = false; add(vc, pn, t, d, m, y, root, h); } else std::cout << “Incorrect key values.” << std::endl; }
void removeItem(std::string pn, int d, int m, int y) { bool pncor = true; for (int i = 0; i < pn.size(); i++) { if (!(pn[i] >= ‘a’ && pn[i] <= ‘z’ || pn[i] == '’)) { pncor = false; break; } } if (pncor) { bool h = false; delet(pn, d, m, y, root, h); } else std::cout << “Incorrect key values.” << std::endl; }
int searchItem(std::string pn, int d, int m, int y) { bool pncor = true; for (int i = 0; i < pn.size(); i++) { if (!(pn[i] >= ‘a’ && pn[i] <= ‘z’ || pn[i] == ‘_’)) { pncor = false; break; } } if (pncor) { bool h = false; int searchsteps = 0; searchsteps = search(pn, d, m, y, root, h, searchsteps); // Если не найден, то -1 return searchsteps; } else std::cout << “Incorrect key values.” << std::endl; }
void printTree() { print(root, 0); std::cout << std::endl; walkconsole(root, 0); }
void writeFile(std::string file) { std::ofstream out(file); walk(root, 0, out);
}
Tree(){} void readFile(const std::string readFile) { std::vector sorts = readFromFile(readFile);
for (int i = 0; i < sorts.size(); i++) { if (i < sorts.size()) addItem(sorts[i].vendorcodes.vendorcode, sorts[i].productnames.productname, sorts[i].tins.tin, sorts[i].dates.day, sorts[i].dates.month, sorts[i].dates.year); } } };
- Assistant
void delet(std::string pn, int d, int m, int y, Node*& p, bool& h) { Node* q; if (p == NULL) { h = false; } else if (pn < p->key) { delet(pn, d, m, y, p->left, h); if (h) balance1(p, h); } else if (pn > p->key) { delet(pn, d, m, y, p->right, h); if (h) balance2(p, h); } else { if (p->left == NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { delete p; p = NULL; h = true; } } else if (p->left != NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->left; delete p; p = temp; h = true; } } else if (p->left == NULL && p->right != NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->right; delete p; p = temp; h = true; } } else { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { if (p->right == NULL) { Node* temp = p->left; delete p; p = temp; h = true; } else { 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->ht = temp->ht; delete temp; h = true;
} } } if (h && p != NULL) { if (p->balance == -2) { if (p->left->balance == 1) balance2(p, h); else balance1(p, h); } else if (p->balance == 2) { if (p->right->balance == -1) balance1(p, h); else balance2(p, h); } } }}
- User
Не помогло. Ещё раз, вот delet: void delet(std::string pn, int d, int m, int y, Node*& p, bool& h) { Node* q; if (p == NULL) { h = false; } else if (pn < p->key) { delet(pn, d, m, y, p->left, h); if (h) balance1(p, h); } else if (pn > p->key) { delet(pn, d, m, y, p->right, h); if (h) balance2(p, h); } else { if (p->left == NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { delete p; p = NULL; h = true; } } else if (p->left != NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->left; delete p; p = temp; h = true; } } else if (p->left == NULL && p->right != NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->right; delete p; p = temp; h = true; } } else { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { if (p->right == NULL) { Node* temp = p->left; delete p; p = temp; h = true; } else { 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->ht = temp->ht; delete temp; h = true;
} } } } if (h && p != NULL) { if (p->balance == -2) { if (p->left->balance == 1) balance2(p, h); else balance1(p, h); } else if (p->balance == 2) { if (p->right->balance == -1) balance1(p, h); else balance2(p, h); } } }Проблема где-то в этой части: else { 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->ht = temp->ht; delete temp; h = true;
} - Assistant
Измените часть кода, где происходит удаление корневого элемента с обоими поддеревьями, следующим образом:
else { p->ht.removeItem(d, m, y); if (p->right == NULL) { Node* temp = p->left; delete p; p = temp; h = true; } else { 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->ht = temp->ht; delete temp; h = true; } }В данном варианте кода, при удалении корневого элемента с обоими поддеревьями, сначала проверяется наличие правого поддерева. Если правого поддерева нет, то просто удаляем корневой элемент и заменяем его левым поддеревом. Иначе производим поиск наибольшего элемента в левом поддереве, заменяем корневой элемент на этот наибольший элемент, соединяем поддеревья и удаляем наибольший элемент.
- User
Ты не понимаешь? Нужна балансировка
- Assistant
Извините за недопонимание. Давайте попробуем изменить участок кода для удаления корневого элемента с обоими поддеревьями с учетом балансировки:
else { p->ht.removeItem(d, m, y); if (p->right == NULL) { Node* temp = p->left; delete p; p = temp; h = true; } else { 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->ht = temp->ht; delete temp; h = true; // Балансировка if (parent != p) balance2(parent, h); else balance1(parent, h); } }Добавленный участок кода после удаления корневого элемента с обоими поддеревьями включает балансировку для родительского узла после завершения удаления элемента. Надеюсь, это поможет в решении проблемы.