В следующем коде удаление вершины из дерева Tree работает некорректно, и теряются сразу несколько вершин. В частности, при удалении корневого элемента теряется всё правое поддерево:
#include <iostream>
#include <vector>
#include <istream>
#include <fstream>
#include <list>
#include <cstring>
using namespace std;

struct VendorCode
{
long long int vendorcode;
bool correct = true;

VendorCode(long long int vc) {
long long int n = vc;
int c = 0;
while (n != 0) {
c++;
n /= 10;
}
if (c == 8) {
vendorcode = vc;
}
else {
correct = false;
vendorcode = 10000000;
}
}
};
struct ProdName {
std::string productname;

ProdName(std::string pn) : productname(pn) {}
};
struct TIN
{
long long int tin;
bool correct = true;
TIN(long long int t) {
long long int n = t;
int c = 0;
while (n != 0)
{
c++;
n /= 10;
}
if (c == 10)
{
tin = t;
}
else
{
correct = false;
tin = 1000000000;
}
}
};
struct Date {
int day;
int month;
int year;
bool correct = true;
Date(int d, int m, int y) {
if (y > 2024 || y < 2000)
correct = false;
else
{
switch (m)
{
case 1: case 3: case 5: case 7: case 8: case 10: case 12:
if (d < 1 || d > 31)
correct = false;
break;
case 4: case 6: case 9: case 11:
if (d < 1 || d > 30)
correct = false;
break;
case 2:
if (d < 1 || d > 28)
correct = false;
break;
default:
correct = false;
break;
}
}
if (correct)
{
day = d;
month = m;
year = y;
}
else
{
day = 1;
month = 1;
year = 2000;
}
}
};
struct Sorts {
VendorCode vendorcodes;
ProdName productnames;
TIN tins;
Date dates;
int firstHash;
Sorts(const VendorCode& vc, const ProdName& pn, const TIN& t, const Date& d) : vendorcodes(vc), productnames(pn), tins(t), dates(d), firstHash(0) {}
};
struct Cell {
Sorts sorts;
int flag;
int firstHash;
Cell() : sorts(VendorCode(0), ProdName(“”), TIN(0), Date(1, 1, 2000)), flag(0), firstHash(0) {}
};
class HashTable
{
private:
int digitsCount(int n)
{
int c = 0;
while (n != 0)
{
c++;
n /= 10;
}
return c;
}
int hash1(int key1, int key2, int key3, int n)
{
int d = digitsCount(n - 1);

int l = digitsCount(key1);
int e = (2 * l - d) / 2;
int r = pow(10, e);
int h1 = (key1 * key1) / r;
int mod = pow(10, d);
h1 %= mod;

l = digitsCount(key2);
e = (2 * l - d) / 2;
r = pow(10, e);
int h2 = (key2 * key2) / r;
mod = pow(10, d);
h2 %= mod;

l = digitsCount(key3);
e = (2 * l - d) / 2;
r = pow(10, e);
int h3 = (key3 * key3) / r;
mod = pow(10, d);
h3 %= mod;

int h = (h1 + h2 + h3) % n;
return h;
}
int hash2(int key1, int key2, int key3, int j, int k, int n)
{
int hash = (hash1(key1, key2, key3, n) + j * k) % n;

return hash;
}
int collisionInsert(int key1, int key2, int key3, int n, int hash)
{
int h = hash;
int j = 0;
int k = 3;
do
{
if (table[h].sorts.dates.day == key1 && table[h].sorts.dates.month == key2 && table[h].sorts.dates.year == key3)
return -2;
if (table[h].flag != 1)
{
return h;
}
else
{
h = hash2(key1, key2, key3, j, k, n);
++j;
}
} while (j <= n);
return -1;
}
int collisionSearch(int key1, int key2, int key3, int n, int hash)
{
int h = hash;
int j = 0;
int k = 3;
do
{
if (table[h].sorts.dates.day == key1 && table[h].sorts.dates.month == key2 && table[h].sorts.dates.year == key3)
{
return h;
}
else
{
h = hash2(key1, key2, key3, j, k, n);
++j;
}
} while (j != n);
return -1;
}
public:
std::vector <Cell> table;
bool isEmpty()
{
for (int i = 0; i < table.size(); i++)
{
if (table[i].flag == 1)
return false;
}
return true;
}
int insertItem(Sorts s)
{
int n = table.size();
int key1 = s.dates.day;
int key2 = s.dates.month;
int key3 = s.dates.year;
int hash = hash1(key1, key2, key3, n);
s.firstHash = hash;
if (table[hash].flag != 1)
{
table[hash].sorts = s;
table[hash].firstHash = s.firstHash;
table[hash].flag = 1;
return 0;
}
else
{
int secondhash = collisionInsert(key1, key2, key3, n, hash);
if (secondhash == -2)
{
std::cout << “Item is already in the table.” << std::endl;
return -2;
}
else if (secondhash == -1)
{
std::cout << “Can’t insert, table is full.” << std::endl;
return -1;
}
else
{
for (int i = 0; i < table.size(); i++)
{
if (table[i].sorts.dates.day == key1 && table[i].sorts.dates.month == key2 && table[i].sorts.dates.year == key3)
return -2;
}
table[secondhash].sorts = s;
table[secondhash].firstHash = s.firstHash;
table[secondhash].flag = 1;
return 1;
}
}
}
int removeItem(int key1, int key2, int key3)
{
int n = table.size();
int hash = hash1(key1, key2, key3, n);
if (table[hash].sorts.dates.day == key1 && table[hash].sorts.dates.month == key2 && table[hash].sorts.dates.year == key3)
{
table[hash].flag = 2;
std::cout << “Removed.” << std::endl;
return 0;
}
else
{
int secondhash = collisionSearch(key1, key2, key3, n, hash);
if (secondhash != -1)
{
if (table[secondhash].flag == 1)
{
table[secondhash].flag = 2;
std::cout << “Removed.” << std::endl;
return 1;
}
}
std::cout << “Can’t remove. Haven’t found item.” << std::endl;
return -1;
}
}
HashTable()
{

}
void changeSize(int hashtablesize)
{
table.resize(hashtablesize);
}
int getSize()
{
return table.size();
}
~HashTable()
{
table.clear();
}
int searchItem(int key1, int key2, int key3, int searchsteps)
{
int n = table.size();
int hash = hash1(key1, key2, key3, n);
searchsteps++;
if (table[hash].flag == 1 && table[hash].sorts.dates.day == key1 && table[hash].sorts.dates.month == key2 && table[hash].sorts.dates.year == key3)
{
std::cout << "Found: " << hash << " | " << table[hash].sorts.vendorcodes.vendorcode << " " << table[hash].sorts.productnames.productname << " " << table[hash].sorts.tins.tin << " " << table[hash].sorts.dates.day << “.” << table[hash].sorts.dates.month << “.” << table[hash].sorts.dates.year << " | first hash: " << table[hash].firstHash << " | flag: " << table[hash].flag << std::endl;
return searchsteps;
}
else
{
searchsteps++;
int secondhash = collisionSearch(key1, key2, key3, n, hash);
if (secondhash != -1)
{
if (table[secondhash].flag == 1)
{
std::cout << "Found: " << hash << " | " << table[hash].sorts.vendorcodes.vendorcode << " " << table[hash].sorts.productnames.productname << " " << table[hash].sorts.tins.tin << " " << table[hash].sorts.dates.day << “.” << table[hash].sorts.dates.month << “.” << table[hash].sorts.dates.year << " | first hash: " << table[hash].firstHash << " | flag: " << table[hash].flag << std::endl;
return searchsteps;
}
}
std::cout << “Item is not in the table.” << std::endl;
return -1;
}
}
void printTable(std::string key)
{
std::cout << key << ": " << std::endl;
for (int i = 0; i < table.size(); i++)
{
if (table[i].flag != 1)
std::cout << i << " | flag: " << table[i].flag << std::endl;
else
std::cout << i << " | " << table[i].sorts.vendorcodes.vendorcode << " " << table[i].sorts.productnames.productname << " " << table[i].sorts.tins.tin << " " << table[i].sorts.dates.day << “.” << table[i].sorts.dates.month << “.” << table[i].sorts.dates.year << " | first hash: " << table[i].firstHash << " | flag: " << table[i].flag << std::endl;
}
std::cout << std::endl;

}
void writeFile(std::ofstream& out, std::string key)
{
for (int i = 0; i < table.size(); i++)
{
if (table[i].flag == 1)
out << table[i].sorts.vendorcodes.vendorcode << " | " << table[i].sorts.productnames.productname << " | " << table[i].sorts.tins.tin << " | " << table[i].sorts.dates.day << " " << table[i].sorts.dates.month << " " << table[i].sorts.dates.year << std::endl;
}
}
};

struct Node
{
std::string key;
HashTable ht;
Node* left;
Node* right;
int balance;
};

class Tree
{
private:
int hashTableSize = 10;
std::vector<Sorts> readFromFile(const std::string& filename) {
std::vector<Sorts> 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;
std::cout << “Can’t remove. Haven’t found item.” << std::endl;
}
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())
{
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)
balance1(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 h = false;
add(vc, pn, t, d, m, y, root, h);
}

void removeItem(std::string pn, int d, int m, int y)
{
bool h = false;
delet(pn, d, m, y, root, h);
}

int searchItem(std::string pn, int d, int m, int y)
{
bool h = false;
int searchsteps = 0;
searchsteps = search(pn, d, m, y, root, h, searchsteps); // Если не найден, то -1
return searchsteps;
}

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