Alberi binari di ricerca
Indice
๐ Definizione
Un albero binario di ricerca รจ un albero binario nel quale ogni nodo rispetta una specifica proprietร di ordinamento:
figli nel sottoalbero sinistro <= nodo < figli nel sottoalbero destro. Questo deve essere vero per ogni nodo.
โ Operazioni
๐ Ricerca
Permette di ricercare un determinato valore all'interno dell'albero.
Restituisce
- il nodo dellโalbero
che contiene la chiave , se presente - NULL, se non presente
L'idea รจ la seguente:
- Iniziamo dalla radice.ย
- Compariamo l'elemento cercato con la radice: se minore, visitiamo il sottoalbero sinistro, altrimenti visitiamo il sottoalbero destro.ย
- Se troviamo l'elemento cercato restituiamo vero (oppure il nodo), altrimenti restituiamo falso (o NULL).
Implementazione ricorsiva
Tree search(Tree root, Item key) {
if(root == NULL || root.key == key)
return root;
else if(key < root.key)
return search(root.left, key);
else
return search(root.right, key);
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
(Worst case Space Complexity :)
Se l'albero non รจ bilanciato, nel caso peggiore รจ praticamente una lista, per questo esce
Implementazione iterativa
Tree search(Tree root, Item key) {
Tree current = root;
while(current != NULL && current.key != key) {
if(key < root.key)
current = current.left;
else
current = current.right;
}
return current;
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
โ Inserimento
Permette di inserire un nuovo nodo all'interno dell'albero binario di ricerca.
L'idea รจ la stessa della ricerca, cerchiamo quindi la chiave del nodo da aggiungere dalla radice fino in fondo all'albero, ossia quando arriveremo ad un nodo nullo. Lรฌ inseriremo il nostro nodo. Il problema รจ solo fare new node dentro un nodo nullo. Per questo ci terremo un puntatore al nodo visitato precedentemente, cosรฌ da fare prev->left (o prev->right) = new node.
Nell'implementazione sotto assumiamo che ogni nodo abbia il riferimento ai due figli. Se ogni nodo avesse anche un riferimento al padre, una volta inserito il nodo dovremmo anche fargli puntatore il padre.
Implementazione iterativa
Tree insert(Tree root, Item key) {
Tree newNode = new Tree(key);
if(root == NULL) {
root = newNode;
return newNode;
}
Tree current = root;
Tree prev = NULL;
while(current != NULL) {
prev = current;
if(key < current.key)
current = current.left;
else
current = current.right;
}
if(key < prev.key)
prev.left = newNode;
else
prev.right = newNode;
return newNode;
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
Implementazione ricorsiva
Tree insert(Tree root, Item key) {
{
if(root == NULL) {
root = new Tree(key);
return root;
}
if(key < root.key)
return insert(root.left, key);
else
return insert(root.right, key);
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
โ๏ธ Minimo
Scelto un nodo, restituisce il minimo rispetto a quel nodo.
L'idea รจ la seguente:
- ร sufficiente visitare ricorsivamente il figlio sinistro, visto che sarร minore del nodo corrente.
Implementazione iterativa
Tree min(Tree root) {
Tree current = root;
while(current.left != NULL) {
current = current.left;
}
return current;
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
Implementazione ricorsiva
Tree min(Tree root) {
if(root.left == NULL)
return root;
return min(root.left);
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
โถ๏ธ Massimo
Scelto un nodo, restituisce il massimo rispetto a quel nodo.
L'idea รจ la seguente:
- ร sufficiente visitare ricorsivamente il figlio destro, visto che sarร maggiore del nodo corrente.
Implementazione iterativa
Tree max(Tree root) {
Tree current = root;
while(current.right != NULL) {
current = current.right;
}
return current;
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
Implementazione ricorsiva
Tree max(Tree root) {
if(root.right == NULL)
return root;
return max(root.right);
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
Successore di un nodo
Il successore di un nodo
Ci sono essenzialmente 4 casi che possono capitare quando si cerca il successore di un nodo.
In tutti gli esempi il nodo blu รจ il nodo
Caso 1
graph TD A((6)) B((3)) C((8)) D((1)) E((4)) F((NULL)) G((12)) H((NULL)) I((5)) J((9)) K((15)) A-->B A-->C B-->D B-->E C-->F C-->G E-->H E-->I G-->J G-->K style C fill:#00758f style J fill:#ff0000
Il caso piรน semplice รจ quando il nodo
Caso 2
graph TD A((6)) B((3)) C((8)) D((1)) E((4)) F((NULL)) G((12)) H((NULL)) I((5)) J((9)) K((15)) A-->B A-->C B-->D B-->E C-->F C-->G E-->H E-->I G-->J G-->K style J fill:#00758f style G fill:#ff0000
Da questo caso in poi vogliamo trovare il successore di un nodo foglia. In questo specifico caso,
Pensiamo infatti ai possibili padri di 12:
- O il padre di 12 รจ piรน piccolo di
, come in questo caso (se cosรฌ non fosse 9 sarebbe un figlio sinistro del padre di 12) - O il padre di 12 รจ piรน grande di 12, quindi non sarebbe il suo successore.
In conclusione, seรจ figlio sinistro il suo successore รจ il padre.
Caso 3
graph TD A((6)) B((3)) C((8)) D((1)) E((4)) F((NULL)) G((12)) H((NULL)) I((5)) J((9)) K((15)) A-->B A-->C B-->D B-->E C-->F C-->G E-->H E-->I G-->J G-->K style I fill:#00758f style A fill:#ff0000
In questo caso,
Caso 4
graph TD A((6)) B((3)) C((8)) D((1)) E((4)) F((NULL)) G((12)) H((NULL)) I((5)) J((9)) K((15)) A-->B A-->C B-->D B-->E C-->F C-->G E-->H E-->I G-->J G-->K style K fill:#00758f
Il caso รจ lo stesso del precedente, dovremmo continuare a risalire l'albero nella speranza di trovare un figlio che รจ sinistro rispetto al padre. Il problema รจ che in questo caso
Implementazione iterativa
Attenzione: In questa implementazione dobbiamo per forza avere un campo parentall'interno del nodo, altrimenti non possiamo risalire l'albero!
Tree successor(Tree t) {
if(t == NULL)
return t;
/* Caso 1*/
Tree current = t;
if(current.right != NULL)
return min(current.right)
else {
Tree p = current.parent;
/* Se p.right != t finiamo nel caso 2-3 */
/* Se p == NULL finiamo nel caso 4 */
while(p != NULL && p.right == current) {
current = p;
p = p.parent;
}
return p;
}
}
- Time complexity:
(n รจ il numero di elementi) - Space complexity:
Predecessore di un nodo
Il predecessore di un nodo
Potrei scrivere "Vedi #Successore di un nodo" visto che รจ la stessa cosa, ma visto che fortunatamente esiste il copia-incolla lo descriverรฒ lo stesso.
Ci sono essenzialmente 4 casi che possono capitare quando si cerca il predecessore di un nodo.
In tutti gli esempi il nodo blu รจ il nodo
Caso 1
graph TB;
A((6))-->B((3))
A-->C((8))
B-->E((1))
B-->F((4))
C-->H((NULL))
C-->I((12))
F-->J((NULL))
F-->K((5))
I-->L((9))
I-->M((15))
style A fill:#00758f
style K fill:#ff0000Il caso piรน semplice รจ quando il nodo
Caso 2
graph TB;
A((6))-->B((3))
A-->C((8))
B-->E((1))
B-->F((4))
C-->H((NULL))
C-->I((12))
F-->J((NULL))
F-->K((5))
I-->L((9))
I-->M((15))
style K fill:#00758f
style F fill:#ff0000Da questo caso in poi vogliamo trovare il predecessore di un nodo foglia. In questo specifico caso,
Pensiamo infatti ai possibili padri di 5:
- O il padre di 5 รจ piรน piccolo di
, come in questo caso (se cosรฌ non fosse 5 sarebbe un figlio sinistro del padre di 4) - O il padre di 12 รจ piรน grande di 12, quindi non sarebbe il suo successore.
In conclusione, seรจ figlio destro il suo predecessore รจ il padre.
Caso 3
graph TB;
A((6))-->B((3))
A-->C((8))
B-->E((1))
B-->F((4))
C-->H((NULL))
C-->I((12))
F-->J((NULL))
F-->K((5))
I-->L((9))
I-->M((15))
style L fill:#00758f
style C fill:#ff0000In questo caso,
Caso 4
graph TB;
A((6))-->B((3))
A-->C((8))
B-->E((1))
B-->F((4))
C-->H((NULL))
C-->I((12))
F-->J((NULL))
F-->K((5))
I-->L((9))
I-->M((15))
style E fill:#00758fIl caso รจ lo stesso del precedente, dovremmo continuare a risalire l'albero nella speranza di trovare un figlio che รจ sinistro rispetto al padre. Il problema รจ che in questo caso
Implementazione iterativa
Attenzione: In questa implementazione dobbiamo per forza avere un campo parentall'interno del nodo, altrimenti non possiamo risalire l'albero!
Tree predecessor(Tree t) {
if(t == NULL)
return t;
/* Caso 1*/
Tree current = t;
if(current.left != NULL)
return max(current.left)
else {
Tree p = current.parent;
/* Se p.left != t finiamo nel caso 2-3 */
/* Se p == NULL finiamo nel caso 4 */
while(p != NULL && p.left == current) {
current = p;
p = p.parent;
}
return p;
}
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
โ Rimozione
Rimuove il nodo contenente la chiave
Ci sono essenzialmente 3 casi che possono capitare quando si rimuove un nodo.
Caso 1
Il caso piรน semplice รจ quando il nodo da eliminare
Esempio
graph TB;
A((11))-->B((4))
A-->C((NULL))
B-->E((1))
B-->F((9))
F-->J((6))
F-->K((10))
style J fill:#ff0000Risultato
graph TB;
A((11))-->B((4))
A-->C((NULL))
B-->E((1))
B-->F((9))
F-->J((NULL))
F-->K((10))Caso 2
Il nodo da eliminare
Esempio
graph TB;
A((11))-->B((4))
A-->C((NULL))
B-->E((1))
B-->F((9))
F-->J((6))
F-->K((10))
J-->L((NULL))
J-->M((7))
M-->N((NULL))
M-->O((8))
style J fill:#ff0000Risultato
graph TB;
A((11))-->B((4))
A-->C((NULL))
B-->E((1))
B-->F((9))
F-->J((7))
F-->K((10))
J-->L((NULL))
J-->M((8))
style J fill:#ff0000Caso 3
Il piรน complicato, quando il nodo da eliminare
In questo caso si procede nel seguente modo:
- Si cerca il successore del nodo da eliminare(o il predecessore, in base a com'รจ fatto l'albero conviene di piรน rimuovere uno che l'altro, vedi qui)
- Il successore puรฒ avere
- Zero figli, allora si stacca il successore e lo si sostituisce al nodo da eliminare, collegandogli i figli di
. - Un figlio (destro, non puรฒ essere sinistro altrimenti sarebbe proprio lui il successore), allora si stacca il successore e pure il suo figlio. Il successore lo si sostituisce al nodo da eliminare (collegandogli i vecchi figli di
), mentre il figlio del successore si attacca al padre del successore.
- Zero figli, allora si stacca il successore e lo si sostituisce al nodo da eliminare, collegandogli i figli di
Esempio
graph TB;
A((11))-->B((4))
A-->C((NULL))
B-->E((1))
B-->F((9))
F-->J((6))
F-->K((10))
J-->L((NULL))
J-->M((7))
M-->N((NULL))
M-->O((8))
style B fill:#ff0000Risultato
Passo intermedio:
graph TB;
A((11))-->B((4))
A-->C((NULL))
B-->E((1))
B-->F((9))
F-->P((NULL))
F-->K((10))
J((6))-->M((7))
M-->O((8))
style B fill:#ff0000
style J fill:#3b19fc
style M fill:#0b6b30
style O fill:#6b4c0bRisultato finale:
graph TB;
A((11))-->B((6))
A-->C((NULL))
B-->E((1))
B-->F((9))
F-->M((7))
F-->K((10))
M-->N((NULL))
M-->O((8))
style B fill:#3b19fc
style M fill:#0b6b30
style O fill:#6b4c0bImplementazione iterativa
Tree remove(Tree root, Item k) {
Tree p = NULL;
/* individuo il nodo da rimuovere */
Tree u = getParent(root, key, p);
/* se il nodo da rimuovere รจ presente nellโalbero... */
if(u == NULL) return;
/* e non ha figli... */
if(u.left == NULL && u.right == NULL) {
if(u != root)
unlink(p, u);
else
root = NULL;
}
/* e ha due figli... */
else if(u.left != NULL && u.right != NULL) {
Tree successor = u.right;
Tree succParent = u;
/* determiniamo il successore di u e teniamo un puntatore a suo padre*/
while(successor.left != NULL) {
succParent = successor;
successor = successor.left;
}
if(succParent == u) {
successor.left = u.left;
}
else {
/* il padre del successore ora punta al figlio destro del successore */
succParent.left = successor.right;
/* il successore viene sostituito al nodo da eliminare*/
successor.left = u.left;
successor.right = u.right;
}
if(u == p.left)
p.left = successor;
else
p.right = successor;
}
/* e ha un solo figlio... */
else {
/* determiniamo se il figlio รจ destro o sinistro*/
Tree childToLink = (u.left != NULL) ? u.left : u.right;
/* verifichiamo se il nodo da eliminare รจ radice */
if(u != root) {
/* se u รจ figlio sinistro attachiamo al padre il nuovo figlio sinistro */
if(u == p.left)
p.left = childToLink;
/* se u รจ figlio destro attachiamo al padre il nuovo figlio destro */
else
p.right = childToLink;
}
else
root = childToLink;
}
delete u;
}
/* Cerca un nodo e restituisce il puntatore ad esso e a suo padre */
Tree search(Tree root, Item key, Tree parent) {
Tree current = root;
while(current != NULL && current.key != key) {
parent = current;
if(current.key < key)
current = current.left;
else
current = current.right;
}
return current;
}
/* Scollega il padre dal figlio */
void unlink(Tree p, Tree u) {
if(u == p.left)
p.left = NULL;
else
p.right = NULL;
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity:
Implementazione ricorsiva
Tree remove(Tree root, Item k) {
if(k < root.key) {
root.left = remove(root.left, k);
else if(k > root.key)
root.right = remove(root.right, k);
else {
Tree toDelete = root;
/* Copre sia il caso di 0 figli, sia il caso di 1 figlio */
if(root.left == NULL || root.right == NULL)
return (root.left != NULL) ? root.left : root.right;
else {
Tree *succ = root.right;
Tree *succParent = root;
while(succ.left) {
succParent = succ;
succ = succ.left;
}
/* corner case, avviene quando vogliamo eliminare la radice ed รจ proprio il padre del successore */
if(succParent == root) {
/* basta collegare il sottoalbero sinistro al successore e farlo diventare radice */
succ.left = root.left;
}
else {
/* colleghiamo il padre del successore al figlio del successore */
succParent.left = succ.right;
/* per non fare root.key = succ.key */
succ.left = root.left;
succ.right = root.right;
}
root = succ;
}
delete toDelete;
}
return root;
}
- Time complexity:
(h รจ l'altezza dell'albero)
(Worst case Time Complexity :) - Space complexity: