preludio
Questo articolo riguarda gli alberi di ricerca binari. Recentemente ho scritto un articolo su Lì non prestavo molta attenzione agli alberi binari, perché i metodi di ricerca, inserimento ed eliminazione non erano rilevanti. Ora ho deciso di scrivere un articolo sugli alberi. Forse inizieremo.
Un albero è una struttura dati costituita da nodi collegati da bordi. Possiamo dire che un albero è un caso speciale di grafo. Ecco un esempio di albero:
Questo non è un albero di ricerca binario! Tutto è sotto taglio!
terminologia
radice
Radice dell'albero è il nodo più in alto. Nell'esempio, questo è il nodo A. Nell'albero, solo un percorso può condurre dalla radice a qualsiasi altro nodo! Infatti, qualsiasi nodo può essere considerato come la radice del sottoalbero corrispondente a questo nodo.
Genitori/figli
Tutti i nodi tranne la radice hanno esattamente un bordo che porta a un altro nodo. Viene chiamato il nodo sopra il nodo corrente genitore questo nodo. Viene chiamato un nodo situato sotto quello attuale e ad esso collegato discendente questo nodo. Facciamo un esempio. Prendi il nodo B, quindi il suo genitore sarà il nodo A e i suoi figli saranno i nodi D, E e F.
Лист
Un nodo che non ha figli è chiamato foglia dell'albero. Nell'esempio i nodi D, E, F, G, I, J, K saranno foglie.
Questa è la terminologia di base. Altri concetti verranno discussi in seguito. Quindi, un albero binario è un albero in cui ciascun nodo non avrà più di due figli. Come hai intuito, l'albero dell'esempio non sarà binario, perché i nodi B e H hanno più di due figli. Ecco un esempio di albero binario:
I nodi dell'albero possono contenere qualsiasi informazione. Un albero di ricerca binario è un albero binario che ha le seguenti proprietà:
- Entrambi i sottoalberi sinistro e destro sono alberi di ricerca binari.
- Tutti i nodi del sottoalbero sinistro di un nodo X arbitrario hanno valori della chiave dati inferiori al valore della chiave dati del nodo X stesso.
- Tutti i nodi del sottoalbero destro di un nodo X arbitrario hanno valori della chiave dati maggiori o uguali al valore della chiave dati del nodo X stesso.
Chiave - alcune caratteristiche del nodo (ad esempio, un numero). La chiave è necessaria per poter trovare l'elemento dell'albero a cui corrisponde questa chiave. Esempio di albero di ricerca binario:
visualizzazione ad albero
Man mano che procedo, includerò alcune parti di codice (forse incomplete) per migliorare la tua comprensione. Il codice completo sarà alla fine dell'articolo.
L'albero è formato da nodi. Struttura dei nodi:
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 Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...остальные методы узла
}
Ogni nodo ha due figli (è del tutto possibile che i figli leftChild e/o rightChild siano nulli). Probabilmente hai capito che in questo caso i dati numerici sono i dati memorizzati nel nodo; chiave - chiave del nodo.
Abbiamo risolto il nodo, ora parliamo dei problemi urgenti riguardanti gli alberi. Nel seguito con il termine "albero" si intenderà il concetto di albero binario di ricerca. Struttura ad albero binario:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Come campo di classe, abbiamo bisogno solo della radice dell'albero, perché dalla radice, utilizzando i metodi getLeftChild() e getRightChild(), puoi raggiungere qualsiasi nodo dell'albero.
Algoritmi ad albero
Ricerca
Diciamo che hai un albero costruito. Come trovare l'elemento con chiave chiave? Devi spostarti in sequenza dalla radice lungo l'albero e confrontare il valore di key con la chiave del nodo successivo: se key è inferiore alla chiave del nodo successivo, vai al discendente sinistro del nodo, se maggiore - a destra, se le chiavi sono uguali, viene trovato il nodo desiderato! Codice rilevante:
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 la corrente diventa nulla, l'iterazione ha raggiunto la fine dell'albero (a livello concettuale, ti trovi in un posto inesistente nell'albero: il figlio di una foglia).
Considera l'efficienza dell'algoritmo di ricerca su un albero bilanciato (un albero in cui i nodi sono distribuiti più o meno uniformemente). Quindi l'efficienza di ricerca sarà O(log(n)) e il logaritmo in base 2. Vedi: se ci sono n elementi in un albero bilanciato, ciò significa che ci saranno log(n) livelli in base 2 dell'albero. E nella ricerca, per un passo del ciclo, scendi di un livello.
inserire
Se hai colto l'essenza della ricerca, non ti sarà difficile comprendere l'inserimento. Devi solo scendere sulla foglia dell'albero (secondo le regole di discesa descritte nella ricerca) e diventarne il discendente: sinistra o destra, a seconda della chiave. Implementazione:
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;
}
}
}
}
}
In questo caso, oltre al nodo corrente, è necessario memorizzare informazioni sul genitore del nodo corrente. Quando current diventa nullo, la variabile genitore conterrà il foglio di cui abbiamo bisogno.
L'efficienza dell'inserimento sarà ovviamente la stessa della ricerca - O(log(n)).
Rimozione
La cancellazione è l'operazione più complessa che dovrà essere eseguita con un albero. È chiaro che prima bisognerà trovare l'elemento che andremo a rimuovere. Ma allora cosa? Se impostiamo semplicemente il suo riferimento su null, perderemo informazioni sul sottoalbero la cui radice è questo nodo. I metodi di rimozione degli alberi sono divisi in tre casi.
Primo caso. Il nodo da rimuovere non ha figli.
Se il nodo da eliminare non ha figli significa che è una foglia. Pertanto, puoi semplicemente impostare i campi leftChild o rightChild del suo genitore su null.
Secondo caso. Il nodo da rimuovere ha un figlio
Anche questo caso non è molto difficile. Torniamo al nostro esempio. Supponiamo di dover eliminare un elemento con chiave 14. Concordiamo che poiché è il figlio destro del nodo con chiave 10, allora qualsiasi dei suoi discendenti (in questo caso, quello giusto) avrà una chiave maggiore di 10, quindi tu può facilmente "tagliarlo" dall'albero e collegare il genitore direttamente al figlio del nodo da eliminare, ad es. colleghiamo il nodo con chiave 10 al nodo 13. La situazione sarebbe simile se dovessimo eliminare un nodo che è il figlio sinistro del suo genitore. Pensaci tu stesso: un'analogia esatta.
Terzo caso. Il nodo ha due figli
Il caso più difficile. Diamo un'occhiata a un nuovo esempio.
Cerca un successore
Diciamo che dobbiamo togliere il nodo con la chiave 25. Chi mettiamo al suo posto? Uno dei suoi seguaci (discendenti o discendenti di discendenti) deve diventare successore(colui che prenderà il posto del nodo rimosso).
Come fai a sapere chi dovrebbe essere il successore? Intuitivamente, questo è il nodo dell'albero la cui chiave è la successiva più grande del nodo da rimuovere. L'algoritmo è il seguente. Bisogna andare al suo figlio destro (sempre a quello destro, perché è già stato detto che la chiave del successore è maggiore della chiave del nodo che si sta cancellando), e poi passare attraverso la catena dei figli sinistri di questo nodo destro bambino. Nell'esempio, dobbiamo andare al nodo con la chiave 35, e poi scendere lungo la catena dai suoi figli di sinistra fino alla foglia - in questo caso, questa catena consiste solo del nodo con la chiave 30. A rigor di termini, stiamo cercando il nodo più piccolo nell'insieme dei nodi maggiore del nodo desiderato.
Codice del metodo di ricerca successivo:
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;
}
Il codice completo del metodo delete:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или 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;
}
La complessità può essere approssimata a O(log(n)).
Trovare il massimo/minimo in un albero
Ovviamente, come trovare il valore minimo / massimo nell'albero: è necessario scorrere in sequenza rispettivamente la catena degli elementi sinistro / destro dell'albero; quando arrivi alla foglia, 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;
}
Complessità - O(log(n))
Bypass simmetrico
L'attraversamento è una visita ad ogni nodo dell'albero per farci qualcosa.
Algoritmo di attraversamento simmetrico ricorsivo:
- Esegui un'azione sul bambino sinistro
- Compi un'azione con te stesso
- Compi un'azione sul bambino giusto
Codice:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
conclusione
Finalmente! Se non ho spiegato qualcosa o non ho commenti, aspetto nei commenti. Come promesso, ecco il codice completo.
Nodo.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());
}
}
}
PS
Degenerazione a O(n)
Molti di voi avranno notato: cosa succede se fai sbilanciare l'albero? Ad esempio, inserisci i nodi nell'albero con chiavi crescenti: 1,2,3,4,5,6... Quindi l'albero ricorderà in qualche modo un elenco collegato. E sì, l’albero perderà la sua struttura ad albero e quindi l’efficienza dell’accesso ai dati. La complessità delle operazioni di ricerca, inserimento e cancellazione diventerà la stessa di una lista concatenata: O(n). Questo è uno degli svantaggi più importanti, secondo me, degli alberi binari.
Solo gli utenti registrati possono partecipare al sondaggio. Per favore.
Non sono su Habré da molto tempo e vorrei sapere quali articoli su quali argomenti ti piacerebbe vedere di più?
-
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 Java
2 utenti hanno votato. 1 utente si è astenuto.
Fonte: www.habr.com