CAPITOLO 18

ESERCIZIO

Date le seguenti definizioniTYPE

nodoint=^tipointtipoint=RECORD

numero:integer;link:nodoint;END;

ListaInt:Nodoint;

Siano date 2 liste una Lint:ListaInt e una Lchar:ListaChar .Sia data la funzione trovato(Lchar,intero):chare la procedura sostituisci(intero,Lint,trovato)Scrivere un algoritmo che sostituisca ogni elemento della lista Lint con il codice ASCII del carattere trovato in Lchar nella posizione determinata dal valore dell’elemento in Lint.

EsempioInput: Lint: 5 4 3 Lchar: a f g h mOutputLint 109 104 103

Nota: La funzione Trovato restituisce il carattere ‘0’ nel caso in cui il valore intero supera la lunghezza di Lchar. Tale carattere può essere sostituito all’intero.

nodochar=^tipochartipochar=RECORD

carattere:char;link:nodochar;

END;

ListaChar:=Nodochar;

GLI ALBERI COME STRUTTURE DATI

Search Tree - (Albero di ricerca) - Memorizza informazioni in maniera tale che possano essere ritrovate molto velocemente e le operazioni di inserimento e cancellazione nodi sono molto efficienti.

ALBERI BINARI

• Un albero è binario se ogni nodo è al più collegato ad altri due

• Un albero binario è:

– L’albero vuoto

– oppure è costituito da una radice e da un sottoalbero sinistro ed un sottoalbero destro

• L’albero è dunque una struttura ricorsiva non lineare.

• I suoi elementi sono detti nodi

I due disegni rappresentano due alberi uguali ma due alberi binari diversi.

L’ovvio modo di rappresentare un albero consiste nell’assegnare ad ogni nodo due puntatori uno che punta al sottoalbero sinistro ed uno che punta al sottoalbero destro.

Per gestire gli alberi introduciamo un ADT costituito da nodi non più con uno ma con due campi per i puntatori. Attraverso questa struttura potremo rappresentare gli alberi di ricerca binari.

Albero Binario

Radice (root)

Sotto albero

Carlo

Maria

Peppe NicolaAnna

Emma

Giulio

CarlaGuido

Ugo

Angela

Definiamo sotto albero ogni nodo in cui almeno un puntatore non è uguale a NIL ma punta ad un altro nodo o sotto albero.

Definiamo radice di un sotto albero quel nodo che punta ad almeno un altro nodo (NB Negli alberi binari si può al massimo puntare a due nodi (destro e sinistro).

La variabile dinamica albero può essere definita attraverso la sua radice, il nodo a partire dal quale si possono raggiungere tutti gli altri nodi della struttura.

XXX

Tree

Left Structure Right Structure

Un albero (sotto albero), che punta a NIL e cioè non contiene nodi è detto albero (sotto albero) vuoto.

Albero Binario

Radice (root)

Sotto albero

Cammino(path)

X

Genitore

Figlio

Livello del nodo X = 3

Nodi fratelli

Altezza dell’albero= Massimo numero di livelliH=3

Foglie

Un albero binario è ordinato quando il campo chiave di ogni

nodo è minore del campo chiave di ogni nodo del suo

sottoalbero destro ed è maggiore del campo chiave di ogni

nodo del suo sottoalbero sinistro. Si parla in questo caso anche

di binary search tree (BST).

Sergio

Toni

Luigi UgoAnna

Dora

Giulio

RiccardoGuido

Maria

Roberto

Un albero binario di ricerca (BST) è tale se:- le foglie sinistre hanno un valore del campo chiave inferiore del nodo padre- le foglie destre hanno un valore del campo chiave maggiore del nodo padre

Campo chiaveKey FieldLeft Right

CONSTNullKey= ’un simbolo o valore per indicare NIL ' ;NullInfo=‘quando possibile assegna un significato al nodo NIL’TYPE

KItemType= STRING[20]InfoType= un data type per le informazioni non keyBSTP=^BSTNode {puntatore a un nodo}

BSTNode = RECORD Key:KItemType;

Info: InfoType; Left,

Right: BSTP END;

Left Key Info Right

TNode

Le operazioni che ci interessa definire sono:

•creazione di un nuovo nodo con un valore assegnato ai campi dati (Key e Info) e NIL

ai campi link (Left e Right)•dispose (dealloca) di un nodo supposto che esso esista come variabile dinamica

•selezionare un nodo data una chiave•selezionare le Info collegate al nodo

•seleziona il figlio a sinistra di un dato nodo•seleziona il figlio a destra di un dato nodo

Left Key Info Right

TNode

INTERFACE

PROCEDURE MakeTNode(KeyValue:KItemType; TheInfo:InfoType; VAR TNode:BSTP);{ Crea un nuovo nodo, assegnando a KeyValue e TheInfo un valore e il valore NIL per i campi Left e Right }

PROCEDURE KillTNode(VAR Node:LNodeP);{dispose la memoria allocata per il TNode e poi pone il TNode a NIL. }

PROCEDURE GetNodesKey(TNode:BSTP; VAR TheKey:KItemType);{ritorna il key field del nodo puntato da Tnode, se Tnode è NIL allora ritorna il valore di NullKey}

PROCEDURE GetNodesInfo(TNode:BSTP; VAR TheInfo:InfoType);{ritorna le informazioni del nodo puntato da Tnode, se Tnode è NIL allora ritorna il valore di NullInfo}

CONSTNullKey= ’un simbolo o valore per indicare NIL ' ;NullInfo=‘quando possibile assegna un significato al nodo NIL’TYPE

KItemType= STRING[20]InfoType= un data type per le informazioni non keyBSTP=^BSTNode {puntatore a un nodo}


Info: InfoType; Left, Right: BSTP END;

Left Key Info Right

TNode

FUNCTION NodesLeftTree(TNode:BSTP) : BSTP;{ritorna il puntatore al sotto albero sinistro di Tnode. Se T Node è NIL allora ritorna NIL }

CONSTNullKey= ’un simbolo o valore per indicare NIL ' ;NullInfo=‘quando possibile assegna un significato al nodo NIL’TYPEKItemType= STRING[20]InfoType= un data type per le informazioni non keyBSTP=^BSTNode {puntatore a un nodo}


Info: InfoType;Left, Right: BSTP END;

FUNCTION NodesRightTree(TNode:BSTP) : BSTP;{ritorna il puntatore al sotto albero destro di Tnode. Se T Node è NIL allora ritorna NIL }

Left Key Info Right

TNode

PROCEDURE MakeTNode(KeyValue:KItemType; TheInfo:InfoType; VAR TNode:BSTP);{ Crea un nuovo nodo, assegnando a KeyValue e TheInfo un valore e il valore NIL per i campi Left e Right }BEGIN

new(Tnode);WITH TNode^ DO BEGIN

Key:=KeyValue;Info:=TheInfo;Left:=NIL;Right:=NIL

ENDEND;




Left Key Info Right

TNode

PROCEDURE KillTNode(VAR Node:LNodeP);{dispose la memoria allocata per il TNode e poi pone il TNode a NIL. }BEGIN

IF Tnode <> NIL THEN BEGIN

dispose(TNode);Tnode:=NIL

ENDEND;




Left Key Info Right

TNode

PROCEDURE GetNodesKey(TNode:BSTP; VAR TheKey:KItemType);{ritorna il key field del nodo puntato da Tnode, se Tnode è NIL allora ritorna il valore di NullKey}BEGIN

IF TNode <> NIL THEN TheKey:= TNode ^.KeyELSE TheKey:= NullKey

END;




Left Key Info Right

TNode

PROCEDURE GetNodesInfo(TNode:BSTP; VAR TheInfo:InfoType);{ritorna le informazioni del nodo puntato da Tnode, se Tnode è NIL allora ritorna il valore di NullInfo}BEGIN

IF TNode <> NIL THEN TheInfo:= TNode ^.InfoELSE TheKey:= NullInfo

END;




Left Key Info Right

TNode

FUNCTION NodesLeftTree(TNode:BSTP) : BSTP;{ritorna il puntatore al sotto albero sinistro di Tnode. Se T Node è NIL allora ritorna NIL }BEGIN

IF Tnode <> NIL THEN NodesLeftTree:=Tnode^LeftELSE NodesLeftTree:=NIL

END:




Left Key Info Right

TNode

FUNCTION NodesRightTree(TNode:BSTP) : BSTP;{ritorna il puntatore al sotto albero destro di Tnode. Se T Node è NIL allora ritorna NIL }BEGIN

IF Tnode <> NIL THEN NodesRightTree:=Tnode^. RightELSE NodesRightTree:=NIL

END:




Left Key Info Right

TNode

Pseudo codice per un algoritmo generalizzato di selezione nodi

PROCEDURE GetNodeField(ANode:NodeP; VAR FieldVar: FieldType)

IF ANode <> NIL THENFieldVar ANode^.identificatore della variabile di campo selezionata

ELSE FieldVar NullValue

Ugo

ToniMaria

Anna

Dora

SergioGiulio

Guido

Luigi

Le stesse informazioni possono essere contenute in alberi binari di forma diversa.

Anna

Dora

Sergio

Giulio

Luigi

Guido

Riccardo

Maria

Riccardo

Toni

Ugo

Un albero si dice bilanciato se il livello di tutte le foglie è uguale all’altezza dell’albero o a questa stessa altezza meno 1.

H=3

L=3

Foglie

H=3

L=3

L=2

Foglie

H=5

L=3

L=2

L=4

L=5

In un albero bilanciato il tempo massimo di ricerca è di O(log2 (N))

dove N è il numero di nodi.

E’ evidente che un albero bilanciato si esplora per fare una ricerca in un numero di passi inferiore a quello necessario per esplorare un albero non bilanciato.

Se un albero bilanciato ha M livelli, il numero di nodi di cui è

formato può variare tra

2M e 2(M+1) -1.

0

1

M

ALBERO BILANCIATO CON 3 LIVELLI

N°NODI

M2

02

12

Totale Nodi

M

i

i

0

2 Totale Nodi

N°NODI

1M2

02

12

1

1

0

21M

i

i

ALBERO BILANCIATO CON 3 LIVELLI

Totale Nodi

N°NODI

1M2

02

12

1

1

0

21M

i

i

N°NODI

0

1

MM2

02

12

Totale Nodi

M

i

i

0

2

M

i

iM

i

i N0

1

0

221

x

xaax

MM

i

i

1

)1( 1

0

Serie geometrica

1a 2x

1221

)21(2 1

1

0

M

MM

i

i

12121 1 MM N

122 1 MM N

Supponiamo sia assegnata una lista di N oggetti tra i quali esiste una relazione d’ordine.Se riusciamo a inserire questi oggetti in un albero di ricerca bilanciato allora il numero di passi per trovare un qualunque oggetto è limitato da O(log2(N)).Se questo non avviene il caso peggiore in cui possiamo trovarci è pari a O(N).

Si può dimostrare che un albero di ricerca binario costruito in maniera casuale, quindi non necessariamente bilanciato, effettua in media un numero di passi per effettuare la ricerca pari a 1.39* O(log2(N)).

Toni

Maria

Ugo

Riccardo

Anna

Dora

Sergio

Giulio

Luigi

Guido

ESEMPIOSupponiamo di avere un albero di tipo BST, chiamiamo con Root il primo nodo.Scrivere una funzione LeftMost che fornisca il puntatore del nodo più a sinistra che si incontra a partire da Root.

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

Left Key Info Right

TNode




Left Key Info Right

TNode




FUNCTION LeftMost(Root: BSTP): BSTP;

VARNodoEsaminato:BSTP;

BEGINIF EmptyTree(Root) THEN NodoEsaminato = NIL;ELSE NodoEsaminato = Root;

WHILE NodesLeftTree(NodoEsaminato) <> NIL DO NodoEsaminato = NodesLeftTree(NodoEsaminato) ;

LeftMost: = NodoEsaminatoEND:

Definizione della funzione

Definizione delle variabili

Verifica se l’albero è vuoto

Cerca il nodo

OPERAZIONI SUI BST

Ogni nodo di un BST punta ad altri due nodi, ciascuno dei quali può essere visto come una variabile dinamica di tipo record.Quindi una variabile di tipo BSTType, cioè un puntatore alla radice di un BST, che è a sua volta una variabile BST, può essere passata da un blocco ad un altro. In altre parole dato un nodo di un BST, questo è radice per i suoi sottoalberi e i nodi a cui punta sono a loro volta radici di altri sottoalberi. Quindi possiamo adoperare ricorsivamente queste variabili.

Poiché una variabile BST può essere interpretata o come nodo di un BST o come un sotto albero di un BST, pur essendo variabili dello stesso tipo parleremo nel primo caso di un tipo BSTP (puntatore a un nodo) e nel secondo caso di un tipo BSTType (puntatore a un albero)




BSTType=BSTPVARNomeAlbero:BSTType

Left Key Info Right

TNode

INTERFACE

PROCEDURE MakeTree(VAR Tree: BSTType);{inizializza a NIL l’albero, creando un albero vuoto}

PROCEDURE AddTNode(KeyValue:KItemType; TheInfo:InfoType;VAR Tree: BSTType; VAR Done:boolean);

{aggiunge un nodo all’albero rispettando la struttura di un BST, se il KeyValue è già presente nell’albero non fa nulla e Done risulta False}

PROCEDURE DeleteTNode(KeyValue:KItemType;VAR Tree: BSTType; VAR Done:boolean);

{elimina il nodo con chiave KeyValue, se esso non esiste Done risulta False}

FUNCTION SearchTNode(Tree: BSTType; KeyValue:KItemType): BSTP;{cerca il nodo con chiave KeyValue, se esso non esiste ritorna NIL}

FUNCTION EmptyTree(Tree: BSTType): boolean;{ritorna vero se l’albero è vuoto}

ESEMPIO: COSTRUZIONE DI UN BST DI NOMI

Left Key Info Right

TNode

CONSTNullKey= ’ ' ;NullInfo=‘ ’TYPEKItemType= STRING[20]InfoType= STRING[20] BSTP=^BSTNode {puntatore a un nodo} BSTNode = RECORD {variabile dinamica per un nodo} Key:KItemType;

Info: InfoType;Left, {radice del sottoalbero di sinistra}

Right: BSTP {radice del sottoalbero di destra} END;

BSTType=BSTP; {definizione per la variabile albero} VAR

NameTree:BSTType;

COSTRUZIONE DI UN BST DI NOMI

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

MariaGiulioSergioDora GuidoRiccardoToniAnnaRobertoreturn

Supponiamo che vengano introdotti da tastiera i seguenti nomi:

Pseudo codice

MakeTree(NameTree)introduci NomeWHILE Nome <> NullKey DO

AddTNode(Nome, NullInfo, NameTree, Success)IF NOT Success THEN

segnala che il Nome esiste giàintroduci il nome

mostra il messaggio di fine lavoro

CONSTNullKey= ’ ' ;NullInfo=‘ ’TYPEKItemType= STRING[20]InfoType= STRING[20] BSTP=^BSTNode


Info: InfoType;Left,

Right: BSTP END;

BSTType=BSTP;VAR

NameTree:BSTTYpe;

PROCEDURE BuildNameTree(VAR NameTree: BSTType);{costruisce un albero a cui assegna un Nome dato in input}VAR

Nome:KItemType;Success: boolean;

BEGINMakeTree(NameTree);write(‘ Dammi un nome : ‘);readln(Nome);WHILE Nome <> NullKey DO BEGIN AddTNode(Nome, NullInfo, NameTree, Success); IF NOT Success THEN

writeln( Nome, ‘ esiste già’); write(‘ Dammi un nome : ‘); readln(Nome) END;

writeln(‘ L’albero è stato piantato’);END;

DEFINIZIONE DIATTRAVERSAMENTO DI UN BST

Visitare tutti i nodi di un BST di nomi, a partire dalla radice, e elencare i nomi in ordine alfabetico.

AnnaDoraGiulioGuidoMariaRiccardoRobertoSergioToni

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

MOSTRA IL CONTENUTO DI UN BST

Mostra le Chiavi (KeyItem) di tutti i nodi del sottoalbero sinistro di NameTree

Mostra la Chiave (KeyItem) della radice di NameTree

Mostra le Chiavi (KeyItem) di tutti i nodi del sottoalbero destro di NameTree

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

ShowTree(NodesLeftTree(NameTree));

GetNodesKey(NameTree, Nome);

Writeln(Nome)

ShowTree(NodesRightTree(NameTree));

Pseudo codice

La procedura ShowTree(NameTree) è una procedura ricorsiva il cui case base è rappresentato dall’albero vuoto (EmptyTree). In altre parole il processo di pop inizia non appena l’argomento di ShowTree(NameTree) è un albero vuoto.

PROCEDURE ShowTree(NameTree: BSTType);VAR

NodesKey: KItemType;BEGIN

IF NOT EmptyTree(NameTree) THEN BEGIN

ShowTree(NodesLeftTree(NameTree));

GetNodesKey(NameTree, Nome);

writeln(Nome)

ShowTree(NodesRightTree(NameTree));

END

END;

IMPLEMENTATION

PROCEDURE MakeTree(VAR Tree: BSTType);{inizializza a NIL l’albero, creando un albero vuoto}BEGIN

Tree:=NILEND;

FUNCTION EmptyTree(Tree: BSTType): boolean;{ritorna vero se l’albero è vuoto} BEGIN

EmptyTree:=Tree=NILEND;

RICERCA DI UN DATO SU UN BST

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

Riccardo ?????????

FUNCTION Binary (VAR Studenti: StudenteRecord; MatrCercata:StringaNome; Lo, Hi :integer) :integer

VARMid:integer;

BEGINIF Lo>Hi THEN Binary := 0ELSE BEGIN Mid (Lo+Hi) DIV 2 IF Studenti[Mid].Matr=MatrCercata THEN

Binary := Mid ELSE

IF Studenti[Mid].Matr<MatrCercata THEN Binary := Binary(Studenti, MatrCercata, Mid+1, Hi)ELSE Binary := Binary(Studenti, MatrCercata, Lo, Mid-1)

END;END;

CASE BASE 2

ESPRESSIONE RICORSIVA

CASE BASE 1

Pseudo codice

FUNCTION SearchTNode(Tree; KeyValue); BSTPIF EmptyTree(Tree) THEN SearchTNode NILELSE GetNodesKey(Tree, TheKey) IF TheKey = KeyValue THEN

SearchTNode Tree ELSE

IF KeyValue < TheKey SearchTNode SearchTNode(NodesLeftTree(Tree), KeyValue)

ELSE SearchTNode SearchTNode(NodesRightTree(Tree), KeyValue)

FUNCTION SearchTNode(Tree: BSTType; KeyValue:KItemType): BSTP;{cerca il nodo con chiave KeyValue, se esso non esiste ritorna NIL}VAR

TheKey: KItemType;BEGIN

IF EmptyTree(Tree) THEN SearchTNode NILELSE BEGIN GetNodesKey(Tree, TheKey) IF TheKey = KeyValue THEN

SearchTNode Tree ELSE

IF KeyValue < TheKey SearchTNode SearchTNode(NodesLeftTree(Tree), KeyValue)

ELSE SearchTNode SearchTNode(NodesRightTree(Tree), KeyValue)

ENDEND;

ESERCIZIO

Sia assegnato un albero binario. scrivere un algoritmo tale che sposti ogni figlio sinistro nel corrispondente figlio destro e viceversa.

A

B C

D E F

G H

A

C B

DF E

H G

AGGIUNTA DI UN DATO SU UN BST

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

Rolando

Per aggiungere un nodo a un BST è necessario innanzitutto verificare che l’Item non esiste già, perché in tal caso il nodo non viene aggiunto. Se non esiste bisogna trovare la sua corretta posizione nell’albero, cioè il suo genitore e attribuirgli come figli, sinistro e destro il puntatore NIL.

PROCEDURE AddTNode(KeyValue:KItemType; TheInfo:InfoType;VAR Tree: BSTType; VAR Done:boolean);

{aggiunge una foglia all’albero rispettando la struttura di un BST, se il KeyValue è già presente nell’albero non fa nulla e Done risulta False}


{elimina il nodo con chiave KeyValue ricostruendo la struttura BST. Se il Nodo non esiste Done risulta False}

Pseudo Codice di AddTNode

Search(Tree, KeyValue, TNode, Parent)

IF NOT EmptyTree(TNode) THENDone FALSE

ELSEcrea e aggiungi un nuovo nodo come figlio del nodo ParentDone TRUE

Se il nodo che vogliamo inserire, avente un certo KeyValue, esiste, allora Tnode non è vuoto e quindi non lo aggiungiamo altrimenti lo aggiungiamo

PROCEDURE AddTNode(KeyValue:KItemType; TheInfo:InfoType;VAR Tree: BSTType; VAR Done: boolean);

VARTnode, Parent : BSTP; {deve valere NIL se il nodo esiste già}ParentsKey: KeyItemType; {genitore del nodo da aggiungere}

BEGINSearch(Tree, KeyValue, TNode, Parent)IF NOT EmptyTree(TNode) THEN {il nodo esiste già}

Done := FALSEELSE {crea e aggiungi un nuovo nodo come figlio del nodo Parent}

BEGIN IF EmptyTree(Parent) THEN {il nuovo nodo sarà la radice}

MakeTNode(KeyValue, TheInfo, Tree) ELSE

BEGIN GetNodesKey(Parent, ParentsKey); IF ParentsKey > KeyValue THEN {il nuovo nodo va a sinistra}

MakeTNode(KeyValue, TheInfo, Parent^.Left) ELSE {il nuovo nodo va a destra}

MakeTNode(KeyValue, TheInfo, Parent^.Right) END;Done := TRUEEND

END; PROCEDURE MakeTNode(KeyValue:KItemType; TheInfo:InfoType; VAR TNode:BSTP);{ Crea un nuovo nodo, assegnando a KeyValue e TheInfo un valore e il valore NIL per i campi Left e Right }

SearchSearch(Tree, KeyValue, TNode, Parent)

Obiettivo: cercare un cammino verso un determinato nodo dell’albero.Se il nodo non esiste ritorna NIL. Se esiste ritorna il puntatore al nodo individuato.

Pseudo Codice

Parent NIL {la root non ha genitori}

TNode Tree {la radice è il primo nodo esaminato}

GetNodesKey(TNode, NodesKey) {estrai la chiave del nodo in esame}

WHILE ci sono altri nodi da esaminare AND non si è ancora trovato il nodo DO

Parent TNode

Tnode il sottoalbero legato al KeyValue


EmptyTree(TNode) NodesKey <> KeyValue

IF NodesKey > KeyValue THEN TNode radice del sottoalbero sinistroELSE TNode radice del sottoalbero destro

Il padre dell’ultimo nodo esaminatodurante la ricerca di KeyValue

19

13 21

12 15

14 18

16 17

20 24

23 26

Aggiungi 18 Tnode NIL

Pseudo Codice

Parent NIL {la root non ha genitori}

TNode Tree {la radice è il primo nodo esaminato}


WHILE ci sono altri nodi da esaminare AND non si è ancora trovato il nodo DO

Parent TNode

Tnode il sottoalbero legato al KeyValue


Aggiungi 22

22

Tnode = NIL

BEGINSearch(Tree, KeyValue, TNode, Parent)IF NOT EmptyTree(TNode) THEN {il nodo esiste già}

Done := FALSEELSE {crea e aggiungi un nuovo nodo come figlio del nodo Parent} BEGIN IF EmptyTree(Parent) THEN MakeTNode(KeyValue, TheInfo, Tree) {il nuovo nodo sarà la radice} ELSE

BEGINGetNodesKey(Parent, ParentsKey);IF ParentsKey > KeyValue THEN {il nuovo nodo va a sinistra}

MakeTNode(KeyValue, TheInfo, Parent^.Left)ELSE {il nuovo nodo va a destra}

MakeTNode(KeyValue, TheInfo, Parent^.Right) END;Done := TRUEEND

END;

AddTNode

Search

PROCEDURE Search(Tree: BSTT, KeyValue: KItemType, VAR TNode, Parent: BSTP);

VAR

NodesKey: KItemType;

BEGIN

Parent:= NIL {la root non ha genitori}

Tnode:= Tree {la radice è il primo nodo esaminato}

GetNodesKey(TNode, NodesKey) {estrai la chiave del primo nodo}

WHILE NOT EmptyTree(TNode) AND (NodesKey <> KeyValue) DO

BEGIN

Parent:= Tnode

IF NodesKey > KeyValue THEN Tnode:= NodesLeftTree(TNode)

ELSE Tnode:= NodesRightTree(TNode)


END

END;

Ricordarsi che GetNodesKey nel caso trovi NIL ritorna NullKey

ProblemaRealizzare una procedura che elimina il nodo con chiave KeyValue

Pseudo CodiceSearch(Tree, KeyValue, Candidate, Parent)GetNodesKey(Candidate, CandsKey)IF CandsKey <> KeyValue THEN

Done FALSEELSE

riorganizza l’albero dopo aver rimosso CandidateKillTNode(Candidate)Done TRUE

Ritorna la chiave CandsKey puntata da Candidate

Implica che se cerco di nuovo un nodo con chiave CandsKey non lo trovo e che l’albero che resta, deallocando il nodo Candidate, è ancora un BST

Analizziamo il problema della riorganizzazione dell’albero una volta eliminato un nodo.

Caso a- il nodo da eliminare ha il sotto albero sinistro vuoto.

QQQ

RRR

Parent

Candidate

left right

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

Caso b- il nodo da eliminare ha il sotto albero destro vuoto.La procedura è analoga alla precedente.

Pseudo Codice

IF EmptyTree(NodesLeftTree(Candidate)) THENLinkParent(Candidate, NodesRightTree(Candidate), Parent, Tree)

ELSEIF EmptyRight(NodesRightTree(Candidate)) THEN LinkParent(Candidate, NodesLeftTree(Candidate), Parent, Tree)ELSE continua a riorganizzare l’albero

PROCEDURE LinkParent (OldChild, NewChild, Parent: BSTP;VAR Tree: BSTType);{riorganizza l’albero BST dopo l’eliminazione di un nodo}

QQQ

RRR

Parent

Candidate

left right

Search(Tree, KeyValue, TNode, Parent)

Se la procedura Search restituisce come valore di Parent NIL allora questo significa che è la root di Tree che deve essere cancellata e quindi Tree deve assumere il valore di NewChild. Se non è così allora il sotto albero di Parent, che abbiamo chiamato OldChild deve ora assumere il valore di NewChild.

IF Parent = NIL THENTree NewChild

ELSEIF OldChild = NodesLeftTree(Parent) THEN

Parent^.Left NewChildELSE

Parent^Right NewChild

Riassunto dei tipi di cancellazione

New

Old

Parent

Old

New


{elimina il nodo con chiave KeyValue ricostruendo la struttura BST. Se il Nodo non esiste Done risulta False}

Nel caso in cui il Nodo da cancellare ha sia il sotto albero di sinistra che quello di destra allora si procede come segue:si sostituisce al nodo da cancellare o il nodo di valore maggiore del suo sottoalbero di sinistra o quello di valore minore del suo sotto albero di destra. Se questo nodo ha a sua volta un sottoalbero di destra e uno di sinistra ci si comporta nei suoi confronti come se fosse un nodo da cancellare e quindi si esegue la stessa procedura sopra descritta.

Nodo da cancellare

30

5

3

40

35

80

38

8

35

5

3

40

35

80

38

8

Pseudo Codice

OldCandidate Candidate

Search(NodesRightTree(OldCandidate), KeyValue, Dummy, Candidate)

OldCandidate^.Info Candidate^.Info

OldCandidate^.Key Candidate^.Key

GetNodesKey(Candidate, CandsKey)

Search(NodesRightTree(OldCandidate), CandsKey, Dummy, Parent)

IF Parent = NIL THEN

LinkParent(Candidate,NodesRightTree(Candidate), OldCandidate, Tree)

ELSE

LinkParent(Candidate,NodesRightTree(Candidate), Parent, Tree)

Restituisce il nodo del sottoalbero destro con la chiave più piccola

Restituisce il nodo genitore di Candidate

PROCEDURE LinkParent(OldChild, NewChild, Parent: BSTP; VAR Tree:BSTType);{collega il nodo genitore con il sottoalbero connesso al nodo da cancellare}BEGIN

IF Parent=NIL THEN {sostituiamo la root} Tree:= NewChildELSE IF OldChild = NodesLeftTree(Parent) THEN

Parent^.Left:=NewChild {sostituiamo al genitore il figlio sinistro} ELSE

Parent^.Right:=NewChild {sostituiamo al genitore il figlio destro}END;

PROCEDURE GetNewCandidate(KeyValue: KItemType; VAR Candidate:BSTP; VAR Tree:BSTType);

VARDummy, {variabile ausiliare per la chiamata alla Search}Parent, OldCandidate :BSTP;CandsKey: KItemType:

BEGIN

OldCandidate := Candidate


OldCandidate^Info := Candidate^Info ;

OldCandidate^Key := Candidate^Key;

GetNodesKey(Candidate, CandsKey);

Search(NodesRightTree(OldCandidate), CandsKey, Dummy, Parent);

IF Parent= NIL THEN


ELSE

LinkParent(Candidate,NodesRightTree(Candidate), Parent, Tree)

END;

PROCEDURE DeleteTNode(KeyValue: KItemType; VAR Tree:BSTType; VAR Done:boolean);VAR

Candidate, {puntatore al nodo candidato per la cancellatura}Parent, {puntatore al genitore del nodo candidato}OldCandidate :BSTP;CandsKey: KItemType:

BEGIN

Search(Tree, KeyValue, Candidate, Parent)


IF CandsKey<> KeyValue THEN

Done:=FALSE

ELSE

IF EmptyTree(NodesLeftTree(Candidate)) THEN LinkParent(Candidate, NodesRightTree(Candidate), Parent, Tree)

ELSE IF EmptyRight(NodesRightTree(Candidate)) THEN LinkParent(Candidate, NodesLeftTree(Candidate), Parent, Tree) ELSE GetNewCandidate(KeyValue, Candidate, Tree);KillTNode(Candidate);Done:= TRUEEND

END;

90

50 95

30

34

40

3617

93 98

10015

13

35

47

Search(Tree, KeyValue, Candidate, Parent)


IF CandsKey<> KeyValue THEN Done:=FALSE

ELSE

IF EmptyTree(NodesLeftTree(Candidate)) THEN LinkParent(Candidate, NodesRightTree(Candidate), Parent, Tree) ELSE IF EmptyRight(NodesRightTree(Candidate)) THEN LinkParent(Candidate, NodesLeftTree(Candidate), Parent, Tree) ELSE GetNewCandidate(KeyValue, Candidate, Tree);KillTNode(Candidate);Done:= TRUE

Cancellare il nodo 30

OldCandidate := Candidate


OldCandidate^.Info := Candidate^.Info ;

OldCandidate^.Key := Candidate^.Key;


Search(NodesRightTree(OldCandidate), CandsKey, Dummy, Parent);

IF Parent = NIL THEN


ELSE

LinkParent(Candidate,NodesRightTree(Candidate), Parent, Tree)END;

P30

P40 30 P34

34

34

P34 34 P363834

P34 P35 P36

ALGORITMI DI ATTRAVERSAMENTO DI BSTAlgoritmi di attraversamento di un albero:

LNR - (LeftNodeRight) - Attraversamento inorder Per ogni nodo1 - Visita il sottoalbero sinistro 2 - Visita il nodo root3 - Visita il sottoalbero destro

NLR - (NodeLeftRight) - Attraversamento pre-order Per ogni nodo1 - Visita il nodo root2 - Visita il sottoalbero sinistro 3 - Visita il sottoalbero destro

LRN - (LeftRightNode) - Attraversamento post-order Per ogni nodo1 - Visita il sottoalbero sinistro 2 - Visita il sottoalbero destro3 - Visita il nodo root

LNR - (LeftNodeRight) - Attraversamento ordinato Per ogni nodo1 - Visita il sottoalbero sinistro 2 - Visita il nodo3 - Visita il sottoalbero destro

PROCEDURE Traverse(Root)IF root <> NIL THEN

Traverse(Root^.Left) {visita tutti i nodi del sottoalbero sinistro}Visit(Root) Traverse(Root^.Right) {visita tutti i nodi del sottoalbero destro}


Visit(Root)Traverse(Root^.Left) {visita tutti i nodi del sottoalbero sinistro}Traverse(Root^.Right) {visita tutti i nodi del sottoalbero destro}

NLR - (NodeLeftRight) - Attraversamento pre-ordinato Per ogni nodo1 - Visita il nodo root2 - Visita il sottoalbero sinistro 3 - Visita il sottoalbero destro


Traverse(Root^.Left) {visita tutti i nodi del sottoalbero sinistro}Traverse(Root^.Right) {visita tutti i nodi del sottoalbero destro}Visit(Root)

LRN - (LeftRightNode) - Attraversamento post-ordinato Per ogni nodo1 - Visita il sottoalbero sinistro 2 - Visita il sottoalbero destro3 - Visita il nodo root

ProblemaEliminare un BST senza lasciare spazzatura.

SoluzioneAttraversa l’albero con un algoritmo LRN (post-order) e cancella ogni nodo incontrato. E’ utilizzato l’LRN perché la root è sempre l’ultima ad essere deallocata dopo aver deallocato i nodi figli, e quindi nessun link è eliminato prima del dovuto.

PROCEDURE KillTree(VAR Tree:BSTType);BEGIN

IF NOT EmptyTree(Tree) THEN BEGIN

KillTree(NodesLeftTree(Tree);KillTree(NodesRightTree(Tree);KillTNode(Tree)

ENDEND; Sergio

Toni

Anna

Dora

Giulio

RiccardoGuido

Maria

Roberto

ProblemaEspressioni aritmetiche.

Notazione Polacca Inversa 5 3 * 4 1 - /

Visita LRNpost-order

Notazione Polacca Diretta/ * 5 3 - 4 1

Visita NLRpre-order

/

*

5 3

-

4 1

Notazione infissa(5*3)/(4-1)

Visita LNRinorder

/

*

5 3

-

4 1

/

*

5 3

-

4 1

*

/

-

5 3 4 1

ProblemaAssegnata una espressione in notazione polacca diretta scrivere una procedura che costruisca l’albero BST di figura.I dati vengono inseriti uno di seguito all’altro e l’elaborazione parte quando digitiamo <eoln>Utilizzare un algoritmo del tipo post-order (LRN).

(5*3)/(4-1).Albero di computazione

PROGRAM EvaluateTree(input, output);TYPE

NoteP=^ExpressionNode; ExpressionNode = RECORD Token: char; {un operatore o un carattere tra ‘0’..’9’} Operand1; {puntatore alla espressione a sinistra} Operand2; {puntatore alla espressione a destro}

NodePEND;

VAREtree: NodeP;

PROCEDURE MakeTree(ETree:NodeP);{costruisce un albero a partire dalla espressione di input in forma PN secondo la strategia NLR}BEGIN ….. END;

FUNCTION TreesValue(ETree: NodeP):integer;{ritorna il valore dell’espressione rappresentata dall’albero ETree secondo la strategia LRN}BEGIN ….. END;{ -------------------- BODY ----------------------- }BEGIN

new(ETree);MakeTree(ETree);readln;write(‘Il valore dell’espressione è ‘);writeln(TresValue(ETree):1)

END.

Allochiamo spazio per l’albero

Variabile passata per valore così che all’uscita puntiamo di nuovo alla root

Pseudo codice di MakeTree

SkipBlancks(Ch) {salta i blank e ritorna invece blank quando incontra <eoln >}IF Ch<> ‘ ‘ THEN

WITH ETree^ DO Token Ch IF Token è un operatore THEN

costruisci il sotto albero sinistrocostruisci il sotto albero destro

Si può facilmente realizzare con ricerca di appartenenza a un dato insieme

Si costruiscono mediante chiamate ricorsive alla procedura MakeTree

PROCEDURE SkipBlanks(VAR Ch:char);{salta i blank e ritorna invece blanck quando incontra EOLN}BEGIN

Ch:= ‘ ‘;WHILE NOT eoln AND (Ch=‘ ‘) DO read(Ch)

END;PROCEDURE MakeTree(ETree: NodeP); {costruzione dell’albero dell’espressione}VAR

Ch: char;BEGIN

SkipBlancks(Ch);IF Ch <> ‘ ‘ THEN WITH ETree^ DO BEGIN

Token:=Ch; IF Token IN [‘*’,’/’,’\’,’+’,’-’] THEN BEGIN

new(Operand1);MakeTree(Operand1);new(Operand2);MakeTree(Operand2);

END END

END;

Carattere candidato come token

Assegna a token la root attuale

Verifica che il token sia un operatore

Crea l’albero sinistro

Crea l’albero destro

Pseudo codice per ExpressionValue{dato un operatore si cercano gli operandi nei sotto-alberi sinistro e destro; quindi si applical’operazione indicata nel nodo radice. In questo caso applichiamo una strategia LRN. La procedura è ricorsiva e il case base si ha quando il nodo a cui siamo giunti rappresenta un singolo operando. Per sapere questo facciamo una chiamata alla funzione NumericValue}

WITH ETree^ DOIF Token rappresenta un letterale intero THEN TreeValues NumericValue(Token)ELSE LeftOperand TreesValue(Operand1) RightOperand TreesValue(Operand2) TreesValue ExpressionValue(LeftOperand,RightOperand, Token))

FUNCTION ExpressionValue(Operand1, Operand2:integer; Operator:char): integer;BEGIN

CASE Operator OF‘*’: ExpressionValue:=Operand1*Operand2;‘/’: ExpressionValue:=Operand1 DIV Operand2;‘\’: ExpressionValue:=Operand1 MOD Operand2;‘+’: ExpressionValue:=Operand1 + Operand2;‘-’: ExpressionValue:=Operand1 - Operand2

ENDEND;

FUNCTION NumericValue(Ch:char):integer;BEGIN

NumericValue:= ord(Ch) - ord(‘0’)END;

FUNCTION TreesValue(ETree:NodeP): integer;VAR

LeftOperand,RightOperand: integer;

BEGINWITH ETree^ DO IF Token IN [‘0’..’9’] THEN

TreesValue:=NumericValue(Token); ELSE BEGIN

LeftOperand:=TreeValue(Operand1);RightOperand:=TreeValue(Operand2);TreesValue:= ExpressionValue(LeftOperand,RightOperand, Token)

ENDEND;

CAPITOLO 18

Documents

Transcript of CAPITOLO 18