Puntatori, alberi e ricorsività

Rieccomi dopo tanto. Questo è il primo articolo di una piccola serie… facciamo miniserie di 3 o forse 4 puntate veloci.
Qualche tempo fa ho fatto un colloquio per una ditta all’estero, il colloquio prevedeva anche un test pratico. 40 minuti di tempo per creare in Delphi un albero, popolarlo e stamparne gli elementi.
L’albero conteneva numeri, a partire dalla radice i numeri minori del nodo corrente venivano memorizzati nel ramo a sinistra, quelli maggiori del nodo corrente invece nel ramo di destra. La lettura ovviamente doveva restituire gli elementi in maniera ordinata.
Facendo un esempio pratico, dovendo inserire i numeri 10 – 6 – 4 – 3 – 8 -12 avremo avuto un albero come questo:

Insomma 🙂 il calssico esercizio di teoria sugli alberi, dov’era l’inghippo? Si avevano a disposizione solo 40 minuti! E il tempo vola.

Devo ammettere che il test era proprio ben fatto. Dopo averlo superato ho pensato che in realtà fosse troppo facile, ma non lo era affatto. Per poterlo passare o si conosceva la teoria o non si sarebbe potuto trovare nulla su google da copiare ed incollare. Gli elementi da inserire erano:

– Puntatori
– Gli alberi
– La ricorsione

I puntatori non sono così usati in Delphi e non ho mai capito bene perché sono indicanti da molti sviluppatori come il male di ogni software. Agli albori di Java una delle frasi che mi aveva divertito di più era:
“La gestione della memoria è troppo importante per lasciarla agli sviluppatori. La gestione della memoria è troppo importante per lasciarla al software”.
Chissà chi aveva ragione…

Sugli alberi dipende molto da che software sviluppate, io non li ho più usati dai tempi della scuola… troppo software gestionale 🙂 con le sue query SQL.
Riguardo la ricorsione… siamo quasi come i puntatori; un altro di quegli argomenti amati e odiati, la ricorsione (qui il link a wikipedia) risolve semplicemente alcune tipologie di problemi ma al tempo stesso non è performante.

Tornando a noi, il programmino finale è quello nella figura di seguito:

Ok è esteticamente bruttino, ma abbiate pietà, comprensione, umanità un principio di cataratta 🙂 … fare le cornicette di notte non mi entusiasma 🙂 Il suo funzionamento è semplice. Si aggiungono gli elementi alla TListBox premendo il bottone “Add Element” che sposta l’elemento dalla TEdit “value” alla lista, una volta che abbiamo popolato a dovere quest’ultima il bottone “Create tree” genererà l’albero.
Il bottone “Sorted elements” scriverà gli elementi dal più piccolo al più grande 🙂 nel componente TEdit a fianco del bottone.

L’implementazione della classe StandardTreeGest prevederà le funzioni pubbliche:

public
  function AddElement(ext_iValue: integer): pElement;
  function SortAscending: string;

Per aggiungere un elemento e per estrarre la lista degli elementi inseriti in maniera ordinata. Queste 2 funzioni saranno le “interfacce” pubbliche delle seguenti funzioni private:

function InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
function ReadFromMinimum(pCurrElem: pElement): string;

Che opereranno realmente sull’albero. Andando ad evidenziare i punti problematici elencati prima (puntatori, alberi e ricorsione) vediamo che ogni nodo di un albero è formato da 2 puntatori ad altri nodi (uno al ramo sinistro e uno al destro) e dal valore del nodo stesso. Questo in Delphi si dichiara così:

type
  pElement = ^Element;

  Element = record
    iValue: integer;
    pLeftElement, pRightElement: pElement;
  end;

Abbiamo quindi le funzioni pubbliche per l’accesso all’albero che richiameranno quelle private che saranno anche quelle ricorsive.

function StandardTreeGest.AddElement(ext_iValue: integer): pElement;
var
  pAddedElement: pElement;

begin
  if pRoot = nil then
  begin
    pRoot := CreateNewElem(ext_iValue);
    pAddedElement := pRoot;
  end
  else
    pAddedElement := InsertOrdered(ext_iValue, pRoot);

  result := pAddedElement;
end;

function StandardTreeGest.SortAscending: string;
var
  sNode: string;

begin
  sNode := ReadFromMinimum(pRoot);
  if (sNode <> '') then
    result := Copy(sNode, 3, length(sNode) - 2)
  else
    result := '';
end;

Come vedete fanno ben poche cose principalmente legate al controllo del nodo radice dell’albero. Il lavoro vero lo fanno le funzioni private:

function CreateNewElem(ext_iValue: integer): pElement;
function InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
function ReadFromMinimum(pCurrElem: pElement): string;

Con il loro codice sorgente:

function StandardTreeGest.CreateNewElem(ext_iValue: integer): pElement;
var
  pNewElement: pElement;
begin
  new(pNewElement);
  pNewElement.iValue := ext_iValue;
  pNewElement.pLeftElement := nil;
  pNewElement.pRightElement := nil;

  result := pNewElement;
end;

function StandardTreeGest.InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
var
  pResultElem: pElement;

begin
  if (pCurrElem = nil) then
  begin
    pResultElem := CreateNewElem(ext_iValue);
    pCurrElem := pResultElem;
  end
  else
    if (ext_iValue < pCurrElem.iValue) then
      pResultElem := InsertOrdered(ext_iValue, pCurrElem.pLeftElement)
    else
      pResultElem := InsertOrdered(ext_iValue, pCurrElem.pRightElement);

  result := pResultElem;
end;

function StandardTreeGest.ReadFromMinimum(pCurrElem: pElement): string;
var
  sOrderedTree: string;

begin
  if pCurrElem <> nil then
  begin
    sOrderedTree := ReadFromMinimum(pCurrElem.pLeftElement) + ' - ' + IntToStr(pCurrElem.iValue);
    sOrderedTree := sOrderedTree + ReadFromMinimum(pCurrElem.pRightElement);
  end
  else
    sOrderedTree := '';

  result := sOrderedTree;
end;

A parte la CreateNewElem le altre funzioni sono ricorsive cioè richiamano se stesse dal loro interno, questo permette ad esempio alla ReadFromMinimum di leggere tutti i nodi a sinistra e una volta arrivato all’ultimo elemento di “riavvolgersi” su se stessa e passare alla lettura del ramo destro del nodo corrente. Tutto questo perché le chiamate a funzione e le variabili locali in esse contenute vengono memorizzate sullo stack. Da qui la lentezza e la grande occupazione di memoria delle funzioni ricorsive a cui si contrappone la drammatica semplicità del codice scritto.

Volevo richiamare la vostra attenzione sulla creazione di un nuovo record nella funzione CreateNewElem

  new(pNewElement);

avete visto l’istruzione new… mica vorrete lasciarla senza la sua dispose!!! 🙂 I puntatori fanno casini quando ci dimentichiamo di deallocarli o magari li usiamo senza allocarli, ma non sono così cattivi in fondo.
La funzione di “ripulitura” è la DeleteAll richiamata anche da dentro il distruttore della classe StandardTreeGest. Il codice completo di quest’ultima è il seguente:

unit TreeGest;

interface

type
  pElement = ^Element;

  Element = record
    iValue: integer;
    pLeftElement, pRightElement: pElement;
  end;

  StandardTreeGest = class
    private
      pRoot: pElement;

      function CreateNewElem(ext_iValue: integer): pElement;
      function InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
      function ReadFromMinimum(pCurrElem: pElement): string;

      procedure DeleteAll_From(pCurrElem: pElement);

    public
      function AddElement(ext_iValue: integer): pElement;
      function SortAscending: string;

      procedure DeleteAll;

      constructor Create; virtual;
      destructor Destroy; override;

  end;

implementation

{ StandardTreeGest }

uses
  System.SysUtils;

constructor StandardTreeGest.Create;
begin
  pRoot := nil;
end;

destructor StandardTreeGest.Destroy;
begin
  if assigned(pRoot) then
    DeleteAll;
end;

procedure StandardTreeGest.DeleteAll;
begin
  DeleteAll_From(pRoot);
  pRoot := nil;
end;

procedure StandardTreeGest.DeleteAll_From(pCurrElem: pElement);
begin
  if pCurrElem <> nil then
  begin
    DeleteAll_From(pCurrElem.pLeftElement);
    DeleteAll_From(pCurrElem.pRightElement);
    Dispose(pCurrElem);
  end
end;

function StandardTreeGest.AddElement(ext_iValue: integer): pElement;
var
  pAddedElement: pElement;

begin
  if pRoot = nil then
  begin
    pRoot := CreateNewElem(ext_iValue);
    pAddedElement := pRoot;
  end
  else
    pAddedElement := InsertSorted(ext_iValue, pRoot);

  result := pAddedElement;
end;

function StandardTreeGest.CreateNewElem(ext_iValue: integer): pElement;
var
  pNewElement: pElement;
begin
  new(pNewElement);
  pNewElement.iValue := ext_iValue;
  pNewElement.pLeftElement := nil;
  pNewElement.pRightElement := nil;

  result := pNewElement;
end;

function StandardTreeGest.InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
var
  pResultElem: pElement;

begin
  if (pCurrElem = nil) then
  begin
    pResultElem := CreateNewElem(ext_iValue);
    pCurrElem := pResultElem;
  end
  else
    if (ext_iValue < pCurrElem.iValue) then
      pResultElem := InsertSorted(ext_iValue, pCurrElem.pLeftElement)
    else
      pResultElem := InsertSorted(ext_iValue, pCurrElem.pRightElement);

  result := pResultElem;
end;

function StandardTreeGest.SortAscending: string;
var
  sNode: string;

begin
  sNode := ReadFromMinimum(pRoot);
  if (sNode <> '') then
    result := Copy(sNode, 3, length(sNode) - 2)
  else
    result := '';
end;

function StandardTreeGest.ReadFromMinimum(pCurrElem: pElement): string;
var
  sOrderedTree: string;

begin
  if pCurrElem <> nil then
  begin
    sOrderedTree := ReadFromMinimum(pCurrElem.pLeftElement) + ' - ' + IntToStr(pCurrElem.iValue);
    sOrderedTree := sOrderedTree + ReadFromMinimum(pCurrElem.pRightElement);
  end
  else
    sOrderedTree := '';

  result := sOrderedTree;
end;

end.

Il sorgente di tutto il programma lo trovate qui

Come potete vedere ho creato il costruttore e il distruttore… ho fatto lo stesso anche con la form del main, so che con le form avrei potuto usare l’evento oncreate per fare le mie inizializzazioni ma sono un po “stagionato” 🙂

Concludo questo primo articolo dicendo che le poche righe scritte non sono certo esaustive, gli alberi sono materia complessa se non di più, ma la mia idea è di buttare una pietra nell’acqua e far muovere un po’ le cose. Spiegare quello che so e anche imparare per cui se avete commenti, suggerimenti o correzioni non esitate a scrivere 🙂