#include <time.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <string>
using namespace std;
typedef struct Node {
int n;
Node *parent;
//string info[3];
int key[3];
Node* ptr[4];
}Node;
typedef struct Table{
string fname;
Node *root;
}Table;
#pragma region Заголовки
vector<string> msgs = { "0. Quit", "1. Add", "2. Show", "3. Delete", "4. Find", "5. Timing","6. Return next" };
vector<string> errmsgs = { "Ok", "Duplicate key" };
vector<string> msgdel = { "Ok","No Item" };
bool StrToInt(string str, int* k)
{
try
{
*k = std::stoi(str);
return true;
}
catch (const std::exception&)
{
return false;
}
}
int dialog();
int D_Add(Node** root);
int D_Show(Node** root);
int D_Delete(Node** root);
int D_Find(Node** root);
int D_Timing(Node**);
int D_Return(Node** root);
//D_Add
int findplace(Node* cur);
Node* split(Node* cur, int position);
int insert(Node** root, int k, string info);
//D_Show
void printTree(Node* root, int level);
void reserve(Node* root);
//D_Delete
Node* workhead(Node*);
Node* sit1(Node*, int k);
Node* sit2(Node*, int);
int del(Node** root, int k);
//D_Find
int find(Node** root, int k);
//D_Timing
int findt(Node** root, int k);
//D_Return
int findr(Node** root, int k);
bool D_Load(Table* ptab);
bool loaded(Table* ptab, string fname);
int D_Save(Table* ptab);
void save(FILE* fp, Node* cur);
void delTree(Node* root);
#pragma endregion
int dialog()
{
string errmsg = "";
string result;
int i,rc;
while (true)
{
for (i = 0; i < msgs.size(); ++i)
cout << msgs[i] << endl;
cin >> result;
if (StrToInt(result, &rc) && rc >= 0 && rc <= 6)
return rc;
else
cout << "Wrong. Repeat.";
}
return 0;
}
//1.
int D_Add(Node** root)
{
int k, rc;
string info = "", str;
do
{
cout << "Enter key:-->";
cin >> str;
} while (!StrToInt(str, &k));
cout << "Enter info:" << endl;
cin >> info;
if (info == "")
return 0;
rc = insert(root, k, info);
cout << errmsgs[rc] << " : " << k << endl;
return 1;
}
//2.
int D_Show(Node **root)
{
int level = 0, k = 0, n;
Node *cur=*root;
string str;
do
{
cout << "Which kind of form?" << endl;
cout << "0.Tree N.Inverse" << endl;
cin >> str;
} while (!StrToInt(str, &k));
if (k==0)
printTree(cur,level);
else
reserve(cur);
return 1;
}
//3.
int D_Delete(Node** root)
{
int k = 0, rc;
string str;
do
{
cout << "Enter key:-->";
cin >> str;
} while (!StrToInt(str, &k));
rc = del(root, k);
cout << msgdel[rc] << ": " << k;
return 1;
}
//4.
int D_Find(Node **root)
{
int k,rc,n;
string str;
do
{
cout << "Enter key:-->";
cin >> str;
} while (!StrToInt(str, &k));
rc = find (root,k);
if (rc == 0)
cout << "No item" << endl;
else
cout << "Ok - " << k << endl;;
return 1;
}
//5.
int D_Timing(Node** cur)
{
Node* root = NULL;
int n = 10, key[10000], k, cnt = 1000000, i, m;
clock_t first, last;
srand(time(NULL));
while (n-- > 0)
{
for (i = 0; i < 10000; ++i)
key[i] = rand() * rand();
for (i = 0; i < cnt;)
{
k = rand() * rand();
if (!insert(&root, k, "a"))
++i;
}
m = 0;
first = clock();
for (i = 0; i < 10000; ++i)
if (findt(&root, key[i]))
++m;
last = clock();
cout << m << "items was found" << endl;
cout << "test #" << 10 - n << ", number of nodes = " << (10 - n) * cnt << ", time = " << last - first << endl;
}
delTree(root);
return 1;
}
//6.
int D_Return(Node **root)
{
int k,rc,n;
printf("Enter key:-->");
//n=getInt(&k);
if (n==0)
return 0;
rc = findr (root,k);
if (rc==1)
printf("No item\n");
else
printf("Ok\n",k);
return 1;
}
//D_Add
int findplace(Node *cur) //Поиск узла необходимого для разбиения
{
int k = cur->key[1];
Node *par= cur->parent;
for (int i=0;i<par->n;++i)
if (k < par->key[i])
return i;
return par->n;
}
Node *split(Node *cur,int position)
{
//for (int i = 0; i < 4; i++)
//{
// x->ptr[i] = 0;
// y->ptr[i] = 0;
// z->ptr[i] = 0;
//}
//for (int i = 0; i < 3; i++)
//{
// x->key[i] = 0;
// y->key[i] = 0;
// z->key[i] = 0;
// x->info[i] = "";
// y->info[i] = "";
// z->info[i] = "";
//}
//Узел который мы должны разбить
Node* x = new Node();//левый узел
Node* z = new Node();//правый узел
Node* par = cur->parent;
if (par != NULL) // Случай когда разбиваем не корневую вершину
{
for (int i = 2; i > position; --i)//Сдвигаем вправо в предке ключи
{
par->key[i] = par->key[i - 1];
//par->info[i] = par->info[i - 1];
}
for (int i = 3; i > position + 1; --i)//сдвигаем указатели
par->ptr[i] = par->ptr[i - 1];
par->key[position] = cur->key[1];
//par->info[position] = cur->info[1];
par->ptr[position] = x;
par->ptr[position + 1] = z;
par->n++;
x->parent = par;
z->parent = par;
//Описываем левого
x->n = 1;
x->key[0] = cur->key[0];
//x->info[0] = cur->info[0];
if (cur->ptr[0] != NULL)//Если есть внизу листья надо указать им предка
{
x->ptr[0] = cur->ptr[0];
x->ptr[0]->parent = x;
}
if (cur->ptr[1] != NULL)
{
x->ptr[1] = cur->ptr[1];
x->ptr[1]->parent = x;
}
//Правого
z->n = 1;
z->key[0] = cur->key[2];
//z->info[0] = cur->info[2];
if (cur->ptr[2] != NULL)//Если есть внизу листья надо указать им предка
{
z->ptr[0] = cur->ptr[2];
z->ptr[0]->parent = z;
}
if (cur->ptr[3] != NULL)
{
z->ptr[1] = cur->ptr[3];
z->ptr[1]->parent = z;
}
//Возвращаем предка в который скинули медиалнный узел
delete cur;
return par;
}
else
{
cur->n = 1;
x->parent = cur;
z->parent = cur;
x->n = 1;
x->key[0] = cur->key[0];
//x->info[0] = cur->info[0];
if (cur->ptr[0] != NULL)
{
x->ptr[0] = cur->ptr[0];
x->ptr[0]->parent = x;
}
if (cur->ptr[1] != NULL)
{
x->ptr[1] = cur->ptr[1];
x->ptr[1]->parent = x;
}
z->n = 1;
z->key[0] = cur->key[2];
//z->info[0] = cur->info[2];
if (cur->ptr[2] != NULL)
{
z->ptr[0] = cur->ptr[2];
z->ptr[0]->parent = z;
}
if (cur->ptr[3] != NULL)
{
z->ptr[1] = cur->ptr[3];
z->ptr[1]->parent = z;
}
cur->key[0] = cur->key[1];
//cur->info[0] = cur->info[1];
cur->ptr[0] = x;
cur->ptr[1] = z;
//для удобства отладки очистим остальные поля
cur->key[1] = 0;
//cur->info[1] = "";
cur->key[2] = 0;
//cur->info[2] = "";
cur->ptr[2] = NULL;
cur->ptr[3] = NULL;
//Возвращаем результат разбиения
return cur;
}
}
int insert(Node** root, int k, string info)
{
int i, j = 0, f = 0;
Node* newnode = NULL, * cur = NULL;
if (*root == NULL) //Проверяем корень дерева
{
*root = new Node();
(*root)->n = 1;
(*root)->key[0] = k;
//(*root)->info[0] = info;
(*root)->parent = NULL;
for (i = 0; i < 4; ++i)
(*root)->ptr[i] = NULL;
return 0;
}
cur = *root;
while (cur != NULL)
{
if (cur->n == 3)//Если узел полный
{
if(cur->parent!=NULL)
j = findplace(cur);
cur = split(cur, j);
if (cur->parent==NULL)
*root = cur;
}
for (i = 0; i < cur->n; ++i) //Проверяем ключи
if (cur->key[i] == k)
return 1;
//Вставка элементов узел
if (k < cur->key[0]) //Уход в 1 ветвь
{
if (cur->ptr[0] == NULL)//Листа нет
{
//Вставляем со сдвигом вправо.
cur->key[2] = cur->key[1];
//cur->info[2] = cur->info[1];
cur->key[1] = cur->key[0];
//cur->info[1] = cur->info[0];
cur->key[0] = k;
//cur->info[0] = info;
cur->ptr[3] = cur->ptr[2];
cur->ptr[2] = cur->ptr[1];
cur->ptr[1] = NULL;
cur->n++;
return 0;
}
else
cur = cur->ptr[0];
}
else
if (cur->n == 1 || k < cur->key[1])//Случай когда либо 1 элемент либо надо вставить между 1 и 2 *|А|*|*
{
if (cur->ptr[1] == NULL)
{
cur->key[2] = cur->key[1];
//cur->info[2] = cur->info[1];
cur->ptr[3] = cur->ptr[2];
cur->ptr[2] = NULL;
cur->key[1] = k;
//cur->info[1] = info;
cur->n++;
return 0;
}
else
cur = cur->ptr[1];
}
else
{
if (cur->ptr[2] == NULL)
{
cur->key[2] = k;
//cur->info[2] = info;
cur->n = 3;
cur->ptr[3] = NULL;
return 0;
}
else
cur = cur->ptr[2];
}
}
}
//D_Show
void printTree(Node *root,int level)
{
int i;
if (root)
{
printTree(root->ptr[0],level+1);
for ( i=0;i<level;i++)
printf(" ");
if (root->n==1)
{
printf(" {%d} \n",root->key[0]);
printf("\n");
}
else
printf(" {%d \n",root->key[0]);
if (root->n > 1)
{
for ( i=0;i<level;i++)
printf(" ");
if (root->n==2)
{
printf(" %d} \n",root->key[1]);
printf("\n");
}
else
printf(" %d \n",root->key[1]);
}
printTree(root->ptr[1],level+1);
printTree(root->ptr[2],level+1);
if (root->n > 2)
{
for ( i=0;i<level;i++)
printf(" ");
printf(" %d}\n",root->key[2]);
printf("\n");
}
printTree(root->ptr[3],level+1);
}
}
void reserve(Node* root)
{
/*if (root == NULL)
{
return;
}
reserve(root->ptr[3]);
if (root->n == 3)
printf("%d:%s ", root->key[2], root->info[2]);
reserve(root->ptr[2]);
if (root->n > 1)
printf("%d:%s ", root->key[1], root->info[1]);
reserve(root->ptr[1]);
printf("%d:%s ", root->key[0], root->info[0]);
reserve(root->ptr[0]);*/
}
//D_Delete
Node *sit1(Node *cur,int k)
{
int j,i,p,s;
Node *rod,*x1=NULL,*x2=NULL,*z1,*z2;
while (cur != NULL)
{
j=cur->n;
for (i=0;i<cur->n;++i)
{
if (k==cur->key[i])
{
rod=cur->parent;
for(p=0;p<rod->n+1;++p)
{
if (rod->ptr[p]==cur)
break;
}
if (p+1 <=rod->n)
x1=rod->ptr[p+1];
if (p-1 >= 0)
x2=rod->ptr[p-1];
if (cur->n==1)
{
if (x1 != NULL)
if (x1->n >=2)
{
cur->key[1]=rod->key[p];
//cur->info[1]=rod->info[p];
cur->n=cur->n+1;
rod->key[p]=x1->key[0];
//rod->info[p]=x1->info[0];
cur->ptr[2]=x1->ptr[0];
x1->key[0]=x1->key[1];
//x1->info[0]=x1->info[1];
x1->key[1]=x1->key[2];
//x1->info[1]=x1->info[2];
x1->n=x1->n-1;
return cur;
}
if (x2 != NULL)
if ((x2->n >=2) && (rod->n > 1))
{
if (p < rod->n)
{
cur->key[1]=cur->key[0];
//cur->info[1]=cur->info[0];
cur->ptr[2]=cur->ptr[1];
cur->ptr[1]=cur->ptr[0];
cur->ptr[0]=x2->ptr[x2->n-1];
cur->key[0]=rod->key[p-1];
//cur->info[0]=rod->info[p-1];
cur->n=cur->n+1;
}
rod->key[p-1]=x2->key[x2->n-1];
rod->ptr[p-1]=x2;
//rod->info[p-1]=x2->info[x2->n-1];
if (p>= rod->n)
rod->n=rod->n+1;
x2->n=x2->n-1;
return cur;
}
}
else
{
if ((x1 != NULL) && (x2 != NULL))
if ((x1->n==1) && (x2->n==1) && (cur->n==1))
{
if ( x1 != NULL)
{
cur->key[1]=rod->key[p];
//cur->info[1]=rod->info[p];
cur->key[2]=x1->key[0];
//cur->info[2]=x1->info[0];
cur->ptr[2]=x1->ptr[0];
cur->ptr[3]=x1->ptr[1];
rod->n=rod->n-1;
for (s=p;s<rod->n-p;++s)
{
rod->key[s]=rod->key[s+1];
//rod->info[s]=rod->info[s+1];
}
if (p==0)
{
rod->ptr[1]=rod->ptr[2];
rod->ptr[2]=rod->ptr[3];
}
if (p==1)
{
rod->ptr[2]=rod->ptr[3];
}
z1=x1->ptr[0];
z2=x1->ptr[1];
if (z1 != NULL)
z1->parent=cur;
if (z2 != NULL)
z2->parent=cur;
cur->n=3;
return cur;
}
}
}
return cur;
}
if (k < cur->key[i])
{
j=i;
break;
}
}
cur=cur->ptr[j];
}
return NULL;
}
Node *sit2(Node *cur,int i)
{
Node *y=cur->ptr[i],*z=cur->ptr[i+1],*z1,*z2,*rod;
int k,j;
string in;
if (z->n >= 2 )
{
k=cur->key[i];
//in=cur->info[i];
cur->key[i]=z->key[z->n-1];
//cur->info[i]=z->info[z->n-1];
z->key[z->n-1]=k;
//z->info[z->n-1]=in;
cur=z;
}
if (y->n >= 2 )
{
k=cur->key[i];
//in=cur->info[i];
cur->key[i]=y->key[y->n-1];
//cur->info[i]=y->info[y->n-1];
y->key[y->n-1]=k;
//y->info[y->n-1]=in;
cur=y;
}
else
if (y->n >= 2 )
{
k=cur->key[i];
//in=cur->info[i];
cur->key[i]=y->key[y->n-1];
//cur->info[i]=y->info[y->n-1];
y->key[y->n-1]=k;
//y->info[y->n-1]=in;
cur=y;
}
else
if ((y->n == 1) && (z->n == 1))
{
y->key[1]=cur->key[i];
//y->info[1]=cur->info[i];
cur->n=cur->n-1;
cur->ptr[i+1]=NULL;
y->ptr[2]=z->ptr[0];
y->ptr[3]=z->ptr[1];
y->key[2]=z->key[0];
//y->info[2]=z->info[0];
y->n=3;
z1=z->ptr[0];
z2=z->ptr[1];
if (z1 != NULL)
z1->parent=y;
if (z2 != NULL)
z2->parent=y;
for (j=i;j<cur->n-i;++j)
{
cur->key[j]=cur->key[j+1];
//cur->info[j]=cur->info[j+1];
}
if (i==0)
{
cur->ptr[1]=cur->ptr[2];
cur->ptr[2]=cur->ptr[3];
}
if (i==1)
{
cur->ptr[2]=cur->ptr[3];
}
free(z);
if (cur->n==0)
{
y->parent=cur->parent;
rod=cur->parent;
for (j=0;j<rod->n+1;++j)
if (rod->ptr[j]==cur)
{
rod->ptr[j]=y;
free(cur);
}
}
cur=y;
}
return cur;
}
int del(Node** root, int k)
{
Node* cur = *root, * br = NULL, * rod = NULL;
int i, j, c;
cur = workhead(cur);
*root = cur;
if (cur == NULL)
return 1;
while ((cur->ptr[0] != NULL))
{
for (i = 0; i < cur->n; ++i)
if (cur->key[i] == k)
{
cur = sit2(cur, i);
c++;
break;
}
if (c != 1)
cur = sit1(cur, k);
c = 0;
if (cur == NULL)
return 1;
}
if (cur->n > 1)
{
for (i = 0; i < cur->n; ++i)
if (cur->key[i] == k)
{
cur->n = cur->n - 1;
for (j = i; j < cur->n; ++j)
{
cur->key[j] = cur->key[j + 1];
//cur->info[j]=cur->info[j+1];
}
return 0;
}
}
else {
rod = cur->parent;
if (rod == NULL)
{
*root = NULL;
free(cur);
return 0;
}
for (i = 0; i < rod->n + 1; ++i)
{
if (rod->ptr[i] == cur)
{
if ((rod->ptr[i + 1] != NULL) && (rod->n >= i + 1))
{
br = rod->ptr[i + 1];
if (br->n > 1)
{
cur->key[0] = rod->key[i];
//cur->info[0]=rod->info[i];
rod->key[i] = br->key[0];
//rod->info[i]=br->info[0];
br->key[0] = br->key[1];
//br->info[0]=br->info[1];
br->key[1] = br->key[2];
//br->info[1]=br->info[2];
br->n = br->n - 1;
return 0;
}
else
{
if (rod->n == 1)
{
rod->n = 2;
rod->key[1] = rod->key[0];
//rod->info[1]=rod->info[0];
rod->key[0] = br->key[0];
//rod->info[0]=br->info[0];
for (j = 0; j < 3; ++j)
rod->ptr[j] = NULL;
free(cur);
free(br);
return 0;
}
else
rod->ptr[i] = NULL;
free(cur);
return 0;
}
}
else {
rod->ptr[i] = NULL;
free(cur);
return 0;
}
}
}
}
}
Node *workhead(Node *root)
{
Node *cur=root,*y,*z,*z1,*z2;
if ((cur->n==1) && (cur->ptr[0] != NULL) && (cur->ptr[1] != NULL))
{
if ((cur->ptr[0]->n==1) && (cur->ptr[1]->n==1))
{
y=cur->ptr[0];
z=cur->ptr[1];
z1=z->ptr[0];
z2=z->ptr[1];
y->n=3;
y->parent=NULL;
y->key[1]=cur->key[0];
y->key[2]=z->key[0];
y->ptr[2]=z->ptr[0];
y->ptr[3]=z->ptr[1];
z1->parent=y;
z2->parent=y;
free(z);
free(cur);
root=y;
}
}
return root;
}
//D_Find
int find(Node **root,int k)
{
Node *cur=*root;
int i,j;
while (cur != NULL)
{
j=cur->n;
for (i=0;i<cur->n;++i)
{
if (k==cur->key[i])
{
//cout << cur->info[i] << " key:" << cur->key[i] << endl;
cout << " key:" << cur->key[i] << endl;
return 1;
}
if (k < cur->key[i])
{
j=i;
break;
}
}
cur=cur->ptr[j];
}
return 0;
}
//D_Timing
int findt(Node** root, int k)
{
Node* cur = *root;
int i, j;
while (cur != NULL)
{
j = cur->n;
for (i = 0; i < cur->n; ++i)
{
if (k == cur->key[i])
return 1;
if (k < cur->key[i])
{
j = i;
break;
}
}
//if (cur->ptr[j] != NULL)
cur = cur->ptr[j];
}
return 0;
}
//D_Return
int findr(Node** root, int k)
{
Node* cur = *root;
string in;
int i, j, l, n;
while (cur != NULL)
{
j = cur->n;
for (i = 0; i < cur->n; ++i)
{
if (k == cur->key[i])
{
n = cur->n;
if (i < cur->n - 1)
{
l = cur->key[i + 1];
in = cur->key[i + 1];
}
cur = cur->ptr[i + 1];
if (cur != NULL)
{
//printf("\"%s\" key:%d\n",cur->info[0],cur->key[0]);
return 0;
}
else
{
if (i < n - 1)
{
//printf("\"%s\" key:%d\n",in,l);
return 0;
}
}
return 1;
}
if (k < cur->key[i])
{
j = i;
break;
}
}
cur = cur->ptr[j];
}
}
#pragma region Load_Save
bool D_Load(Table* ptab)
{
int rc;
string fname;
cout << "Enter file name: -->";
//getline(cin, fname);
fname = "D:\\tree.txt";
if (fname == "")
return true;
if (loaded(ptab, fname))
return true;
else
{
cout<<"The appropriate date file is not exists";
false;
}
}
bool loaded(Table* ptab, string fname)
{
std::ifstream fin;
fin.open("D:\\tree.txt");
if (fin.is_open())
{
int count;
string str, line;
while (getline(fin, line))
{
stringstream ss(line);
vector <string> array;
while (ss >> str)
array.push_back(str);
insert(&(ptab->root), std::stoi(array[0]), array[1]);
}
fin.close();
return true;
}
else
return false;
}
int D_Save(Table* ptab)
{
//FILE *fd=NULL;
//int c=0;
//fd=fopen(ptab->fname,"w");
//if (fd==NULL)
// return 0;
//save(fd,ptab->root);
//fclose(fd);
return 1;
}
void save(FILE* fp, Node* cur)
{
if (cur == NULL)
{
return;
}
save(fp, cur->ptr[3]);
if (cur->n == 3)
{
fprintf(fp, "%d\n", cur->key[2]);
//fprintf(fp, "%s\n", cur->info[2]);
}
save(fp, cur->ptr[2]);
if (cur->n > 1)
{
fprintf(fp, "%d\n", cur->key[1]);
//fprintf(fp, "%s\n", cur->info[1]);
}
save(fp, cur->ptr[1]);
fprintf(fp, "%d\n", cur->key[0]);
//fprintf(fp, "%s\n", cur->info[0]);
save(fp, cur->ptr[0]);
}
#pragma endregion
void delTree(Node *root)
{
if (root ==NULL)
{
return;
}
delTree(root->ptr[0]);
delTree(root->ptr[1]);
delTree(root->ptr[2]);
delTree(root->ptr[3]);
delete(root);
}
int main() {
Table ptab;
int rc, kc;
int (*fptr[])(Node**) = { NULL, D_Add,D_Show,D_Delete,D_Find,D_Timing,D_Return };
ptab.root = NULL;
if (!D_Load(&ptab))
return 1;
while (rc = dialog())
if (!fptr[rc](&(ptab.root)))
break;
//kc = D_Save(&ptab);
//if (kc == 0)
// printf("Invalid save");
//delTree(ptab.root);
cout << "That all";
return 0;
}