Preludio
Este artículo trata sobre árboles de búsqueda binarios. Hace poco escribí un artículo sobre Allí realmente no presté atención a los árboles binarios, porque los métodos de búsqueda, inserción y eliminación no eran relevantes. Ahora decidí escribir un artículo sobre árboles. Quizás empecemos.
Un árbol es una estructura de datos que consta de nodos conectados por aristas. Podemos decir que un árbol es un caso especial de un grafo. Aquí hay un árbol de ejemplo:
¡Este no es un árbol de búsqueda binario! ¡Todo está bajo el corte!
Vocabulario
raíz
Raíz del arbol es el nodo superior. En el ejemplo, este es el nodo A. En el árbol, ¡solo un camino puede conducir desde la raíz a cualquier otro nodo! De hecho, cualquier nodo puede ser considerado como la raíz del subárbol correspondiente a este nodo.
Padres/descendencia
Todos los nodos, excepto la raíz, tienen exactamente un borde que conduce a otro nodo. El nodo por encima del nodo actual se llama padre este nodo. Un nodo ubicado debajo del actual y conectado a él se llama descendiente este nodo. Tomemos un ejemplo. Tome el nodo B, entonces su padre será el nodo A y sus hijos serán los nodos D, E y F.
Hoja
Un nodo que no tiene hijos se llama hoja del árbol. En el ejemplo, los nodos D, E, F, G, I, J, K serán hojas.
Esta es la terminología básica. Más adelante se discutirán otros conceptos. Entonces, un árbol binario es un árbol en el que cada nodo no tendrá más de dos hijos. Como habrás adivinado, el árbol del ejemplo no será binario, porque los nodos B y H tienen más de dos hijos. Aquí hay un ejemplo de un árbol binario:
Los nodos del árbol pueden contener cualquier información. Un árbol de búsqueda binario es un árbol binario que tiene las siguientes propiedades:
- Los subárboles izquierdo y derecho son árboles de búsqueda binarios.
- Todos los nodos del subárbol izquierdo de un nodo X arbitrario tienen valores de clave de datos menores que el valor de clave de datos del propio nodo X.
- Todos los nodos del subárbol derecho de un nodo X arbitrario tienen valores de clave de datos mayores o iguales que el valor de la clave de datos del propio nodo X.
Llave - alguna característica del nodo (por ejemplo, un número). La clave es necesaria para poder encontrar el elemento del árbol al que corresponde esta clave. Ejemplo de árbol de búsqueda binaria:
vista de árbol
A medida que avance, incluiré algunos fragmentos de código (quizás incompletos) para mejorar su comprensión. El código completo estará al final del artículo.
El árbol está formado por nodos. Estructura del 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 tiene dos hijos (es muy posible que los hijos leftChild y/o rightChild sean nulos). Probablemente entendiste que en este caso los datos numéricos son los datos almacenados en el nodo; clave - clave de nodo.
Descubrimos el nudo, ahora hablemos de los problemas urgentes de los árboles. En adelante, la palabra "árbol" significará el concepto de un árbol de búsqueda binaria. Estructura de árbol binario:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Como campo de clase, solo necesitamos la raíz del árbol, porque desde la raíz, usando los métodos getLeftChild() y getRightChild(), puede llegar a cualquier nodo del árbol.
Algoritmos de árbol
búsqueda
Digamos que tienes un árbol construido. ¿Cómo encontrar el elemento con clave clave? Debe moverse secuencialmente desde la raíz hacia abajo en el árbol y comparar el valor de la clave con la clave del siguiente nodo: si la clave es menor que la clave del siguiente nodo, vaya al descendiente izquierdo del nodo, si es más: a la derecha, si las claves son iguales, ¡se encuentra el nodo deseado! 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;
}
Si la corriente se vuelve nula, entonces la iteración ha llegado al final del árbol (a nivel conceptual, se encuentra en un lugar inexistente en el árbol: un hijo de una hoja).
Considere la eficiencia del algoritmo de búsqueda en un árbol equilibrado (un árbol en el que los nodos se distribuyen de manera más o menos uniforme). Entonces la eficiencia de búsqueda será O(log(n)), y el logaritmo de base 2. Ver: si hay n elementos en un árbol balanceado, entonces esto significa que habrá log(n) niveles de base 2 del árbol. Y en la búsqueda, por un paso del ciclo, bajas un nivel.
insertar
Si ha captado la esencia de la búsqueda, no le resultará difícil comprender la inserción. Solo necesita bajar a la hoja del árbol (de acuerdo con las reglas de descenso descritas en la búsqueda) y convertirse en su descendiente, izquierda o derecha, según la 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;
}
}
}
}
}
En este caso, además del nodo actual, es necesario almacenar información sobre el padre del nodo actual. Cuando actual se vuelve nulo, la variable principal contendrá la hoja que necesitamos.
La eficiencia de inserción será obviamente la misma que la de la búsqueda - O(log(n)).
Eliminación
La eliminación es la operación más compleja que deberá realizarse con un árbol. Está claro que primero habrá que encontrar el elemento que vamos a eliminar. ¿Pero entonces, qué? Si simplemente establecemos su referencia en nulo, perderemos información sobre el subárbol cuya raíz es este nodo. Los métodos de eliminación de árboles se dividen en tres casos.
Primer caso. El nodo que se eliminará no tiene hijos.
Si el nodo a eliminar no tiene hijos, significa que es una hoja. Por lo tanto, simplemente puede establecer los campos de niño izquierdo o niño derecho de su padre en nulo.
Segundo caso. El nodo a eliminar tiene un hijo.
Este caso tampoco es muy difícil. Volvamos a nuestro ejemplo. Supongamos que necesitamos eliminar un elemento con clave 14. Acuerde que dado que es el hijo derecho del nodo con clave 10, cualquiera de sus descendientes (en este caso, el derecho) tendrá una clave mayor que 10, por lo que puede "cortarlo" fácilmente del árbol y conectar el padre directamente al hijo del nodo que se está eliminando, es decir conecte el nodo con la clave 10 al nodo 13. La situación sería similar si tuviéramos que eliminar un nodo que es el hijo izquierdo de su padre. Piénselo usted mismo: una analogía exacta.
Tercer caso. El nodo tiene dos hijos.
El caso más difícil. Echemos un vistazo a un nuevo ejemplo.
Buscar un sucesor
Digamos que necesitamos eliminar el nodo con la clave 25. ¿A quién pondremos en su lugar? Uno de sus seguidores (descendientes o descendientes de descendientes) debe convertirse sucesor(el que tomará el lugar del nodo eliminado).
¿Cómo saber quién debe ser el sucesor? Intuitivamente, este es el nodo en el árbol cuya clave es la siguiente más grande del nodo que se está eliminando. El algoritmo es como sigue. Debe ir a su hijo derecho (siempre a la derecha, porque ya se dijo que la clave del sucesor es mayor que la clave del nodo que se está eliminando), y luego recorrer la cadena de hijos izquierdos de este derecho niño. En el ejemplo, debemos ir al nodo con la clave 35 y luego descender por la cadena de sus hijos izquierdos hasta la hoja; en este caso, esta cadena consta solo del nodo con la clave 30. Estrictamente hablando, estamos buscando el nodo más pequeño en el conjunto de nodos mayor que el nodo deseado.
Código del método de búsqueda del 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;
}
El código completo del 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;
}
La complejidad se puede aproximar a O(log(n)).
Encontrar el máximo/mínimo en un árbol
Obviamente, cómo encontrar el valor mínimo / máximo en el árbol: debe recorrer secuencialmente la cadena de elementos izquierdo / derecho del árbol, respectivamente; cuando llegue a la hoja, será el 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;
}
Complejidad - O(log(n))
Derivación simétrica
El recorrido es una visita a cada nodo del árbol para hacer algo con él.
Algoritmo de recorrido simétrico recursivo:
- Hacer una acción en el niño izquierdo
- Haz una acción contigo mismo
- Hacer una acción en el niño correcto
Código:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Conclusión
¡Finalmente! Si no expliqué algo o no tengo ningún comentario, entonces estoy esperando en los comentarios. Como prometí, aquí está el código 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;
}
}
ÁrbolBinario.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
Degeneración a O(n)
Muchos de ustedes se habrán dado cuenta: ¿y si desequilibran el árbol? Por ejemplo, coloque nodos en el árbol con claves crecientes: 1,2,3,4,5,6... Entonces el árbol recordará un poco a una lista enlazada. Y sí, el árbol perderá su estructura de árbol y, por lo tanto, la eficiencia del acceso a los datos. La complejidad de las operaciones de búsqueda, inserción y eliminación será la misma que la de una lista enlazada: O(n). Esta es una de las desventajas más importantes, en mi opinión, de los árboles binarios.
Solo los usuarios registrados pueden participar en la encuesta. por favor
Hace mucho tiempo que no estoy en Habré y me gustaría saber qué artículos sobre qué temas les gustaría ver más.
-
Estructuras de datos
-
Algoritmos (DP, recursión, compresión de datos, etc.)
-
Aplicación de estructuras de datos y algoritmos en la vida real
-
Programación de aplicaciones android en Java
-
Programación de aplicaciones web Java
2 usuarios votaron. 1 usuario se abstuvo.
Fuente: www.habr.com