Determinar la altura del árbol de búsqueda binaria en Java

1. el árbol de búsqueda binaria
2. Aplicación del árbol de búsqueda binaria
3. Determinar la altura del árbol de búsqueda binaria

En este artículo detallado, aprenderemos los conceptos básicos de un árbol de búsqueda binaria antes de implementar un programa de búsqueda recursiva para determinar la altura de un árbol en nuestro programa Java. Para comprender este tutorial, le recomendamos que tenga un conocimiento básico de los conceptos de estructura de datos de los árboles.

el árbol de búsqueda binaria

Mantengámoslo simple. No lo aburriremos con el extenso concepto teórico. Sin embargo, los siguientes son los conceptos básicos con los que debe estar familiarizado:

1. Una única referencia al nodo raíz de una estructura de datos jerárquica.
2. Existe un máximo de dos nodos secundarios (uno izquierdo y uno derecho) para cada nodo.
3. La función de búsqueda binaria organiza los nodos:
   • Cada nodo se ordena de acuerdo con uno o más campos de datos clave.
   • La clave de cada nodo en el árbol es mayor que la clave de su hijo izquierdo y debe ser menor que la clave de su hijo derecho.
   • Figura: Árbol de búsqueda binaria:

Aplicación del árbol de búsqueda binaria

Mantengámoslo simple. No lo aburriremos con el extenso concepto teórico.

Sin embargo, los siguientes son los conceptos básicos con los que debe estar familiarizado:

1. También puede utilizar un BST, donde el flujo y la estructura de los datos entran o salen constantemente, como los métodos map y set en la mayoría de los lenguajes de programación, incluido Java.

2. También podemos usar BST en videojuegos tridimensionales para determinar la posición de los objetos y el proceso de renderizado. Lea más sobre la partición de espacio usando BST: Partición de espacio binario.

3. Si hablamos principalmente de redes, podemos usar estos árboles en casi todos los enrutadores de gran ancho de banda para almacenar tablas de enrutadores; Intentos binarios.

4. Si está interesado en torrents y la generación única de firmas de imágenes. Suponga que desea verificar las necesidades de hash, pero el archivo completo no está disponible.

   Ahí es también donde puede hacer uso de BST. Leer más: Árboles de hachís

En pocas palabras, podemos usar árboles de búsqueda binarios en varias aplicaciones, gracias a su capacidad para ayudar a organizar los datos que queremos. Podemos hacer una indexación de varios niveles usando un árbol de búsqueda binario.

Además, también podemos usarlos para implementar diferentes algoritmos de búsqueda. Dado que los BST pueden ayudar a mantener un flujo de datos ordenado.

Determinar la altura del árbol de búsqueda binaria

Determinar la altura de un árbol de búsqueda binario no es una tarea difícil si sigue estos sencillos pasos:

1. La longitud del camino más largo desde la raíz hasta un nodo hoja determina la altura de un árbol binario. También se conoce como la profundidad de un árbol binario.

   La altura de la raíz es igual a la altura del árbol.

2. La profundidad de un nodo es la longitud del camino a su raíz.

3. Para calcular la altura del árbol, debemos contar el número de aristas entre la raíz y la hoja más lejana.

Como ves en el gráfico anterior, el número de aristas entre la raíz y la hoja más lejana es 3. Por lo tanto, la altura del árbol también es 3.

Buscar una clave específica en el árbol de búsqueda binaria

Puede buscar una clave específica en un árbol de búsqueda binaria de forma recursiva o iterativa. Ambos métodos son opciones populares para varias operaciones de estructura de datos.

Si hablamos del método de búsqueda recursiva, el proceso de búsqueda comienza con un examen del nodo raíz. En este sentido, supongamos que el árbol es nil, entonces la clave buscada no existe en el árbol.

Si el resultado de la búsqueda es exitoso, se devuelve el nodo si la clave coincide con la raíz. Sin embargo, suponga que la clave es más pequeña que la raíz y luego la búsqueda del programa se mueve al subárbol izquierdo.

Pasos recursivos para encontrar la altura del árbol de búsqueda binaria

Debe tener en cuenta que si el árbol está vacío, su altura es 0. Por el contrario, debe comenzar desde el nodo superior hacia abajo.

Supongamos que queremos determinar recursivamente la profundidad máxima del subárbol izquierdo. La profundidad máxima de estos dos es la altura del árbol binario (subárboles izquierdo y derecho).

Echa un vistazo al siguiente pseudocódigo.

BinarySearchTree(a, k)
   if a = NIL or k = a.key then
     return a
   if k < a.key then
     return Tree-Search(a.L, k)
   else
     return Tree-Search(a.R, k)
   end if

Implementemos nuestro programa recursivamente para buscar la altura dentro de un BST.

Ejemplo:

package heightofbinarysearchBSTree.delftstack;
// Java program to find the height of BSTree
// A binary BSTree BSTreeNode
public class DetHeight {
  int BSTreedata;
  DetHeight BSTreeNodeLeft, BSTreeNoderight;
  DetHeight(int i) {
    BSTreedata = i;
    BSTreeNodeLeft = BSTreeNoderight = null;
  }
}
class BST {
  DetHeight BSTreeroot;
  /* Compute the "MaximumHeight" of a BSTree -- the number of
  BSTreeNodes along the longest path from the BSTreeroot BSTreeNode
  down to the farthest leaf BSTreeNode.*/
  int MaximumHeight(DetHeight BSTreeNode) {
    if (BSTreeNode == null)
      return -1;
    else {
      /* compute the depth of each subBSTree */
      int LeftHeight = MaximumHeight(BSTreeNode.BSTreeNodeLeft);
      int Rightheight = MaximumHeight(BSTreeNode.BSTreeNoderight);

      /* use the larger one */
      if (LeftHeight > Rightheight)
        return (LeftHeight + 1);
      else
        return (Rightheight + 1);
    }
  }
  /* Driver program to test above functions */
  public static void main(String[] args) {
    BST BSTree = new BST();
    BSTree.BSTreeroot = new DetHeight(12);
    BSTree.BSTreeroot.BSTreeNodeLeft = new DetHeight(25);
    BSTree.BSTreeroot.BSTreeNoderight = new DetHeight(35);
    BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNodeLeft = new DetHeight(47);
    BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(26);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft = new DetHeight(29);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNoderight = new DetHeight(53);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(31);
    System.out.println("Height of BSTree is : " + BSTree.MaximumHeight(BSTree.BSTreeroot));
  }
}

Producción :

The height of this tree : 3

Complejidad del programa de búsqueda

En este caso particular, es lineal, ya que estamos atravesando todos los nodos del árbol binario recursivamente mientras mantenemos la altura. Por tanto, la complejidad temporal es O(N), donde N es el número de nodos del árbol.