Prelude
Questo articolo è dedicato agli alberi binari di ricerca. Di recente ho scritto un articolo su Lì non ho prestato molta attenzione agli alberi binari, poiché i metodi di ricerca, inserimento e cancellazione non erano rilevanti. Adesso ho deciso di scrivere un articolo specificamente sugli alberi. Cominciamo.
Un albero è una struttura dati composta da nodi connessi 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 sotto il tag!
Terminologia
Radice
La radice dell'albero è il suo nodo più alto. Nell'esempio, questo è il nodo A. Nell'albero, dalla radice a qualsiasi altro nodo può esserci un solo percorso! In realtà, ogni nodo può essere considerato come la radice del relativo sottoalbero.
Genitori/Discendenti
Tutti i nodi, tranne quello radice, hanno esattamente un arco che sale verso un altro nodo. Il nodo posizionato sopra quello corrente è chiamato genitore di questo nodo. Un nodo posizionato sotto quello corrente, e connesso a esso, è chiamato discendente di questo nodo. Prendiamo l'esempio. Prendiamo il nodo B, quindi il suo genitore sarà il nodo A, e i suoi figli saranno i nodi D, E e F.
Foglia
Un nodo che non ha figli 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 saranno trattati in seguito. Quindi, un albero binario è un albero in cui ogni nodo può avere al massimo due figli. Come avete indovinato, l'albero dell'esempio non sarà binario, poiché i nodi B e H hanno più di due figli. Ecco un esempio di albero binario:
Nei nodi dell'albero può trovarsi qualsiasi informazione. Un albero binario di ricerca è un albero binario che ha le seguenti proprietà:
- Entrambi i sottoalberi — quello sinistro e quello destro — sono alberi binari di ricerca.
- In tutti i nodi del sottoalbero sinistro di un nodo X qualsiasi, i valori delle chiavi dei dati sono minori rispetto al valore della chiave dei dati del nodo X stesso.
- In tutti i nodi del sottoalbero destro di un nodo X qualsiasi, i valori delle chiavi dei dati sono maggiori o uguali rispetto al valore della chiave dei dati del nodo X stesso.
Chiave — qualsiasi caratteristica di un nodo (ad esempio, un numero). La chiave è necessaria per poter trovare l'elemento dell'albero corrispondente a questa chiave. Esempio di albero binario di ricerca:
Rappresentazione dell'albero
Man mano che avanziamo, presenterò alcuni (possibilmente incompleti) frammenti di codice per migliorare la vostra comprensione. Il codice completo sarà alla fine dell'articolo.
Un albero è composto da nodi. Struttura del 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 figli (è possibile che i figli 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 è la chiave del nodo.
Con il nodo chiarito, ora parliamo delle problematiche attuali sugli alberi. Qui e in seguito, con la parola "albero" intenderò il concetto di albero binario di ricerca. La struttura di un albero binario:
public class BinaryTree {
private Node root;
//metodi dell'albero
}
Come classe, avremo bisogno solo della radice dell'albero, poiché dalla radice possiamo accedere a qualsiasi nodo dell'albero utilizzando i metodi getLeftChild() e getRightChild().
Algoritmi negli alberi
Поиск
Supponiamo di avere un albero costruito. Come trovare l'elemento con la chiave key? Dobbiamo spostarci 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, passiamo al figlio sinistro del nodo; se è maggiore, passiamo a quello destro; se le chiavi sono uguali, il nodo ricercato è stato trovato! Ecco il codice corrispondente:
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;
}
Se current diventa uguale a null, significa che l'iterazione ha raggiunto la fine dell'albero (a livello concettuale ti trovi in un luogo non esistente dell'albero — nel figlio di una foglia).
Esaminiamo l'efficienza dell'algoritmo di ricerca su un albero bilanciato (un albero in cui i nodi sono distribuiti in modo piuttosto uniforme). In questo caso, l'efficienza della ricerca sarà O(log(n)), dove il logaritmo è in base 2. Osservate: se in un albero bilanciato ci sono n elementi, ciò significa che ci saranno log(n) livelli dell'albero in base 2. Nella ricerca, ad ogni passo del ciclo si scende di un livello.
Inserimento
Se avete afferrato il concetto di ricerca, capire l'inserimento non sarà difficile. Bisogna semplicemente scendere fino alla foglia dell'albero (seguendo le regole di discesa descritte nella ricerca) e diventare un 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, oltre al nodo corrente, è necessario memorizzare le informazioni sul genitore del nodo attuale. Quando current diventa uguale a null, nella variabile parent ci sarà il nodo foglia di cui abbiamo bisogno.
L'efficienza dell'inserimento, ovviamente, sarà la stessa della ricerca — O(log(n)).
Eliminazione
La cancellazione è l'operazione più complessa da effettuare con un albero. È chiaro che prima dovremo trovare l'elemento che intendiamo rimuovere. Ma cosa succede dopo? Se assegniamo semplicemente il valore null al suo riferimento, perderemo le informazioni sul sottoalbero di cui questo nodo è la radice. I metodi di cancellazione dell'albero si dividono in tre casi.
Primo caso. Il nodo da eliminare non ha discendenti.
Se il nodo da eliminare non ha discendenti, significa che è una foglia. Pertanto, possiamo 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 complicato. Torniamo al nostro esempio. Supponiamo di dover rimuovere un elemento con chiave 14. Considerate che essendo un discendente destro del nodo con chiave 10, qualsiasi suo discendente (in questo caso il destro) avrà una chiave maggiore di 10, quindi può essere facilmente "rimosso" dall'albero, e il padre può collegarsi direttamente con il discendente del nodo rimosso, cioè il nodo con chiave 10 si collegherà al nodo 13. La situazione sarebbe analoga se dovessimo rimuovere un nodo che è un discendente sinistro del suo genitore. Pensateci da soli: è un'analogia precisa.
Terzo caso. Un nodo ha due discendenti.
Il caso più complesso. Analizziamo un nuovo esempio.
Ricerca del successore
Supponiamo di dover rimuovere un nodo con chiave 25. Chi metteremo al suo posto? Qualcuno dei suoi successori (discendenti o discendenti dei discendenti) deve diventare successore(colui che occuperà il posto del nodo rimosso).
Come capire chi deve diventare il successore? È intuitivamente chiaro che si tratta di un nodo nell'albero, la cui chiave è la più vicina in valore a quella del nodo da rimuovere. L'algoritmo è il seguente. Bisogna andare al suo discendente destro (sempre a destra, poiché si è già detto che la chiave del successore è maggiore di quella del nodo eliminato) e poi percorrere la catena dei discendenti sinistri di questo discendente destro. Nell'esempio dobbiamo recarci al nodo con chiave 35 e poi scendere fino a una foglia attraverso la catena dei suoi discendenti sinistri — in questo caso, questa catena è costituita solo dal nodo con chiave 30. In senso stretto, stiamo cercando il nodo più piccolo in un insieme di nodi che sono 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(); // nodo "iterativo"
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
// uscendo dal ciclo abbiamo successore e genitore del successore
if (successor != deleteNode.getRightChild()) { // se il successore non corrisponde al nodo destro del nodo da eliminare
parentSuccessor.setLeftChild(successor.getRightChild()); // il suo genitore prende il discendente del successore, per non perderlo
successor.setRightChild(deleteNode.getRightChild()); // collegare il successore con il nodo destro del nodo da eliminare
}
return successor;
}
Codice completo del metodo delete:
public boolean delete(int deleteKey) {
Node current = root;
Node parent = current;
boolean isLeftChild = false; // In base a se il nodo da eliminare è un figlio sinistro o destro, 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
È ovvio come trovare il valore minimo/massimo nell'albero: si deve passare in sequenza lungo la catena degli elementi sinistri/destri dell'albero; quando si raggiunge una foglia, essa sarà l'elemento minimo/massimo.
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;
}
La complessità è O(log(n))
Attraversamento simmetrico
L'attraversamento è la visita di ciascun nodo dell'albero per compiere un'azione su di esso.
Algoritmo di attraversamento simmetrico ricorsivo:
- Compiere un'azione sul figlio sinistro
- Compiere un'azione su se stessi
- Compiere un'azione sul figlio destro
Codice:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Qui può esserci qualsiasi cosa
inOrder(current.getRightChild());
}
}
Conclusione
Finalmente! Se ho omesso qualcosa o se ci sono osservazioni, aspetto i vostri commenti. Come promesso, ecco il codice completo.
Node.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class 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.
Degrado 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 rimozione diventerà quella di una lista collegata: O(n). Questo è uno dei più importanti, a mio parere, svantaggi degli alberi binari.
Solo gli utenti registrati possono partecipare al sondaggio. , per favore.
Non sono molto tempo su Habr, e mi piacerebbe sapere su quali argomenti vi piacerebbe vedere più articoli?
Strutture dati
Algoritmi (DP, ricorsione, compressione dei 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. 1 utente ha votato per astensione.
Fonte: habr.com
