Preludio
Questo articolo è dedicato agli alberi binari di ricerca. Recentemente ho scritto un articolo su In quel caso non prestavo molta attenzione agli alberi binari, poiché i metodi di ricerca, inserimento e cancellazione non erano rilevanti. Ora ho deciso di scrivere un articolo proprio sugli alberi. Cominciamo.
Un albero è una struttura dati composta da nodi collegati da archi. Si può dire che un albero è un caso particolare di grafo. Ecco un esempio di albero:
Questo non è un albero binario di ricerca! Tutto a casa!
Terminologia
Radice
La radice dell'albero è il nodo più alto. Nell'esempio, è il nodo A. In un albero, dalla radice a qualsiasi altro nodo può esserci solo un percorso! In realtà, qualsiasi nodo può essere considerato come la radice del relativo sott'albero.
Genitori/Discendenti
Tutti i nodi, tranne quello radice, hanno esattamente un arco che conduce verso un altro nodo. Il nodo situato sopra quello corrente è chiamato genitore di questo nodo. Il nodo situato sotto quello corrente e collegato ad esso è chiamato discendente di questo nodo. Prendiamo come esempio il nodo B, quindi il suo genitore sarà il nodo A, mentre i suoi discendenti saranno i nodi D, E e F.
Foglia
Un nodo che non ha discendenti sarà chiamato foglia dell'albero. Nell'esempio, le foglie saranno i nodi D, E, F, G, I, J, K.
Questa è la terminologia di base. Altri concetti verranno trattati successivamente. Dunque, un albero binario è un albero in cui ogni nodo avrà al massimo due discendenti. Come avrete già indovinato, l'albero dell'esempio non sarà binario, poiché i nodi B e H hanno più di due discendenti. Ecco un esempio di albero binario:
Nei nodi dell'albero può trovarsi qualsiasi informazione. Un albero binario di ricerca è un albero binario che presenta le seguenti proprietà:
- Entrambi i sott'alberi — quello sinistro e quello destro — sono alberi binari di ricerca.
- Per tutti i nodi del sott'albero sinistro di un nodo X, i valori delle chiavi sono minori rispetto al valore della chiave del nodo X stesso.
- Per tutti i nodi del sott'albero destro di un nodo X, i valori delle chiavi sono maggiori o uguali rispetto al valore della chiave del nodo X stesso.
Chiave — una qualsiasi caratteristica del nodo (ad esempio, un numero). La chiave è necessaria per poter trovare l'elemento dell'albero corrispondente a quella chiave. Ecco un esempio di albero binario di ricerca:
Rappresentazione dell'albero
Man mano che procediamo, fornirò alcuni frammenti di codice (possibilmente incompleti) per migliorare la tua comprensione. Il codice completo sarà alla fine dell'articolo.
L'albero è composto da nodi. La struttura di un nodo:
public class Node {
private T data;
private int key;
private Node leftChild;
private Node rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
//...altri metodi del nodo
}
Ogni nodo ha due discendenti (è possibile che i discendenti leftChild e/o rightChild contengano il valore null). Probabilmente hai capito che in questo caso il numero data rappresenta i dati memorizzati nel nodo; key rappresenta la chiave del nodo.
Ora che abbiamo chiarito il nodo, parliamo delle problematiche attuali sugli alberi. Qui e oltre, con il termine "albero" intenderò il concetto di un albero binario di ricerca. La struttura di un albero binario:
public class BinaryTree {
private Node root;
//metodi dell'albero
}
Come campo di classe, avremo bisogno solo della radice dell'albero, poiché partendo dalla radice, con i metodi getLeftChild() e getRightChild(), possiamo raggiungere qualsiasi nodo dell'albero.
Algoritmi nell'albero
Ricerca
Supponiamo di avere un albero costruito. Come trovare l'elemento con la chiave key? Bisogna muoversi successivamente dalla radice verso il basso nell'albero e confrontare il valore di key con la chiave del nodo corrente: se key è minore della chiave del nodo corrente, passare al discendente sinistro del nodo; se è maggiore, passare al destro; se le chiavi sono uguali, il nodo cercato è trovato! Il codice corrispondente:
public Node find(int key) {
Node current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
Se current diventa uguale a null, significa che l'iterazione ha raggiunto la fine dell'albero (a livello concettuale, ti trovi in un luogo inesistente dell'albero — un discendente di una foglia).
Consideriamo l'efficacia dell'algoritmo di ricerca su un albero bilanciato (un albero in cui i nodi sono distribuiti in modo più o meno uniforme). In questo caso, l'efficacia della ricerca sarà O(log(n)), con logaritmo in base 2. Nota: se in un albero bilanciato ci sono n elementi, significa che ci saranno log(n) livelli in base 2 dell'albero. E nella ricerca, in un singolo ciclo, scenderai di un livello.
Inserimento
Se hai colto il senso della ricerca, comprendere l'inserimento non ti costerà sforzo. Devi semplicemente scendere fino al foglio dell'albero (secondo le regole di discesa descritte nella ricerca) e diventare suo discendente: sinistro o destro, a seconda della chiave. Implementazione:
public void insert(T insertData, int key) {
Node current = root;
Node parent;
Node newNode = new Node(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
In questo caso, è necessario, oltre al nodo corrente, memorizzare l'informazione sul genitore del nodo attuale. Quando current diventa uguale a null, la variabile parent conterrà il foglio di cui abbiamo bisogno.
L'efficienza dell'inserimento sarà ovviamente la stessa della ricerca: O(log(n)).
Elimina
La cancellazione è l'operazione più complessa che si dovrà effettuare sull'albero. È chiaro che prima sarà necessario trovare l'elemento che si intende eliminare. Ma cosa succede dopo? Se assegniamo semplicemente il suo riferimento a null, perderemo l'informazione sul sottoalbero di cui questo nodo è la radice. I metodi di cancellazione dell'albero vengono suddivisi in tre casi.
Primo caso. Il nodo da eliminare non ha discendenti.
Se il nodo da eliminare non ha discendenti, significa che è una foglia. Quindi, è possibile semplicemente assegnare il valore null ai campi leftChild o rightChild del suo genitore.
Secondo caso. Il nodo da eliminare ha un discendente.
Questo caso non è molto complesso. Torniamo al nostro esempio. Supponiamo di dover eliminare l'elemento con chiave 14. Convenite che poiché è un discendente destro del nodo con chiave 10, qualsiasi suo discendente (in questo caso il destro) avrà una chiave maggiore di 10, quindi è facile "ritagliarlo" dall'albero e collegare direttamente il genitore al discendente del nodo da eliminare, cioè collegare il nodo con chiave 10 al nodo 13. Sarebbe simile la situazione se dovessimo eliminare un nodo che è un discendente sinistro del suo genitore. Rifletti su questo: è un'analogia precisa.
Terzo caso. Il nodo ha due discendenti.
Il caso più complesso. Analizziamolo con un nuovo esempio.
Ricerca del successore
Supponiamo di dover rimuovere un nodo con la chiave 25. Chi mettiamo al suo posto? Qualcuno dei suoi seguaci (discendenti o discendenti dei discendenti) deve diventare successore(colui che occuperà il posto del nodo rimosso).
Come capire chi deve diventare successore? È intuitivamente chiaro che si tratta di un nodo nell'albero, la cui chiave è la successiva più grande rispetto al nodo rimosso. L'algoritmo è il seguente. Dobbiamo passare al suo discendente destro (sempre a destra, poiché è già stato detto che la chiave del successore è maggiore della chiave del nodo rimosso) e poi attraversare la catena dei discendenti sinistri di questo discendente destro. Nell'esempio dobbiamo passare al nodo con chiave 35 e poi scendere fino alla foglia lungo la catena dei suoi discendenti sinistri: in questo caso, questa catena è composta solo dal nodo con chiave 30. In termini rigorosi, stiamo cercando il nodo più piccolo all'interno dell'insieme dei nodi maggiori del nodo cercato.
Codice del metodo di ricerca del successore:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode; // genitore del successore
Node<T> successor = deleteNode; // successore
Node<T> current = successor.getRightChild(); // semplicemente un nodo "in transito"
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
// all'uscita dal ciclo abbiamo il successore e il genitore del successore
if (successor != deleteNode.getRightChild()) { // se il successore non coincide con il discendente destro del nodo rimosso
parentSuccessor.setLeftChild(successor.getRightChild()); // il suo genitore prende il discendente del successore, per non perderlo
successor.setRightChild(deleteNode.getRightChild()); // colleghiamo il successore al discendente destro del nodo rimosso
}
return successor;
}
Codice completo del metodo delete:
public boolean delete(int deleteKey) {
Node current = root;
Node parent = current;
boolean isLeftChild = false; // A seconda che il nodo da eliminare sia un figlio sinistro o destro del suo genitore, la variabile booleana isLeftChild assumerà il valore true o false rispettivamente.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) { // primo caso
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) { // secondo caso
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else { // terzo caso
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
La complessità può essere approssimata a O(log(n)).
Ricerca del massimo/minimo nell'albero
È evidente come trovare il valore minimo/massimo nell'albero: bisogna seguire in sequenza la catena dei nodi sinistri/destri dell'albero; quando si arriva alla foglia, essa sarà l'elemento minimo/massimo.
public Node getMinimum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node getMaximum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
La complessità è O(log(n))
Traversal simmetrico
Il traversal implica la visita di ogni nodo dell'albero per eseguire un'azione su di esso.
Algoritmo di traversal simmetrico ricorsivo:
- Eseguire un'azione sul figlio sinistro
- Eseguire un'azione su se stessi
- Eseguire un'azione sul figlio destro
Codice:
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Qui può esserci tutto quello che vuoi
inOrder(current.getRightChild());
}
}
Conclusione
Finalmente! Se non ho spiegato qualcosa o se ci sono commenti, aspetto i vostri feedback. Come promesso, fornisco il codice completo.
Node.java:
public class Node {
private T data;
private int key;
private Node leftChild;
private Node rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node newNode) {
leftChild = newNode;
}
public void setRightChild(Node newNode) {
rightChild = newNode;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
classe pubblica BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
P.S.
Degradazione a O(n)
Molti di voi potrebbero aver notato: e se facessimo in modo che l'albero diventasse sbilanciato? Ad esempio, inserendo nell'albero nodi con chiavi crescenti: 1,2,3,4,5,6… Allora l'albero assomiglierà a una lista collegata. E sì, l'albero perderà la sua struttura ad albero, e di conseguenza, anche l'efficienza nell'accesso ai dati. La complessità delle operazioni di ricerca, inserimento e cancellazione diventerà simile a quella di una lista collegata: O(n). Qui si manifesta uno dei più grandi difetti, a mio avviso, degli alberi binari.
Solo gli utenti registrati possono partecipare al sondaggio. , per favore.
Non sono su Habr da molto tempo e mi piacerebbe sapere quali argomenti vorreste vedere trattati di più negli articoli?
Strutture dati
Algoritmi (DP, ricorsione, compressione dati, ecc.)
Applicazione di strutture dati e algoritmi nella vita reale
Programmazione di applicazioni Android in Java
Programmazione di applicazioni web in Java
Hanno votato 2 utenti. Si è astenuto 1 utente.
Fonte: habr.com
