Estructuras de datos: árbol binario en Java

Hola hola! Es difícil ser un programador fuerte sin conocimientos básicos. Y aquí nos referimos no sólo al conocimiento de la sintaxis del lenguaje de programación nativo, sino también a los fundamentos y conceptos de la programación en general. Uno de estos fundamentos son los algoritmos y las estructuras de datos. Como regla general, algunos tienen más conocimientos sobre este tema, otros menos, pero hay información básica que todos deberían saber. Entre las bases de datos para estructuras de datos, definitivamente vale la pena comprender los árboles de búsqueda binarios. De hecho, hoy veremos la estructura en sí con sus características y descubriremos cómo se puede implementar un árbol binario en Java . Primero, averigüemos qué es un árbol binario. Un árbol binario es una estructura de datos en la que cada nodo (padre) tiene como máximo dos hijos (heredero derecho e izquierdo). En la práctica, se utilizan habitualmente dos tipos de árboles binarios: árbol de búsqueda binario y pirámide (montón). Hoy veremos un árbol de búsqueda binario.

Beneficios del árbol binario

¿Cuál es la ventaja de almacenar datos como un árbol de búsqueda binario? Imaginemos que tenemos un libro de referencia de 100 páginas y necesitamos encontrar una página específica que contenga los datos que necesitamos. También sabemos por el contenido qué página específica necesitamos. Si seguimos el camino habitual, tendremos que pasar página a página hasta llegar a la que necesitamos. Es decir, pasaremos de 1 a 100 páginas hasta encontrarnos en el lugar indicado. Por ejemplo, si necesitamos la página 77, entonces tendremos 77 búsquedas. Si hablamos de complejidad temporal, entonces será O(N) . Pero esto se puede hacer de manera más eficiente, ¿verdad? Intentemos hacer lo mismo, pero usando búsqueda binaria :

1. Dividimos el directorio en dos partes, la primera, del 1 al 50, la segunda, del 51 al 100. Sabemos exactamente en cuál de estas partes está nuestra página: si volvemos a tomar la página 77, está en la segunda parte del libro.
2. A continuación, consideramos la segunda parte y la dividimos en dos: de 51 a 75, de 76 a 100. En este caso, nuestra página volverá a estar en la segunda mitad, en el rango 76-100.
3. Luego dividimos este intervalo por 2 y obtenemos 76-88 y 89-100. La página encaja en el primer espacio, por lo que descartamos el segundo.
4. Los siguientes son los intervalos: 76-81 y 82-88, toma el primero.
5. 76-78 y 79-81, toma el primero.
6. 76 y 77-78, toma el segundo.
7. 77 y 78, tome el primero y obtenga nuestra página: 77.

¡En lugar de 77 pasos, solo necesitábamos 7! La complejidad temporal de esta búsqueda será O(log(N)) .

Reglas para construir un árbol de búsqueda binario

El árbol de búsqueda binaria se construye según ciertas reglas:

• cada nodo tiene como máximo dos hijos;
• cada valor menor que el valor del nodo se convierte en el hijo izquierdo o en el hijo del hijo izquierdo;
• cada valor mayor o igual al valor del nodo se convierte en el hijo correcto o en el hijo del hijo correcto.

Por ejemplo, tenemos una serie de números del 1 al 10. Veamos cómo se verá el árbol de búsqueda binario para esta serie: Pensemos si aquí se cumplen todas las condiciones de un árbol binario:

• todos los nodos no tienen más de dos herederos, se cumple la primera condición;
• Si consideramos, por ejemplo, un nodo con el valor 7 (o cualquier otro), veremos que todos los valores de los elementos en el subárbol izquierdo serán menores y en el derecho, más. Esto significa que se cumplen las condiciones 2 y 3.

Veamos cómo ocurren las operaciones básicas: inserción, eliminación, búsqueda.

Buscar un elemento

Al buscar un elemento con un valor determinado, comenzamos en el elemento raíz:

1. Si es igual al valor buscado, el elemento raíz es el buscado; si no, comparamos los valores de la raíz y el buscado.
2. Si el elemento que buscamos es más grande, pasamos al hijo derecho; si no, pasamos al hijo izquierdo.
3. Si no se encuentra el elemento, aplique los pasos 1 y 2, pero al hijo (derecha o izquierda) hasta que encuentre el elemento.

Por ejemplo, en el árbol de búsqueda binario que se muestra arriba, queremos encontrar el elemento con el valor 5:

• lo comparamos con el elemento raíz, vemos que el elemento raíz es más grande, entonces pasamos al hijo izquierdo, que tiene un valor de 3;
• comparamos el que buscamos y el elemento con valor 3, vemos que el que buscamos es más grande, por lo que necesitamos el descendiente derecho del elemento en cuestión, es decir, el elemento con valor 5;
• Comparamos este descendiente con el que estamos buscando y vemos que los valores son iguales: se encuentra el elemento.

Insertando un elemento

El algoritmo de inserción también es muy, muy sencillo:

1. Comparamos el nuevo con el raíz (si no existe, el nuevo elemento es el raíz).

2. Si un nuevo elemento:

   • es menor, entonces vamos al heredero izquierdo, si no hay ninguno, el nuevo elemento toma el lugar del heredero izquierdo y se completa el algoritmo;
   • es mayor o igual que la raíz, entonces pasamos al heredero derecho. Y de manera similar, si este elemento no existe, entonces un nuevo elemento ocupará el lugar del elemento correcto y se completará el algoritmo.

3. Para el nuevo elemento en cuestión, que estaba a la derecha o a la izquierda del paso anterior, repita los pasos 1 y 2 hasta que el elemento insertado esté en su lugar.

   Como ejemplo, querremos insertar en el árbol considerado anteriormente, un elemento con el valor 11:

   • comparamos con el elemento raíz 7 y vemos que el elemento raíz es más pequeño, por lo que pasamos al heredero derecho;
   • el siguiente elemento considerado tiene un valor de 9, que es menor que el nuevo 11, por lo que pasamos al heredero derecho;
   • el heredero derecho tiene un valor de 10, que nuevamente es menor, entonces vamos al primer elemento, y como no está, se coloca en este lugar un nuevo elemento con un valor de 11.
   ↓

Eliminando un elemento

Quizás, de todas las operaciones con árboles de búsqueda binarios, la eliminación sea la más difícil. En primer lugar se busca el elemento a eliminar, tras lo cual sigue una etapa que puede tener tres variaciones:

1. El nodo que se va a eliminar es un nodo hoja (no tiene hijos).

   Quizás el más sencillo. Todo se reduce al hecho de que simplemente lo cortamos del árbol, sin manipulación innecesaria. Por ejemplo, de nuestro árbol eliminamos el nodo con el valor 8:

   ↓

2. El nodo que se está eliminando tiene un hijo.

   En este caso, eliminamos el nodo seleccionado y colocamos su descendiente en su lugar (en esencia, simplemente cortamos el nodo seleccionado de la cadena). Como ejemplo, eliminemos un nodo con valor 9 del árbol:

   ↓

3. El nodo que se está eliminando tiene dos hijos.

   La parte más interesante. Después de todo, si el nodo que se está eliminando tiene dos hijos a la vez, no se puede simplemente reemplazarlo con uno de estos hijos (especialmente si el hijo tiene sus propios hijos).

   Ejemplo: en el árbol de arriba, ¿qué nodo debería ser el hijo izquierdo del nodo 3?

   Si lo piensas un poco, resulta obvio que este debería ser un nodo con un valor de 4. Pero, ¿y si el árbol no es tan simple? Si tiene cientos de valores, ¿será tan fácil determinar quién será el sucesor?

   Está claro que no. Por lo tanto, necesitamos nuestro propio algoritmo de búsqueda de receptores pequeños:

   1. Primero debemos ir al hijo derecho del nodo seleccionado, cuyo valor debe ser mayor que el valor del nodo.
   2. Luego vamos al hijo izquierdo del hijo derecho (si existe), luego al hijo izquierdo del hijo izquierdo, etc., siguiendo la cadena de hijos izquierdos.
   3. En consecuencia, el último hijo que quede en este camino será el sucesor del nodo original.

   Generalicemos un poco este pequeño algoritmo: en el subárbol del hijo derecho del nodo de origen, todos los nodos son más grandes que el que se elimina, lo que se puede entender a partir de las reglas básicas del árbol de búsqueda binaria. En este subárbol buscamos el valor más pequeño.

   En otras palabras, buscamos el nodo más pequeño en un conjunto de nodos más grandes que el nodo original. Este nodo más pequeño entre los más grandes será el sucesor más adecuado.

   Cómo se verá el árbol después de eliminar el nodo con valor 3:

   ↓

Ahora es el momento de pasar de la práctica a la teoría. Echemos un vistazo a cómo podemos mapear esta estructura de datos en Java. Clase de nodo único:

class Node {
   private int value; // ключ узла
   private Node leftChild; // Левый узел потомок
   private Node rightChild; // Правый узел потомок

   public void printNode() { // Вывод значения узла в консоль
       System.out.println(" Выбранный узел имеет significado :" + value);
   }

   public int getValue() {
       return this.value;
   }

   public void setValue(final int value) {
       this.value = value;
   }

   public Node getLeftChild() {
       return this.leftChild;
   }

   public void setLeftChild(final Node leftChild) {
       this.leftChild = leftChild;
   }

   public Node getRightChild() {
       return this.rightChild;
   }

   public void setRightChild(final Node rightChild) {
       this.rightChild = rightChild;
   }

   @Override
   public String toString() {
       return "Node{" +
               "value=" + value +
               ", leftChild=" + leftChild +
               ", rightChild=" + rightChild +
               '}';
   }
}

Nada demasiado complicado: cada elemento tiene un vínculo con su hijo izquierdo y derecho. Y ahora, quizás, la clase más importante sea la clase de árbol:

class Tree {
   private Node rootNode; // корневой узел

   public Tree() { // Пустое дерево
       rootNode = null;
   }

   public Node findNodeByValue(int value) { // поиск узла по значению
       Node currentNode = rootNode; // начинаем поиск с корневого узла
       while (currentNode.getValue() != value) { // поиск покуда не будет найден элемент o не будут перебраны все
           if (value < currentNode.getValue()) { // движение влево?
               currentNode = currentNode.getLeftChild();
           } else { //движение вправо
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null) { // если потомка нет,
               return null; // возвращаем null
           }
       }
       return currentNode; // возвращаем найденный элемент
   }

   public void insertNode(int value) { // метод вставки нового elemento
       Node newNode = new Node(); // создание нового узла
       newNode.setValue(value); // вставка данных
       if (rootNode == null) { // если корневой узел не существует
           rootNode = newNode;// то новый элемент и есть корневой узел
       }
       else { // корневой узел занят
           Node currentNode = rootNode; // начинаем с корневого узла
           Node parentNode;
           while (true) // мы имеем внутренний выход из цикла
           {
               parentNode = currentNode;
               if(value == currentNode.getValue()) {   // если такой элемент в дереве уже есть, не сохраняем его
                    return;    // просто выходим из метода
                }
                else  if (value < currentNode.getValue()) {   // движение влево?
                   currentNode = currentNode.getLeftChild();
                   if (currentNode == null){ // если был достигнут конец цепочки,
                       parentNode.setLeftChild(newNode); //  то вставить слева и выйти из методы
                       return;
                   }
               }
               else { // Или направо?
                   currentNode = currentNode.getRightChild();
                   if (currentNode == null) { // если был достигнут конец цепочки,
                       parentNode.setRightChild(newNode);  //то вставить справа
                       return; // и выйти
                   }
               }
           }
       }
   }

   public boolean deleteNode(int value) // Удаление узла с заданным ключом
   {
       Node currentNode = rootNode;
       Node parentNode = rootNode;
       boolean isLeftChild = true;
       while (currentNode.getValue() != value) { // начинаем поиск узла
           parentNode = currentNode;
           if (value < currentNode.getValue()) { // Определяем, нужно ли движение влево?
               isLeftChild = true;
               currentNode = currentNode.getLeftChild();
           }
           else { // o движение вправо?
               isLeftChild = false;
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null)
               return false; // yзел не найден
       }

       if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { // узел просто удаляется, если не имеет потомков
           if (currentNode == rootNode) // если узел - корень, то дерево очищается
               rootNode = null;
           else if (isLeftChild)
               parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя
           else
               parentNode.setRightChild(null);
       }
       else if (currentNode.getRightChild() == null) { // узел заменяется левым поддеревом, если правого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getLeftChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getLeftChild());
           else
               parentNode.setRightChild(currentNode.getLeftChild());
       }
       else if (currentNode.getLeftChild() == null) { // узел заменяется правым поддеревом, если левого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getRightChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getRightChild());
           else
               parentNode.setRightChild(currentNode.getRightChild());
       }
       else { // если есть два потомка, узел заменяется преемником
           Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла
           if (currentNode == rootNode)
               rootNode = heir;
           else if (isLeftChild)
               parentNode.setLeftChild(heir);
           else
               parentNode.setRightChild(heir);
       }
       return true; // элемент успешно удалён
   }

   // метод возвращает узел со следующим significadoм после передаваемого аргументом.
   // для этого он сначала переходим к правому потомку, а затем
   // отслеживаем цепочку левых потомков этого узла.
   private Node receiveHeir(Node node) {
       Node parentNode = node;
       Node heirNode = node;
       Node currentNode = node.getRightChild(); // Переход к правому потомку
       while (currentNode != null) // Пока остаются левые потомки
       {
           parentNode = heirNode;// потомка задаём Cómo текущий узел
           heirNode = currentNode;
           currentNode = currentNode.getLeftChild(); // переход к левому потомку
       }
       // Если преемник не является
       if (heirNode != node.getRightChild()) // правым потомком,
       { // создать связи между узлами
           parentNode.setLeftChild(heirNode.getRightChild());
           heirNode.setRightChild(node.getRightChild());
       }
       return heirNode;// возвращаем приемника
   }

   public void printTree() { // метод для вывода дерева в консоль
       Stack globalStack = new Stack(); // общий стек для значений дерева
       globalStack.push(rootNode);
       int gaps = 32; // начальное significado расстояния между elementoми
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack localStack = new Stack(); // локальный стек для задания потомков elemento
           isRowEmpty = true;

           for (int j = 0; j < gaps; j++)
               System.out.print(' ');
           while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
               Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека
               if (temp != null) {
                   System.out.print(temp.getValue()); // выводим его significado в консоли
                   localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего elemento
                   localStack.push(temp.getRightChild());
                   if (temp.getLeftChild() != null ||
                           temp.getRightChild() != null)
                       isRowEmpty = false;
               }
               else {
                   System.out.print("__");// - если элемент пустой
                   localStack.push(null);
                   localStack.push(null);
               }
               for (int j = 0; j < gaps * 2 - 2; j++)
                   System.out.print(' ');
           }
           System.out.println();
           gaps /= 2;// при переходе на следующий уровень расстояние между elementoми каждый раз уменьшается
           while (localStack.isEmpty() == false)
               globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
       }
       System.out.println(separator);// подводим черту
   }
}

De nuevo, nada demasiado complicado. Las operaciones del árbol de búsqueda binaria descritas anteriormente están presentes, además de un método para mostrar el árbol en la consola. Bueno, ahora echemos un vistazo al árbol en acción:

public class Application {
   public static void main(String[] args) {
       Tree tree = new Tree();
       // вставляем узлы в дерево:
       tree.insertNode(6);
       tree.insertNode(8);
       tree.insertNode(5);
       tree.insertNode(8);
       tree.insertNode(2);
       tree.insertNode(9);
       tree.insertNode(7);
       tree.insertNode(4);
       tree.insertNode(10);
       tree.insertNode(3);
       tree.insertNode(1);
       // отображение дерева:
       tree.printTree();

       // удаляем один узел и выводим оставшееся дерево в консоли
       tree.deleteNode(5);
       tree.printTree();

       // находим узел по значению и выводим его в консоли
       Node foundNode = tree.findNodeByValue(7);
       foundNode.printNode();
   }
}

Las operaciones de búsqueda/inserción/eliminación en un árbol de búsqueda binario tienen una complejidad temporal de O(log(N)) . Pero ese es el mejor de los casos. En general, la complejidad temporal de las operaciones varía de O(log(N)) a O(N) . Depende del grado de degeneración del árbol.

¿Qué es un árbol degenerado?

Este es el árbol en el que cayeron los elementos cuando se agregaron a la posición del nodo más a la izquierda (número más pequeño) o al nodo más grande (más grande). Esto puede suceder si, por ejemplo, todo el árbol de la izquierda está vacío en cada nivel, solo hay árboles de la derecha, en cuyo caso el árbol degenera en una lista (yendo hacia la derecha). Sí, así es como un árbol degenerado se convierte efectivamente en una lista enlazada individualmente, en la que cada elemento sólo conoce el que está al lado. En este caso, todas las operaciones en esta estructura se acercan a la complejidad temporal de O(N) .

¿En qué caso un árbol puede degenerar?

Por ejemplo, si agrega una lista de elementos ordenados. Si la lista está ordenada en orden ascendente, entonces la raíz será la primera y, respectivamente, la más pequeña. El siguiente después de él tomará la posición del niño correcto. Y el que viene después será más grande que el segundo y ocupará la posición de su sucesor derecho, y así sucesivamente... Si la lista está en orden descendente, entonces sucederá lo mismo, pero con los elementos más a la izquierda. Para evitar esto, después de recibir una serie de elementos, simplemente puedes mezclarlos. Entonces la clasificación desaparecerá y los números estarán más o menos uniformemente dispersos por todo el árbol. Eso es todo por hoy, ¡gracias por su atención!