Binary search tree


#1

Ciao a tutti, in questo periodo sono venuto a conoscenza dei BST, e dei BBST, e stavo cercando un modo per implemetarli, qualcuno sa come fare?


#2


questo è il più semplice BBST che ci sia


#3

Mi sono espresso male, intendevo che cerco un modo per implemetare un generico BST, in quanto gli unici alberi che ho usato fino ad adesso sono il fenwik e il segment che alloco facilmente su un vettore, mentre su molti dei problemi del forum vedo che i BST vengono implemetati con classi o struct, (la questione del bilanciamento è accidentale, ho già studiato il meccanismo degli AVL)


#4

Ciao, per rappresentare un bst bisogna innanzitutto definire un nodo, un nodo è formato dalla chiave e da due puntatori al figlio sinistro e destro. Solitamente hai una cosa del tipo:

struct node
{
    int key;
    node *left, *right;
    node(int k) : key(k), left(nullptr), right(nullptr) {}
};

Oppure puoi fare la versione generica templetizzata che hai il vantaggio che puoi sostituire il tipo della chiave con qualsiasi tipo:

template<typename T>
struct node
{
    T key;
    node *left, *right;
    node(T k) : key(k), left(nullptr), right(nullptr) {}
};

L’utilizzo dei puntatori è fondamentale poiché ti permettono gestire in modo efficiente i sotto-alberi.
L’albero viene rappresentato dalla sua radice (spesso chiamata root) inizialmente inizializzata a NULL.
Le operazioni in generale vengono spesso fatte mediante la ricorsione, per esempio nell’inserimento procedo ricorsivamente: se l’elemento da inserire è minore del valore del nodo, inserisco l’elemento nel figlio sinistro, altrimenti lo inserisco nel figlio destro. Solitamente ottieni una cosa di questo tipo:

node *insert(node *p,int val)
{
    if(!p) return new node(val);
    if(val<p->key) p->left=insert(p->left,val);
    else p->right=insert(p->right,val);
    return p;
}

La ricerca è simile all’inserimento:

bool find(node *p,int val)
{
    if(!p) return false;
    if(val<p->key) return find(p->left,val);
    else if(val>p->key) return find(p->right,val);
    return true;
}

La rimozione è un po’ più complicata, ci sono svariati modi per implementarla, io propongo un esempio:

node *erase(node *p,int val)
{
    if(!p) return p;
    if(val<p->key) p->left=erase(p->left,val);
    else if(val>p->key) p->right=erase(p->right,val);
    else if(!p->right) { node *n=p->left; delete p; return n; }
    else
    {
        node *f=p, *n=p->right;
        while(n->left) { f=n; n=n->left; }
        if(f->left==n) f->left=n->right;
        else f->right=n->right;
        p->key=n->key;
        delete n;
    }
    return p;
}

Adesso per chiamare le funzioni basta passargli come parametro la radice:

node *root=nullptr;
root=insert(root,42);
cout<<find(root,42);
root=erase(root,42);

Fintanto che vi è un solo albero si può gestire mediante un nodo, ma quando le cose diventano complicate è bene gestire il tutto con una classe.
Solitamente quando ho bisogno prendo spunto da @dp_1.
Spero di esserti stato di aiuto, se c’è qualcosa di non chiaro chiedi pure.


#5

Come ricordarmi le repo iniziate e mai finite :see_no_evil:

Btw, non fidatevi troppo di @lukecavabarrett, gli aa sono meglio dei treap se non serve split/merge


#6

Grazie mille @Borto, solo che in quanto a programmazione a oggetti (se così si può definire questa) sono completamente inesperto, l’ unico utilizzo che conoscevo delle struct era quello di semplici variabili composite(quello che significa la terza riga della struct per me è un mistero), mi puoi consigliare un buon sito con almeno il necessario per capire il codice che hai postato?


#7

In realtà non è neanche troppo a oggetti così come ha impostato il codice, in quanto le funzioni sono globali e prendono il nodo attualmente in esame come parametro.

Quali sono le parti che ti sembrano meno chiare?


#8

gli aa sono piĂą veloci da scrivere?


#9

nello specifico non ho capito :

e

che operatore è “->” ?


#10

Quello è il costruttore della struct node, che prende come argomento un valore di tipo T.
Dopo i : vengono specificati eventuali costruttori da invocare sui campi della struct.
In questo caso, viene inizializzata la proprietĂ  key a k, mentre i due puntatori left e right vengono iniziallizati a nullptr, in modo da indicare che di base un nodo del BST appena creato non ha figli.

Ha la stessa funzione del punto, però si utilizza sui puntatori di struct/class.
Per intederci, s->key ha un comportamento analogo a (*s).key