Arbori AVL in C/C++

Un mic demo care lucreaza cu arbori AVL. Programul este scris in C++ (foloseste clase si alocarea dinamica a memoriei)

demo2.cpp

// demo2.cpp
#include <iostream>
#include <fstream>
#include "AVL.h"

using namespace std;

bool CitesteFisier(AVL &arb)
{
	ifstream fin("noduri.txt", ios::in);
	if(fin.fail())
		return false;
	//	citim
	int cheie;
	while(!fin.eof())
	{
		fin>>cheie;
		cout<<cheie<<", ";
		arb.Adauga(cheie);
	}

	fin.close();
	return true;
}

void main()
{
	AVL arb;

	int cheie;
	char opt;
	do
	{
		cout<<"C - initializeaza arborele AVL\n";
		cout<<"I - insereaza un nod cu cheia precizata\n";
		cout<<"S - suprima un nod cu o cheie precizata\n";
		cout<<"V - vizualizeaza arborele pe niveluri\n";
		cout<<"P - determina raportul intre numarul de reechilibrari si numarul de insertii\n";
		cout<<"X - terminare\n";
		cout<<"optiunea: ";
		cin>>opt;
		switch(opt)
		{
		case 'c':
			arb.StergeArbore();
			break;
		case 'i':
			cout<<"cheie: "; cin>>cheie;
			arb.Adauga(cheie);
			break;
		case 's':
			cout<<"cheie: "; cin>>cheie;
			arb.StergeNod(cheie);
			break;
		case 'v':
			arb.Nivele();
			break;
		case 'p':
			arb.StergeArbore();
			cout<<"noduri: ";
			CitesteFisier(arb);
			cout<<endl;
			arb.Statistici();
			cout<<endl;
			break;
		case 'x':
			cout<<"iesire din program\n";
			break;
		default:
			cout<<"optiunea invalida\n";
		}
		cout<<endl;
	}
	while(opt != 'x');
}

AVL.h

// fisierul AVL.h
#pragma once

#include <stdlib.h>
#include <iostream>

using namespace std;

typedef struct Node
{  
	int cheie, h;
	struct Node *st, *dr;
} Node;

class AVL
{
private:
	int nrIns, nrEch, nrNoduri;
	Node *rad, *NIL;

	Node* Sterge(Node *nod, int cheie);
	Node* Insereaza(Node *n, int cheie);
	bool Cauta(Node *n, int cheie);

	Node* Balance(Node *n);
	Node* RotDr(Node *n);
	Node* RotSt(Node *n);

	void DetH(Node *n);
	void StergeArbore(Node *n);
public:
	AVL(void);
	~AVL(void)                  {	StergeArbore();										}
	void Adauga(int cheie)      {	rad = Insereaza(rad, cheie);						}
	void StergeNod(int cheie)   {	rad = Sterge(rad, cheie);							}
	void StergeArbore()         {	StergeArbore(rad); rad = NIL; nrEch = nrIns = nrNoduri = 0;	}

	void Statistici()           {	cout<<"insertii: "<<nrIns<<", echilibrari: "<<nrEch<<endl;	}
	void Nivele();
};

AVL.cpp

// fisierul AVL.cpp
#include "AVL.h"


  
AVL::AVL(void)
{
	nrEch = nrIns = nrNoduri = 0;
	rad = NIL = new Node;
	NIL->cheie = NIL->h = 0;
	NIL->st = NIL->dr = NULL;
}

void AVL::DetH(Node *n)
{
	if(n->st->h > n->dr->h)
		n->h = 1 + n->st->h;
	else
		n->h = 1 + n->dr->h;
}

Node* AVL::RotSt(Node *n)
{  
	Node *t = n->st;  
	
	n->st = t->dr;
	t->dr = n;
	DetH(n);
	DetH(t);
	
	return t;  
}  
  
Node* AVL::RotDr(Node *n)
{  
	Node *t = n->dr;  
   
	n->dr = t->st;
	t->st = n;
	DetH(n);
	DetH(t);
	
	return t;
}  
  
Node* AVL::Balance(Node *n)
{  
	DetH(n);
	if (n->st->h > n->dr->h + 1)
	{
		nrEch++;	//	nr ech
		if (n->st->dr->h > n->st->st->h)
			n->st = RotDr(n->st);
		n = RotSt(n);
	}
	else if (n->dr->h > n->st->h + 1)
	{
		nrEch++;	//	nr ech
		if (n->dr->st->h > n->dr->dr->h)
			n->dr = RotSt(n->dr);
		n = RotDr(n);
	}
	return n;
}

Node* AVL::Insereaza(Node *n, int cheie)
{
	if (n == NIL)
	{
		nrIns++;	//	nr ins
		nrNoduri++;	//	nr nod
		n = new Node;
		n->cheie = cheie;
		n->h = 1;
		n->st = n->dr = NIL;
			return n;
	}
	if (cheie < n->cheie)
		n->st = Insereaza(n->st, cheie);
	else
		n->dr = Insereaza(n->dr, cheie);
	return Balance(n);
}

Node* AVL::Sterge(Node *n, int cheie)
{
	Node *t;
	if(n == NIL)
		return n;
	if(n->cheie == cheie)
	{
		if (n->st == NIL || n->dr == NIL)
		{
			t = n->st;
			if(t == NIL)
				n->dr;
			else
				n->st;
			nrNoduri--;	//	nr nod
			delete n;
			return t;
		}
		else
		{
			for (t = n->dr; t->st != NIL; t = t->st);
			n->cheie = t->cheie;
			n->dr = Sterge(n->dr, t->cheie);
			return Balance(n);
		}
	}
	if (cheie < n->cheie)
		n->st = Sterge(n->st, cheie);
	else
		n->dr = Sterge(n->dr, cheie);
	return Balance(n);
}

void AVL::StergeArbore(Node *n)
{
	if(n == NIL)
		return;
	StergeArbore(n->dr);
	StergeArbore(n->st);
	delete n;
}

bool AVL::Cauta(Node *n, int cheie)
{  
	if (n == NIL)
		return false;
	if (n->cheie == cheie)
		return true;
	if (cheie < n->cheie)
		return Cauta(n->st, cheie);
	else
		return Cauta(n->dr, cheie);
}

void AVL::Nivele()
{
	//	verificari
	if(rad == NULL)
	{
		cout<<"Arborele e gol!\n";
		return;
	}
	//	variabile auxiliare
	Node ** coada = new Node*[nrNoduri];	//	retine nodurile parcurse in latime
	int *nivele = new int[nrNoduri];	//	retine nivelul pe care se afla fiecare nod
	Node *x;
	int 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];
		cout<<x->cheie<<" ";
		//	bagam fii ultimului nod in coada
		//	si completam nivelul nodurilor
		if(x->st != NIL)
		{
			coada[++sf] = x->st;
			nivele[sf] = nivele[inc]+1;
		}
		if(x->dr != NIL)
		{
			coada[++sf] = x->dr;
			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;
}