Guida agli alberi AVL in Java

1. Introduzione

In questo tutorial, introdurremo l'albero AVL e esamineremo gli algoritmi per l'inserimento, l'eliminazione e la ricerca di valori.

2. Cos'è l'albero AVL?

L'albero AVL, dal nome dei suoi inventori Adelson-Velsky e Landis, è un albero binario di ricerca autobilanciato (BST).

Un albero di autobilanciamento è un albero di ricerca binario che bilancia l'altezza dopo l'inserimento e la cancellazione secondo alcune regole di bilanciamento.

La complessità temporale nel caso peggiore di un BST è una funzione dell'altezza dell'albero. In particolare, il percorso più lungo dalla radice dell'albero a un nodo. Per un BST con N nodi, diciamo che ogni nodo ha solo zero o un figlio. Pertanto la sua altezza è uguale a N e il tempo di ricerca nel caso peggiore è O (N). Quindi il nostro obiettivo principale in una BST è mantenere l'altezza massima vicino al log (N).

Il fattore di equilibrio del nodo N è l' altezza (destra (N)) - altezza (sinistra (N)) . In un albero AVL, il fattore di equilibrio di un nodo può essere solo uno dei valori 1, 0 o -1.

Definiamo un oggetto Node per il nostro albero:

public class Node { int key; int height; Node left; Node right; ... }

Quindi, definiamo AVLTree :

public class AVLTree { private Node root; void updateHeight(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); } int height(Node n) { return n == null ? -1 : n.height; } int getBalance(Node n) { return (n == null) ? 0 : height(n.right) - height(n.left); } ... }

3. Come bilanciare un albero AVL?

L'albero AVL controlla il fattore di equilibrio dei suoi nodi dopo l'inserimento o l'eliminazione di un nodo. Se il fattore di equilibrio di un nodo è maggiore di uno o minore di -1, l'albero si riequilibra.

Ci sono due operazioni per ribilanciare un albero:

  • rotazione a destra e
  • rotazione a sinistra.

3.1. Rotazione a destra

Cominciamo con la giusta rotazione.

Supponiamo di avere un BST chiamato T1, con Y come nodo radice, X come figlio sinistro di Y e Z come figlio destro di X. Date le caratteristiche di un BST, sappiamo che X <Z <Y.

Dopo una rotazione destra di Y, abbiamo un albero chiamato T2 con X come radice e Y come figlio destro di X e Z come figlio sinistro di Y. T2 è ancora un BST perché mantiene l'ordine X <Z <Y .

Diamo un'occhiata alla giusta operazione di rotazione per il nostro AVLTree :

Node rotateRight(Node y) { Node x = y.left; Node z = x.right; x.right = y; y.left = z; updateHeight(y); updateHeight(x); return x; }

3.2. Operazione di rotazione a sinistra

Abbiamo anche un'operazione di rotazione sinistra.

Assumiamo un BST chiamato T1, con Y come nodo radice, X come figlio destro di Y e Z come figlio sinistro di X. Detto questo, sappiamo che Y <Z <X.

Dopo una rotazione sinistra di Y, abbiamo un albero chiamato T2 con X come radice e Y come figlio sinistro di X e Z come figlio destro di Y. T2 è ancora un BST perché mantiene l'ordine Y <Z <X .

Diamo un'occhiata all'operazione di rotazione sinistra per il nostro AVLTree :

Node rotateLeft(Node y) { Node x = y.right; Node z = x.left; x.left = y; y.right = z; updateHeight(y); updateHeight(x); return x; }

3.3. Tecniche di riequilibrio

Possiamo usare le operazioni di rotazione destra e sinistra in combinazioni più complesse per mantenere bilanciato l'albero AVL dopo ogni modifica nei suoi nodi . In una struttura sbilanciata, almeno un nodo ha un fattore di equilibrio pari a 2 o -2. Vediamo come possiamo bilanciare l'albero in queste situazioni.

Quando il fattore di equilibrio del nodo Z è 2, la sottostruttura con Z come radice si trova in uno di questi due stati, considerando Y come il figlio destro di Z.

Per il primo caso, l'altezza nel bambino destro di Y (X) è maggiore dell'altezza del bambino sinistro (T2). Possiamo riequilibrare l'albero facilmente con una rotazione sinistra di Z.

Per il secondo caso, l'altezza del bambino destro di Y (T4) è inferiore all'altezza del bambino sinistro (X). Questa situazione richiede una combinazione di operazioni di rotazione.

In questo caso, prima ruotiamo Y verso destra, in modo che l'albero abbia la stessa forma del caso precedente. Quindi possiamo riequilibrare l'albero con una rotazione sinistra di Z.

Inoltre, quando il fattore di equilibrio del nodo Z è -2, il suo sottoalbero è in uno di questi due stati, quindi consideriamo Z come radice e Y come suo figlio sinistro.

L'altezza nel figlio sinistro di Y è maggiore di quella del suo figlio destro, quindi bilanciamo l'albero con la rotazione destra di Z.

O nel secondo caso, il figlio destro di Y ha un'altezza maggiore del figlio sinistro.

Quindi, prima di tutto, lo trasformiamo nella forma precedente con una rotazione sinistra di Y, quindi bilanciamo l'albero con la rotazione destra di Z.

Diamo uno sguardo all'operazione di ribilanciamento per il nostro AVLTree :

Node rebalance(Node z) { updateHeight(z); int balance = getBalance(z); if (balance > 1) { if (height(z.right.right) > height(z.right.left)) { z = rotateLeft(z); } else { z.right = rotateRight(z.right); z = rotateLeft(z); } } else if (balance  height(z.left.right)) z = rotateRight(z); else { z.left = rotateLeft(z.left); z = rotateRight(z); } } return z; }

Useremo il ribilanciamento dopo aver inserito o eliminato un nodo per tutti i nodi nel percorso dal nodo modificato alla radice.

4. Inserire un nodo

Quando inseriremo una chiave nell'albero, dobbiamo individuare la sua posizione corretta per passare le regole BST. Quindi partiamo dalla radice e confrontiamo il suo valore con la nuova chiave. Se la chiave è maggiore, continuiamo a destra, altrimenti andiamo al bambino sinistro.

Una volta trovato il nodo genitore appropriato, aggiungiamo la nuova chiave come nodo a sinistra oa destra, a seconda del valore.

Dopo aver inserito il nodo, abbiamo un BST, ma potrebbe non essere un albero AVL. Pertanto, controlliamo i fattori di equilibrio e ribilanciamo il BST per tutti i nodi nel percorso dal nuovo nodo alla radice.

Diamo un'occhiata all'operazione di inserimento:

Node insert(Node node, int key) { if (node == null) { return new Node(key); } else if (node.key > key) { node.left = insert(node.left, key); } else if (node.key < key) { node.right = insert(node.right, key); } else { throw new RuntimeException("duplicate Key!"); } return rebalance(node); }

È importante ricordare che una chiave è unica nell'albero: non esistono due nodi che condividono la stessa chiave.

La complessità temporale dell'algoritmo di inserimento è una funzione dell'altezza. Poiché il nostro albero è bilanciato, possiamo presumere che la complessità temporale nel caso peggiore sia O (log (N)).

5. Eliminare un nodo

Per eliminare una chiave dall'albero, dobbiamo prima trovarla nel BST.

Dopo aver trovato il nodo (chiamato Z), dobbiamo introdurre il nuovo candidato come suo sostituto nell'albero. Se Z è una foglia, il candidato è vuoto. Se Z ha un solo figlio, questo bambino è il candidato, ma se Z ha due figli, il processo è un po 'più complicato.

Assume the right child of Z called Y. First, we find the leftmost node of the Y and call it X. Then, we set the new value of Z equal to X ‘s value and continue to delete X from Y.

Finally, we call the rebalance method at the end to keep the BST an AVL Tree.

Here is our delete method:

Node delete(Node node, int key) { if (node == null) { return node; } else if (node.key > key) { node.left = delete(node.left, key); } else if (node.key < key) { node.right = delete(node.right, key); } else { if (node.left == null || node.right == null) { node = (node.left == null) ? node.right : node.left; } else { Node mostLeftChild = mostLeftChild(node.right); node.key = mostLeftChild.key; node.right = delete(node.right, node.key); } } if (node != null) { node = rebalance(node); } return node; }

The time complexity of the delete algorithm is a function of the height of the tree. Similar to the insert method, we can assume that time complexity in the worst case is O(log(N)).

6. Search for a Node

Searching for a node in an AVL Tree is the same as with any BST.

Start from the root of the tree and compare the key with the value of the node. If the key equals the value, return the node. If the key is greater, search from the right child, otherwise continue the search from the left child.

La complessità temporale della ricerca è funzione dell'altezza. Possiamo supporre che la complessità temporale nel caso peggiore sia O (log (N)).

Vediamo il codice di esempio:

Node find(int key) { Node current = root; while (current != null) { if (current.key == key) { break; } current = current.key < key ? current.right : current.left; } return current; }

7. Conclusione

In questo tutorial, abbiamo implementato un albero AVL con operazioni di inserimento, eliminazione e ricerca.

Come sempre, puoi trovare il codice su Github.