Preludio
Este artigo trata sobre árbores de busca binarias. Recentemente escribín un artigo sobre Alí realmente non prestei atención ás árbores binarias, porque os métodos de busca, inserción e eliminación non eran relevantes. Agora decidín escribir un artigo sobre árbores. Quizais empecemos.
Unha árbore é unha estrutura de datos formada por nós conectados por bordos. Podemos dicir que unha árbore é un caso especial dun gráfico. Aquí tes un exemplo de árbore:
Esta non é unha árbore de busca binaria! Todo está baixo o corte!
Terminoloxía
Root
Raíz da árbore é o nodo máis alto. No exemplo, este é o nodo A. Na árbore, só un camiño pode levar desde a raíz a calquera outro nodo. De feito, calquera nodo pode ser considerado como a raíz da subárbore correspondente a este nodo.
Pais/fillos
Todos os nodos excepto a raíz teñen exactamente un bordo que conduce a outro nodo. Chámase o nodo por riba do actual pai este nodo. Chámase un nodo situado debaixo do actual e conectado a el descendente este nodo. Poñamos un exemplo. Tome o nodo B, entón o seu pai será o nodo A e os seus fillos serán os nós D, E e F.
Folla
Un nodo que non ten fillos chámase folla da árbore. No exemplo, os nós D, E, F, G, I, J, K serán follas.
Esta é a terminoloxía básica. Outros conceptos comentaranse máis adiante. Así, unha árbore binaria é unha árbore na que cada nodo non terá máis de dous fillos. Como adiviñaches, a árbore do exemplo non será binaria, porque os nós B e H teñen máis de dous fillos. Aquí tes un exemplo de árbore binaria:
Os nodos da árbore poden conter calquera información. Unha árbore de busca binaria é unha árbore binaria que ten as seguintes propiedades:
- Ambas as subárbores esquerda e dereita son árbores de busca binarias.
- Todos os nós da subárbore esquerda dun nodo X arbitrario teñen valores de clave de datos inferiores ao valor da clave de datos do propio nodo X.
- Todos os nós da subárbore dereita dun nodo X arbitrario teñen valores de clave de datos superiores ou iguais ao valor da clave de datos do propio nodo X.
Clave - algunha característica do nodo (por exemplo, un número). A clave é necesaria para poder atopar o elemento da árbore ao que corresponde esta chave. Exemplo de árbore de busca binaria:
vista en árbore
A medida que vaia, incluirei algunhas pezas de código (quizais incompletas) para mellorar a súa comprensión. O código completo estará ao final do artigo.
A árbore está formada por nós. Estrutura do nodo:
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;
}
//...остальные методы узла
}
Cada nodo ten dous fillos (é moi posible que os fillos leftChild e/ou rightChild sexan nulos). Probablemente entendeses que neste caso os datos numéricos son os datos almacenados no nodo; clave - clave de nodo.
Descubrimos o nó, agora imos falar dos problemas acuciantes das árbores. Aquí e abaixo, a palabra "árbore" significará o concepto de árbore de busca binaria. Estrutura da árbore binaria:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Como campo de clase, só necesitamos a raíz da árbore, porque desde a raíz, usando os métodos getLeftChild() e getRightChild(), podes chegar a calquera nodo da árbore.
Algoritmos de árbores
Procurar
Digamos que tes unha árbore construída. Como atopar un elemento coa chave? Debe moverse secuencialmente desde a raíz cara abaixo na árbore e comparar o valor da clave coa clave do seguinte nodo: se a clave é menor que a clave do seguinte nodo, vaia ao descendente esquerdo do nodo, se máis - á dereita, se as claves son iguais - atópase o nodo desexado. Código relevante:
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 a corrente pasa a ser nula, entón a iteración chegou ao final da árbore (a nivel conceptual, estás nun lugar inexistente da árbore: un fillo dunha folla).
Considere a eficiencia do algoritmo de busca nunha árbore equilibrada (unha árbore na que os nós están distribuídos de forma máis ou menos uniforme). Entón a eficiencia da busca será O(log(n)), e o logaritmo de base 2. Vexa: se hai n elementos nunha árbore equilibrada, isto significa que haberá niveis log(n) de base 2 da árbore. E na procura dun paso do ciclo, baixas un nivel.
inserir
Se entendeu a esencia da busca, non lle será difícil comprender a inserción. Só tes que baixar ata a folla da árbore (segundo as regras de descenso descritas na busca) e converterte no seu descendente - á esquerda ou á dereita, dependendo da clave. Implementación:
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;
}
}
}
}
}
Neste caso, ademais do nodo actual, é necesario almacenar información sobre o pai do nodo actual. Cando a corrente pasa a ser nula, a variable pai conterá a folla que necesitamos.
A eficiencia de inserción será obviamente a mesma que a da busca - O(log(n)).
Eliminar
A eliminación é a operación máis complexa que haberá que facer cunha árbore. Está claro que primeiro será necesario atopar o elemento que imos eliminar. Pero entón que? Se simplemente establecemos a súa referencia como nula, perderemos información sobre a subárbore cuxa raíz é este nodo. Os métodos de eliminación de árbores divídense en tres casos.
Primeiro caso. O nodo que se vai eliminar non ten fillos.
Se o nodo que se vai eliminar non ten fillos, significa que é unha folla. Polo tanto, pode simplemente establecer os campos leftChild ou rightChild do seu pai como nulos.
Segundo caso. O nodo que se vai eliminar ten un fillo
Este caso tampouco é moi difícil. Volvamos ao noso exemplo. Supoñamos que necesitamos eliminar un elemento coa clave 14. Acordamos que, dado que é o fillo correcto dun nodo coa clave 10, calquera dos seus descendentes (neste caso, o correcto) terá unha clave superior a 10, polo que pode ser "cortada" facilmente da árbore, e o pai pode conectarse directamente ao fillo do nodo que se elimina, é dicir. conectar o nodo coa chave 10 ao nodo 13. A situación sería semellante se tivésemos que eliminar un nodo que é o fillo esquerdo do seu pai. Pense niso por si mesmo - unha analoxía exacta.
Terceiro caso. Node ten dous fillos
O caso máis difícil. Vexamos un novo exemplo.
Busca un sucesor
Digamos que hai que eliminar o nodo coa chave 25. A quen poñeremos no seu lugar? Un dos seus seguidores (descendentes ou descendentes de descendentes) debe converterse sucesor(o que ocupará o lugar do nodo eliminado).
Como sabes quen debe ser o sucesor? Intuitivamente, este é o nodo da árbore cuxa clave é a seguinte máis grande do nodo que se elimina. O algoritmo é o seguinte. Cómpre ir ao seu fillo dereito (sempre ao dereito, porque xa se dixo que a clave do sucesor é maior que a clave do nodo que se borra), e despois pasar pola cadea de fillos esquerdos deste fillo dereito. No exemplo, temos que navegar ata o nodo coa tecla 35 e, a continuación, percorrer a cadea dos seus fillos esquerdos ata a folla; neste caso, esta cadea consiste só no nodo coa clave 30. En rigor, estamos a buscar o nodo máis pequeno do conxunto de nodos máis grandes que o nodo desexado.
Código do método de busca sucesor:
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;
}
O código completo do método de eliminación:
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;
}
A complexidade pódese aproximar a O(log(n)).
Atopar o máximo/mínimo nunha árbore
Obviamente, como atopar o valor mínimo / máximo na árbore - cómpre percorrer secuencialmente a cadea de elementos esquerda / dereita da árbore, respectivamente; cando chegue á folla, será o elemento mínimo/máximo.
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;
}
Complexidade - O(log(n))
Bypass simétrico
A travesía é unha visita a cada nó da árbore para facer algo con el.
Algoritmo de travesía simétrica recursiva:
- Fai unha acción no fillo esquerdo
- Fai unha acción contigo mesmo
- Fai unha acción sobre o neno axeitado
Código:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Conclusión
Por fin! Se non expliquei algo ou teño algún comentario, estou esperando nos comentarios. Como prometeu, aquí está o código 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());
}
}
}
PS
Dexeneración a O(n)
Moitos de vós se decatarades: e se desequilibrades a árbore? Por exemplo, coloque nodos na árbore con claves crecentes: 1,2,3,4,5,6... Entón a árbore lembrará un pouco unha lista ligada. E si, a árbore perderá a súa estrutura en árbore e, polo tanto, a eficiencia do acceso aos datos. A complexidade das operacións de busca, inserción e eliminación pasará a ser a mesma que a dunha lista ligada: O(n). Esta é unha das desvantaxes máis importantes, na miña opinión, das árbores binarias.
Só os usuarios rexistrados poden participar na enquisa. , por favor.
Hai bastante tempo que non entro en Habré, e gustaríame saber que artigos sobre que temas che gustaría ver máis?
-
Estruturas de datos
-
Algoritmos (DP, recursión, compresión de datos, etc.)
-
Aplicación de estruturas de datos e algoritmos na vida real
-
Programación de aplicaciones de Android en Java
-
Programación de aplicacións web Java
Votaron 2 usuarios. 1 usuario abstívose.
Fonte: www.habr.com