Arbori B (BTree) in C++

Un mic demo pentru BTree sau Arbori B. Citirea nu este facuta din fisier de data asta, dar nu e un lucru prea important, daca intelegi programul sigur nu o sa ai probleme cu asa ceva :D

demo.cpp

// demo.cpp
#define _CRT_SECURE_NO_WARNINGS



#include <iostream>
#include <stdio.h>

using namespace std;



#include "BTree.h"



void CitireFisier(BTree * arb)
{
	// fisierul este citit linie cu linie, continutul fiecarei linii este adaugat in arbore
	char buf[513];
	FILE *f = fopen("numefis.txt", "r");

	if(f == NULL)
		return; // eroare la deschidere fisier

	while(!foef(f))
	{
		fgets(buf, 512,f);   //   fscanf(f, "%s\n", buf);

		arb->add(buf);
		arb->nivele();
		cout<<endl;
	}
	fclose(f);
}


void main()

{

	BTree arb;

	char buf[512];

	char opt;


	// in loc de for poate fi apelata functia de citire din fisier
	// CitireFisier(&arb);  // sterge liniile de comentariu si for-ul pt a face citire din fisier
	for(int i=10; i<29; i++)

	{

		sprintf(buf, "%2d", 50-i);

		arb.add(buf);

		arb.nivele();

		cout<<endl;

	}

	cout<<"\n\n";



	do

	{

		cout<<"V - face vid arborele\n";

		cout<<"C - cauta o cheie, afisand info\n";

		cout<<"A - adauga o cheie\n";

		cout<<"S - suprima o cheie\n";

		cout<<"L - afiseaza cheile arborelui in ordine crescatoare\n";

		cout<<"P - afiseaza arborele pe pagini\n";

		cout<<"D - afiseaza adancimea arborelui, cheia cea mai mica si cea mai mare\n";

		cout<<"X - terminare\n";

		cout<<"optiunea: ";

		cin>>opt;



		switch(opt)

		{

		case 'v':

			arb.erase();

			cout<<"arborele este gol\n";

			break;

		case 'c':

			cout<<"Cheia cautata: ";

			cin>>buf;

			arb.info(buf);

			break;

		case 'a':

			cout<<"Cheie noua: ";

			cin>>buf;

			arb.add(buf);

			break;

		case 's':

			cout<<"Cheia de sters: ";

			cin>>buf;

			arb.erase(buf);

			break;

		case 'l':

			arb.inord();

			break;

		case 'p':

			cout<<"Arborele afisat pe pagini\n";

			arb.nivele();

			arb.statistici();

			break;

		case 'd':

			arb.info();

			break;

		case 'x':

			break;

		default:

			cout<<"optiune inexistenta\n";

		}



		cout<<endl<<endl;

	}

	while(opt != 'x');

}

Btree.h

// BTree.h
#pragma once

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

class BKey
{
public:
	char *value;
	int nr;

	BKey(char *val)	{
		value = new char[strlen(val) + 1];
		strcpy(value, val);
		nr = 1;	}
	~BKey()	{	if(value)	delete []value;	}
};

class BPage
{
protected:
	static int ordin;
	static int maxChei;
	static BPage *NIL;
public:
	static void setOrdin(int value)	{	
		ordin = value; maxChei = 2*value;	}
	static void setNIL(BPage *nil)	{	NIL = nil;	}

public:
	int h;
	int nrKeys;
	BKey **keys;
	BPage **fii;

public:
	BPage();
	~BPage();

	BKey* getKey(int index);
	BKey* operator[] (int index)	{	return getKey(index);	}
	BPage* getPage(int index);
	BPage* getLeft(int key);
	BPage* getRight(int key);

	int insertKey(BKey *&newKey);
	int insertKey(char *value);
	int insertKey(BKey *&newKey, BPage *left, BPage *right);
	int insertKey(char *value, BPage *left, BPage *right);
	int eraseKey(char *value);
	int eraseKey(char *value, BPage *&left, BPage *&right);
	int eraseKey(int poz);
	int eraseKey(int poz, BPage *&left, BPage *&right);

	BKey* removeKey(int poz, BPage *&left, BPage *&right);
	BKey* removeKey(int poz);

	bool split(BPage *&outLeft, BPage *&outRight, BPage *&outMid);
	bool merge(BPage *&page);
};

class BTree
{
private:
	int ordin;
	int maxChei;
	int nrChei;
	int nrCheiFaraDuplicat;
	int nrPointeriNefolositi;
	int nrPagini;
	BPage *NIL;	//	nu e implementat cu nil
	BPage *rad;

	BPage* addKey(BPage *&rad, char *value);
	BPage* eraseKey(BPage *&rad, char *value);
	BPage* eraseMaxKey(BPage *&rad, BKey *&outErasedValue);
	void eraseAll(BPage *rad);

	BPage* maxPage(BPage *rad);
	BPage* minPage(BPage *rad);
	bool findKey(BPage *father, BPage *rad, char *value, BPage *&outFather, int &outPos);

	void parcInordine(BPage *rad);
	void parcStat(BPage *rad);
public:
	BTree(void);
	~BTree(void);

	void add(char *value);
	void erase(char *value);
	void erase();

	void info(char *value);
	void info();

	void inord();
	void nivele();

	void statistici();
};

BTree.cpp

// BTree.cpp
#include "BTree.h"

BPage::BPage()
{
	keys = new BKey* [sizeof(BKey*) * (maxChei +1)];
	fii = new BPage* [sizeof(BPage*) * (maxChei + 2)];
	nrKeys = 0;
	h = 0;
}
BPage::~BPage()
{
	delete []keys;
	delete []fii;
}

BKey* BPage::getKey(int index)
{
	if(index < 0 || index >= maxChei)
	{
		cout<<"Eroare index-ul cheii nu este corect !!! index=<<"<<index<<"\n";
		return NULL;
	}
	return keys[index];
}

BPage* BPage::getPage(int index)
{
	if(index < 0 || index > maxChei)
	{
		cout<<"Eroare index-ul paginii nu este corect !!! index=<<"<<index<<"\n";
		return NULL;
	}
	return fii[index];
}

BPage* BPage::getLeft(int index)
{
	if(index < 0 || index > maxChei)
	{
		cout<<"Eroare index-ul paginii nu este corect !!! index=<<"<<index<<"\n";
		return NULL;
	}
	return fii[index];
}

BPage* BPage::getRight(int index)
{
	if(index < 0 || index > maxChei)
	{
		cout<<"Eroare index-ul paginii nu este corect !!! index=<<"<<index<<"\n";
		return NULL;
	}
	return fii[index];
}

int BPage::insertKey(BKey *&newKey)
{
	int i, poz, cmp = 1;
	char *newVal = newKey->value;
	for(poz=0; poz<nrKeys && (cmp = strcmp(keys[poz]->value, newVal)) < 0; poz++);
	if(poz == maxChei+1)
	{
		cout<<"Eroare cheia: "<<newVal<<" nu a putut fi inserata !\n";
		return -1;
	}
	//	cheia exista deja
	if(cmp == 0)
	{
		keys[poz]->nr += newKey->nr;
		delete newKey;	//	daca cheie noua exista sub alta forma
		newKey = NULL;	//	trebuie stearsa
		return poz;
	}
	//	trebuie mutate toate elementele cu o pozitie sa facem loc la cheia noua
	for(i=nrKeys; i>poz; i--)
	{
		keys[i] = keys[i-1];
		fii[i+1] = fii[i];
	}
	keys[poz] = newKey;
	nrKeys++;
	return poz;
}

int BPage::insertKey(BKey *&newKey, BPage *left, BPage *right)
{
	int poz = insertKey(newKey);
	fii[poz] = left;
	fii[poz+1] = right;
	return poz;
}

int BPage::insertKey(char *value)
{
	BKey *newKey = new BKey(value);
	return insertKey(newKey);
}

int BPage::insertKey(char *value, BPage *left, BPage *right)
{
	BKey *newKey = new BKey(value);
	return insertKey(newKey, left, right);
}

int BPage::eraseKey(char *value, BPage *&left, BPage *&right)
{
	left = right = NULL;
	int i, poz, cmp = 1;
	for(poz=0; poz<nrKeys && (cmp = strcmp(keys[poz]->value, value)) < 0; poz++);
	if(poz == nrKeys)
		return -1;
	//	cheia a fost gasita
	if(cmp == 0)
	{
		left = fii[poz];
		right = fii[poz+1];
		delete keys[poz];
		for(i=poz; i<nrKeys-1; i++)
		{
			keys[i] = keys[i+1];
			fii[i] = fii[i+1];
		}
		fii[i] = fii[i+1];
		nrKeys--;
		return poz;
	}
	//	cheia nu a fost gasita
	return -1;
}

int BPage::eraseKey(char *value)
{
	BPage *left, *right;
	return eraseKey(value, left, right);
}

int BPage::eraseKey(int poz, BPage *&left, BPage *&right)
{
	if(poz < 0 || poz >= nrKeys)
	{
		cout<<"Eroare stergere indexlul chei nu este corect: "<<poz<<" !!!\n";
		return -1;
	}
	left = fii[poz];
	right = fii[poz+1];
	delete keys[poz];
	int i;
	for(i=poz; i<nrKeys-1; i++)
	{
		keys[i] = keys[i+1];
		fii[i] = fii[i+1];
	}
	fii[i] = fii[i+1];
	nrKeys--;
	return poz;
}

int BPage::eraseKey(int poz)
{
	BPage *left, *right;
	return eraseKey(poz, left, right);
}

BKey* BPage::removeKey(int poz, BPage *&left, BPage *&right)
{
	if(poz < 0 || poz >= nrKeys)
	{
		cout<<"Eroare stergere indexlul chei nu este corect: "<<poz<<" !!!\n";
		return NULL;
	}
	left = fii[poz];
	right = fii[poz+1];
	BKey *rezult = keys[poz];
	int i;
	for(i=poz; i<nrKeys-1; i++)
	{
		keys[i] = keys[i+1];
		fii[i] = fii[i+1];
	}
	fii[i] = fii[i+1];
	nrKeys--;
	return rezult;
}

BKey* BPage::removeKey(int poz)
{
	BPage *left, *right;
	return removeKey(poz, left, right);
}

bool BPage::split(BPage *&outLeft, BPage *&outRight, BPage *&outMid)
{
	outLeft = outRight = NULL;
	outMid = NULL;
	if(nrKeys != maxChei + 1)
	{
		cout<<"Eroare pagina nu poate fi impartita, are: "<<nrKeys<<" chei !!!\n";
		return false;
	}

	int i;
	//	right
	outRight = new BPage();
	for(i=0; i<ordin; i++)
	{
		outRight->keys[i] = keys[ordin + 1 + i];
		outRight->fii[i] = fii[ordin + 1 + i];
	}
	outRight->fii[ordin] = fii[maxChei+1];
	outRight->nrKeys = ordin;
	outRight->h = h;
	//	left
	nrKeys = ordin;
	outLeft = this;
	//	mid
	outMid = new BPage();
	outMid->nrKeys = 1;
	outMid->h = h+1;
	outMid->keys[0] = keys[ordin];
	outMid->fii[0] = outLeft;
	outMid->fii[1] = outRight;

	return true;
}

bool BPage::merge(BPage *&page)
{
	int totalKeys = nrKeys + page->nrKeys;
	if(totalKeys > maxChei + 1)
	{
		cout<<"Eroare, paginile nu pot fi unite, au prea multe noduri: "<<totalKeys<<" in total\n";
		return false;
	}
	int poz;
	if(page->nrKeys == 1)
	{
		poz = insertKey(page->keys[0]);
		fii[poz] = page->fii[0];
		fii[poz+1] = page->fii[1];
	}
	else if(nrKeys == 1)
	{
		poz = page->insertKey(keys[0]);
		page->fii[poz] = fii[0];
		page->fii[poz+1] = fii[1];
		//	copiem tot continut
		int i;
		for(i=0; i<page->nrKeys; i++)
		{
			keys[i] = page->keys[i];
			fii[i] = page->fii[i];
		}
		fii[i] = page->fii[i];
		nrKeys = page->nrKeys;
		h = page->h;
	}
	else
	{
		if(totalKeys > maxChei)
		{
			cout<<"Eroare la unire pagini, ambele pagini au mai mult de 1 cheie si nr total de chei este mai mare decat cel maxim !!!\n";
			return false;
		}
		int nrKeysPage = page->nrKeys;
		int i;
		if(strcmp(keys[nrKeys-1]->value, page->keys[nrKeysPage-1]->value) < 0)
		{
			for(i=0; i<nrKeysPage; i++)
			{
				keys[nrKeys+i] = page->keys[i];
				fii[nrKeys+i] = page->fii[i];
			}
			fii[nrKeys+i] = page->fii[i];
			nrKeys = totalKeys;
		}
		else
		{
			cout<<"Eroare la unire pagini, pagina a doua trebui sa aiba cheile mai mari decat prima !!!\n";
			return false;
		}
	}

	delete page;
	page = NULL;
	return true;
}

//	static
int BPage::ordin = 2;
int BPage::maxChei = BPage::ordin * 2;
BPage* BPage::NIL = NULL;






BTree::BTree(void)
{
	ordin = 2;
	maxChei = 2*ordin;
	nrChei = nrCheiFaraDuplicat = nrPagini = 0;
	rad = NULL;

	BPage::setOrdin(ordin);
	//BPage::setNIL(rad);
}

BTree::~BTree(void)
{
	erase();
}

BPage* BTree::minPage(BPage *rad)
{
	if(rad == NULL)
		return NULL;
	if(rad->h == 0)
		return rad;
	return minPage(rad->fii[0]);
}

BPage* BTree::maxPage(BPage *rad)
{
	if(rad == NULL)
		return NULL;
	if(rad->h == 0)
		return rad;
	return maxPage(rad->fii[rad->nrKeys]);
}

bool BTree::findKey(BPage *father, BPage *rad, char *value, BPage *& outFather, int &outPos)
{
	if(rad == NULL)
		return false;
	//	trebuie sa parcurgem fii
	int poz, cmp;
	for(poz=0; poz<rad->nrKeys && (cmp = strcmp(rad->keys[poz]->value, value)) < 0; poz++);
	//	cheia a fost gasita
	if(cmp == 0)
	{
		outPos = poz;
		outFather = father;
		return true;
	}
	else
	{
		//	cheia nu a fost gasita
		if(poz == rad->nrKeys)
		{
			//	e in dreapta
			if(findKey(rad, rad->fii[poz+1], value, outFather, outPos))
				return true;
		}
		else
		{
			//	e in stanga
			if(findKey(rad, rad->fii[poz], value, outFather, outPos))
				return true;
		}
	}
	return false;
}

void BTree::info(char *value)
{
	BPage *father;
	BPage *page = rad;
	int poz;
	if(!findKey(NULL, rad, value, father, poz))
		cout<<"cheia nu exista!\n";
	else
	{
		if(father == NULL)
			cout<<"este radacina";
		else
		{
			page = father->fii[poz];
			if(poz>0)
				cout<<"cheia "<<father->keys[poz-1]->value<<" este tata stang\n";
			if(poz<father->nrKeys)
				cout<<"cheia "<<father->keys[poz]->value<<" este tatal drept\n";
		}
		cout<<"inaltimea "<<page->h<<"\n";
	}
}

void BTree::info()
{
	if(rad == NULL)
	{
		cout<<"arbore gol\n";
		return;
	}
	cout<<"inaltimea "<<rad->h<<"\n";
	BPage *min = minPage(rad);
	BPage *max = maxPage(rad);
	cout<<"cheie minima "<<min->keys[0]->value<<"\n";
	cout<<"cheia maxima "<<max->keys[max->nrKeys-1]->value<<"\n";
}

BPage* BTree::addKey(BPage *&rad, char *value)
{
	if(rad == NULL)
	{
		rad = new BPage();
		rad->insertKey(value, NULL, NULL);
		nrPagini++;
		nrChei++;
		return rad;
	}
	//	suntem intr-o frunza
	if(rad->h == 0)
	{
		rad->insertKey(value);
		nrChei++;
		if(rad->nrKeys > maxChei)
		{
			nrPagini+= 2;
			BPage *left, *right, *mid;
			rad->split(left, right, mid);
			rad = mid;
			return rad;
		}
		return NULL;
	}
	//	trebuie sa parcurgem fii
	int poz, cmp;
	for(poz=0; poz<rad->nrKeys && (cmp = strcmp(rad->keys[poz]->value, value)) < 0; poz++);
	//	cheia exista
	if(cmp == 0)
	{
		rad->keys[poz]->nr ++;
		return NULL;
	}
	//	cheie trebuie inserata la poz
	BPage* rez = addKey(rad->fii[poz], value);
	if(rez == NULL)
		return NULL;
	if(rez->nrKeys < ordin)
	{
		//	rez trebuie introdus in rad
		rad->merge(rez);
		nrPagini--;
	}
	if(rad->nrKeys > maxChei)
	{
		nrPagini+= 2;
		BPage *left, *right, *mid;
		rad->split(left, right, mid);
		rad = mid;
		return rad;
	}
	return NULL;
}

void BTree::add(char *value)
{
	int h1 = -1, h2;
	if(rad)
		h1 = rad->h;

	addKey(rad, value);
	h2 = rad->h;

	if(h1 != h2)
		cout<<"Arborele a crescut in inaltime, h = "<<h2<<endl;
}

void BTree::nivele()
{
	//	verificari
	if(rad == NULL)
	{
		cout<<"Arborele e gol!\n";
		return;
	}
	//	variabile auxiliare
	BPage ** coada = new BPage*[1000];	//	retine nodurile parcurse in latime
	int *nivele = new int[1000];	//	retine nivelul pe care se afla fiecare nod
	BPage *x;
	int i, n, inc, sf;	//	inceputul si sfarsitul cozii
	//	initializam nivelele, coada.
	nivele[0] = 1;	//	nivelul nodurilor
	coada[0] = rad;	//	primul nod din coada
	inc = sf = 0;	//	inceputul si sfasitul cozii
	//	cata vreme avem noduri in coada
	cout<<"\nNivel 1: ";
	while(inc <= sf)
	{
		//	afisam primul nod din coada
		x = coada[inc];
		n = x->nrKeys;
		//cout<<"("<<x->inaltime<<")";
		cout<<"[";
		for(i=0; i<n-1; i++)
			cout<<x->keys[i]->value<<"|";
		cout<<x->keys[n-1]->value<<"] ";
		//	bagam fii ultimului nod in coada
		//	si completam nivelul nodurilor
		if(x->h != 0)
		{
			//	daca are fii ii adaugam
			for(i=0; i<=n; i++)
			{
				coada[++sf] = x->fii[i];
				nivele[sf] = nivele[inc]+1;
			}
		}
		//	scoatem primul nod din coada
		inc++;
		//	afisam nivelul daca este diferit de nivelul nodului precedent
		if(nivele[inc] != nivele[inc-1] && inc <= sf)
			cout<<"\nNivel "<<nivele[inc]<<": ";
	}

	//	stergem memoria folosita pentru retinerea cozii si a nivelului nodului
	delete[] coada;
	delete[] nivele;
}

void BTree::parcInordine(BPage *rad)
{
	if(rad == NULL)
		return;
	int i;
	if(rad->h == 0)
	{
		for(i=0; i<rad->nrKeys; i++)
			cout<<rad->keys[i]->value<<" ";
	}
	else
	{
		for(i=0; i<rad->nrKeys; i++)
		{
			parcInordine(rad->fii[i]);
			cout<<rad->keys[i]->value<<" ";
		}
		parcInordine(rad->fii[i]);
	}
}

void BTree::inord()
{
	cout<<"cheile in ordine crescatoare:\n";
	parcInordine(rad);
}

void BTree::eraseAll(BPage *rad)
{
	int i;
	if(rad == NULL)
		return;
	if(rad->h != 0)
	{
		for(i=0; i<=rad->nrKeys; i++)
		{
			eraseAll(rad->fii[i]);
			delete rad->fii[i];
		}
	}
	delete rad;	
}

BPage* BTree::eraseMaxKey(BPage *&rad, BKey *&outErasedKey)
{
	int nr;
	if(rad == NULL)
		return NULL;
	//	ne aflam intr-o frunza, stergem max
	if(rad->h == 0)
	{
		nr = rad->nrKeys;
		outErasedKey = rad->keys[nr-1];
		rad->nrKeys--;

		if(rad->nrKeys < ordin)
			return rad;
		return NULL;
	}
	//	mergem la fiul cel mai mare
	nr = rad->nrKeys;
	BPage* rezultat = eraseMaxKey(rad->fii[nr], outErasedKey);
	if(rezultat == NULL)
		return NULL;
	//	rezultatul are ordinul prea mic
	//	stim ca rezultatul este mai mare decat cheia curenta
	nr = rad->nrKeys;
	BPage *fiuStang = rad->fii[nr-1];
	int nrKeysLeft = fiuStang->nrKeys;
	//	putem imprumuta de la stanga
	if(nrKeysLeft > ordin)
	{
		//	cheia cea mai mare trece la dreapta
		rezultat->insertKey(rad->keys[nr-1]);
		//	fiul cel mai mare de la stanga trece ca fiul cel mai mic la dreapta
		rezultat->fii[0] = fiuStang->fii[nrKeysLeft];
		//	mut cheia din stang in radacina
		rad->keys[nr-1] = fiuStang->keys[nrKeysLeft-1];
		//	redimensinam
		fiuStang->nrKeys--;
		return NULL;
	}
	//	nu putem imprumuta, trebui sa facem un nod nou
	fiuStang->insertKey(rad->keys[nr-1]);
	rad->nrKeys--;
	//	adaugam la fiul stang pe fiul drept
	//	fiul stang trebuie sa aiba exact ordin+1 chei
	//	iar cel drept exact ordin-1 chei
	int i;
	for(i=0; i<ordin-1; i++)
	{
		fiuStang->keys[ordin+1+i] = rezultat->keys[i];
		fiuStang->fii[ordin+1+i] = rezultat->fii[i];
	}
	fiuStang->fii[ordin+1+i] = rezultat->fii[i];
	fiuStang->nrKeys = maxChei;
	if(rad->nrKeys < ordin)
	{
		if(rad->nrKeys == 0)
		{
			delete rad;
			rad = fiuStang;
		}
		return rad;
	}
	return NULL;
}

BPage* BTree::eraseKey(BPage *&rad, char *value)
{
	if(rad == NULL)
		return NULL;
	//	ne aflam intr-o frunza
	if(rad->h == 0)
	{
		rad->eraseKey(value);
		if(rad->nrKeys < ordin)
		{
			if(rad->nrKeys == 0)
			{
				delete rad;
				rad = NULL;
			}
			return rad;
		}
		return NULL;
	}
	//	trebuie sa parcurgem fii
	BPage* rezult;
	int poz, cmp = 1;
	for(poz=0; poz<rad->nrKeys && (cmp = strcmp(rad->keys[poz]->value, value)) < 0; poz++);
	if(cmp == 0)
	{
		//	trebuie sters nodul curent
		BKey *maxKey;
		rezult = eraseMaxKey(rad->fii[poz], maxKey);
		//	punem cheia maxima in locul celei sterse
		delete rad->keys[poz];
		rad->keys[poz] = maxKey;
	}
	else
		rezult = eraseKey(rad->fii[poz], value);
	//	nu este afectata structura arborelui de sterger
	if(rezult == NULL)
		return NULL;

	//	arborele a fost dezechilibrat...
	//	rezult are ordin-1 chei
	//	vedem de unde putem imprumuta
	BPage *st = NULL, *dr = NULL;
	int nSt, nDr, insPoz;
	if(poz>0)
	{
		//	avem stanga
		st = rad->fii[poz-1];
		nSt = st->nrKeys;
		if(poz < rad->nrKeys)
		{
			dr = rad->fii[poz+1];
			nDr = dr->nrKeys;
			//	avem stanga si dreapta
			if(nSt > ordin)
			{
				//	imprumut din stanga
				insPoz = rezult->insertKey(rad->keys[poz-1]);
				rezult->fii[insPoz] = st->fii[nSt];
				rad->keys[poz-1]= st->keys[nSt-1];
				st->nrKeys--;
				return NULL;
			}
			if(nDr > ordin)
			{
				//	imprumut din dreapta
				insPoz = rezult->insertKey(rad->keys[poz]);
				rezult->fii[insPoz+1] = dr->fii[0];
				rad->keys[poz] = dr->removeKey(0);
				return NULL;
			}
		}
		else
		{
			//	avem doar stanga
			if(nSt > ordin)
			{
				//	imprumut din stanga
				insPoz = rezult->insertKey(rad->keys[poz-1]);
				rezult->fii[insPoz] = st->fii[nSt];
				rad->keys[poz-1]= st->keys[nSt-1];
				st->nrKeys--;
				return NULL;
			}
		}
		//	trebuie unita cheia curenta cu cheia stanga
		insPoz = st->insertKey(rad->keys[poz-1]);	//	-1
		st->fii[st->nrKeys] = rezult->fii[0];	//	fiu mijloc, ca sa fim siguri
		st->merge(rezult);
		//	trebuie sa modificam radacina
		rad->fii[poz] = st;		//	-1
		rad->removeKey(poz-1);
		if(rad->nrKeys < ordin)
		{
			//	a scazut in nivel
			if(rad->nrKeys == 0)
			{
				delete rad;
				rad = st;
			}
			return rad;
		}
		return NULL;
	}
	else
	{
		//	avem doar dreapta
		dr = rad->fii[poz+1];
		nDr = dr->nrKeys;
		if(nDr > ordin)
		{
			//	imprumut din dreapta
			insPoz = rezult->insertKey(rad->keys[poz]);
			rezult->fii[insPoz+1] = dr->fii[0];
			rad->keys[poz] = dr->removeKey(0);
			return NULL;
		}
		///////
		nivele();
		//	trebuie unita cheia curenta cu cheia dreapta
		insPoz = rezult->insertKey(rad->keys[poz]);
		rezult->fii[rezult->nrKeys] = dr->fii[0];	//	fiu mijloc, ca sa fim siguri
		rezult->merge(dr);
		//	trebuie sa modificam radacina
		rad->fii[poz+1] = rezult;
		rad->removeKey(poz);
		if(rad->nrKeys < ordin)
		{
			//	a scazut in nivel
			if(rad->nrKeys == 0)
			{
				delete rad;
				rad = rezult;
			}
			return rad;
		}
		return NULL;
	}

	return NULL;
}

void BTree::erase(char *value)
{
	int h1 = -1, h2=-1;
	if(rad)
		h1 = rad->h;
	eraseKey(rad, value);
	if(rad)
		h2 = rad->h;
	if(h1 != h2)
		cout<<"\ninaltime a scazut: "<<h2<<endl;
}

void BTree::erase()
{
	eraseAll(rad);
	rad = NULL;
}

void BTree::parcStat(BPage *rad)
{
	if(rad == NULL) return;

	nrPagini++;
	if(rad->h == 0)
	{
		nrChei += rad->nrKeys;
		nrPointeriNefolositi += rad->nrKeys + 1;
	}
	else
	{
		int i;
		for(i=0; i<rad->nrKeys; i++)
		{
			nrChei++;
			parcStat(rad->fii[i]);
		}
		parcStat(rad->fii[i]);
	}
}

void BTree::statistici()
{
	nrPagini = nrChei = nrPointeriNefolositi = 0;
	parcStat(rad);
	cout<<"\npagini: "<<nrPagini<<"\nchei: "<<nrChei<<"\npointeri nefolositi: "<<nrPointeriNefolositi<<endl;
}