Saltar al contenido

Árbol – javatpoint

septiembre 29, 2021
tree

Leemos las estructuras de datos lineales como una matriz, lista enlazada, pila y cola en la que todos los elementos están ordenados de manera secuencial. Las diferentes estructuras de datos se utilizan para diferentes tipos de datos.

Se consideran algunos factores para elegir la estructura de datos:

  • Qué tipo de datos deben almacenarse?: Es posible que una determinada estructura de datos sea la más adecuada para algún tipo de datos.
  • Costo de operaciones: Si queremos minimizar el costo de las operaciones para las operaciones que se realizan con mayor frecuencia. Por ejemplo, tenemos una lista simple en la que tenemos que realizar la operación de búsqueda; Luego, podemos crear una matriz en la que los elementos se almacenan en orden ordenado para realizar la búsqueda binaria. La búsqueda binaria funciona muy rápido para la lista simple, ya que divide el espacio de búsqueda a la mitad.
  • Uso de memoria: A veces, queremos una estructura de datos que utilice menos memoria.

Un árbol es también una de las estructuras de datos que representan datos jerárquicos. Supongamos que queremos mostrar a los empleados y sus posiciones en forma jerárquica, entonces se puede representar como se muestra a continuación:

Árbol

El árbol de arriba muestra el jerarquía organizativa de alguna empresa. En la estructura anterior, John es el CEO de la empresa, y John tiene dos informes directos nombrados como Steve y Rohan. Steve tiene tres informes directos llamados Lee, Bob, Ella dónde Steve es gerente. Bob tiene dos informes directos llamados Sal y Emma. Emma tiene dos subordinados directos llamados Tomás y Raj. Tom tiene un subordinado directo llamado Factura. Esta estructura lógica particular se conoce como Árbol. Su estructura es similar a la del árbol real, por lo que se denomina Árbol. En esta estructura, el raíz está en la parte superior y sus ramas se mueven hacia abajo. Por tanto, podemos decir que la estructura de datos Tree es una forma eficiente de almacenar los datos de forma jerárquica.

Entendamos algunos puntos clave de la estructura de datos del árbol.

  • Una estructura de datos de árbol se define como una colección de objetos o entidades conocidas como nodos que están vinculados entre sí para representar o simular una jerarquía.
  • Una estructura de datos de árbol es una estructura de datos no lineal porque no se almacena de forma secuencial. Es una estructura jerárquica, ya que los elementos de un árbol se organizan en varios niveles.
  • En la estructura de datos de árbol, el nodo superior se conoce como nodo raíz. Cada nodo contiene algunos datos y los datos pueden ser de cualquier tipo. En la estructura de árbol anterior, el nodo contiene el nombre del empleado, por lo que el tipo de datos sería una cadena.
  • Cada nodo contiene algunos datos y el enlace o referencia de otros nodos que se pueden llamar hijos.

Algunos términos básicos utilizados en la estructura de datos del árbol.

Consideremos la estructura del árbol, que se muestra a continuación:

Árbol

En la estructura anterior, cada nodo está etiquetado con algún número. Cada flecha que se muestra en la figura anterior se conoce como Enlace entre los dos nodos.

  • Raíz: El nodo raíz es el nodo superior en la jerarquía del árbol. En otras palabras, el nodo raíz es el que no tiene ningún padre. En la estructura anterior, el nodo numerado 1 es el nodo raíz del árbol. Si un nodo está directamente vinculado a otro nodo, se llamaría relación padre-hijo.
  • Nodo hijo: Si el nodo es descendiente de cualquier nodo, entonces el nodo se conoce como nodo hijo.
  • Padre: Si el nodo contiene algún subnodo, se dice que ese nodo es el padre de ese subnodo.
  • Hermano: Los nodos que tienen el mismo padre se conocen como hermanos.
  • Nodo de hoja: – El nodo del árbol, que no tiene ningún nodo hijo, se llama nodo hoja. Un nodo hoja es el nodo más inferior del árbol. Puede haber cualquier número de nodos hoja presentes en un árbol general. Los nodos hoja también se pueden llamar nodos externos.
  • Nodos internos: Un nodo tiene al menos un nodo hijo conocido como interno
  • Nodo ancestro: – Un ancestro de un nodo es cualquier nodo predecesor en una ruta desde la raíz hasta ese nodo. El nodo raíz no tiene antepasados. En el árbol que se muestra en la imagen de arriba, los nodos 1, 2 y 5 son los antepasados ​​del nodo 10.
  • Descendiente: El sucesor inmediato del nodo dado se conoce como descendiente de un nodo. En la figura anterior, 10 es el descendiente del nodo 5.

Propiedades de la estructura de datos del árbol

  • Estructura de datos recursiva: El árbol también se conoce como estructura de datos recursiva. Un árbol se puede definir de forma recursiva porque el nodo distinguido en una estructura de datos de árbol se conoce como nodo raíz. El nodo raíz del árbol contiene un enlace a todas las raíces de sus subárboles. El subárbol izquierdo se muestra en color amarillo en la figura siguiente, y el subárbol derecho se muestra en color rojo. El subárbol izquierdo se puede dividir en subárboles que se muestran en tres colores diferentes. La recursividad significa reducir algo de una manera auto-similar. Entonces, esta propiedad recursiva de la estructura de datos de árbol se implementa en varias aplicaciones.
    Árbol
  • Numero de aristas: Si hay n nodos, entonces habría n-1 aristas. Cada flecha de la estructura representa el vínculo o la ruta. Cada nodo, excepto el nodo raíz, tendrá al menos un enlace entrante conocido como borde. Habría un enlace para la relación padre-hijo.
  • Profundidad del nodo x: La profundidad del nodo x se puede definir como la longitud de la ruta desde la raíz hasta el nodo x. Un borde aporta una unidad de longitud en el camino. Entonces, la profundidad del nodo x también se puede definir como el número de bordes entre el nodo raíz y el nodo x. El nodo raíz tiene una profundidad 0.
  • Altura del nodo x: La altura del nodo x se puede definir como la ruta más larga desde el nodo x hasta el nodo hoja.

Según las propiedades de la estructura de datos del árbol, los árboles se clasifican en varias categorías.

Implementación de Tree

La estructura de datos de árbol se puede crear creando los nodos dinámicamente con la ayuda de los punteros. El árbol en la memoria se puede representar como se muestra a continuación:

Árbol

La figura anterior muestra la representación de la estructura de datos de árbol en la memoria. En la estructura anterior, el nodo contiene tres campos. El segundo campo almacena los datos; el primer campo almacena la dirección del hijo izquierdo y el tercer campo almacena la dirección del hijo derecho.

En programación, la estructura de un nodo se puede definir como:

La estructura anterior solo se puede definir para los árboles binarios porque el árbol binario puede tener un máximo de dos hijos y los árboles genéricos pueden tener más de dos hijos. La estructura del nodo para árboles genéricos sería diferente en comparación con el árbol binario.

Aplicaciones de los árboles

Las siguientes son las aplicaciones de los árboles:

  • Almacenamiento de datos naturalmente jerárquicos: Los árboles se utilizan para almacenar los datos en la estructura jerárquica. Por ejemplo, el sistema de archivos. El sistema de archivos almacenado en la unidad de disco, el archivo y la carpeta tienen la forma de datos naturalmente jerárquicos y se almacenan en forma de árboles.
  • Organizar datos: Se utiliza para organizar datos para una inserción, eliminación y búsqueda eficientes. Por ejemplo, un árbol binario tiene un tiempo logN para buscar un elemento.
  • Trie: Es un tipo especial de árbol que se utiliza para almacenar el diccionario. Es una forma rápida y eficaz de revisión ortográfica dinámica.
  • Montón: También es una estructura de datos de árbol implementada mediante matrices. Se utiliza para implementar colas de prioridad.
  • Árbol B y Árbol B +: B-Tree y B + Tree son las estructuras de datos de árbol que se utilizan para implementar la indexación en las bases de datos.
  • Tabla de ruteo: La estructura de datos de árbol también se utiliza para almacenar los datos en tablas de enrutamiento en los enrutadores.

Tipos de estructura de datos de árbol

Los siguientes son los tipos de estructura de datos de árbol:

  • Árbol general: El árbol general es uno de los tipos de estructura de datos de árbol. En el árbol general, un nodo puede tener 0 o un número máximo de n nodos. No se impone ninguna restricción sobre el grado del nodo (el número de nodos que puede contener un nodo). El nodo superior de un árbol general se conoce como nodo raíz. Los hijos del nodo padre se conocen como subárboles.
    Árbol
    Puede haber norte número de subárboles en un árbol general. En el árbol general, los subárboles están desordenados ya que los nodos del subárbol no se pueden ordenar.
    Cada árbol no vacío tiene un borde hacia abajo, y estos bordes están conectados a los nodos conocidos como nodos secundarios. El nodo raíz está etiquetado con el nivel 0. Los nodos que tienen el mismo padre se conocen como hermanos.
  • Árbol binario: Aquí, el nombre binario en sí sugiere dos números, es decir, 0 y 1. En un árbol binario, cada nodo de un árbol puede tener dos nodos secundarios como máximo. Aquí, máximo significa si el nodo tiene 0 nodos, 1 nodo o 2 nodos.
    Árbol
    Para saber más sobre el árbol binario, haga clic en el enlace que figura a continuación:
    https://www.javatpoint.com/binary-tree
  • Árbol de búsqueda binaria: El árbol de búsqueda binaria es una estructura de datos no lineal en la que un nodo está conectado a norte número de nodos. Es una estructura de datos basada en nodos. Un nodo se puede representar en un árbol de búsqueda binario con tres campos, es decir, parte de datos, hijo izquierdo y hijo derecho. Un nodo se puede conectar a los dos nodos secundarios máximos en un árbol de búsqueda binario, por lo que el nodo contiene dos punteros (secundario izquierdo y secundario derecho).
    Cada nodo del subárbol izquierdo debe contener un valor menor que el valor del nodo raíz, y el valor de cada nodo del subárbol derecho debe ser mayor que el valor del nodo raíz.

Se puede crear un nodo con la ayuda de un tipo de datos definido por el usuario conocido como estructura Como se muestra abajo:

Lo anterior es la estructura del nodo con tres campos: campo de datos, el segundo campo es el puntero izquierdo del tipo de nodo y el tercer campo es el puntero derecho del tipo de nodo.

Para saber más sobre el árbol de búsqueda binaria, haga clic en el enlace que figura a continuación:

https://www.javatpoint.com/binary-search-tree

Es uno de los tipos del árbol binario, o podemos decir que es una variante del árbol de búsqueda binaria. El árbol AVL satisface la propiedad del árbol binario así como de la árbol de búsqueda binaria. Es un árbol de búsqueda binario autoequilibrado que fue inventado por Adelson Velsky Lindas. Aquí, autoequilibrio significa equilibrar las alturas del subárbol izquierdo y el subárbol derecho. Este equilibrio se mide en términos de factor de equilibrio.

Podemos considerar un árbol como un árbol AVL si el árbol obedece tanto al árbol de búsqueda binario como a un factor de equilibrio. El factor de equilibrio se puede definir como el diferencia entre la altura del subárbol izquierdo y la altura del subárbol derecho. El valor del factor de equilibrio debe ser 0, -1 o 1; por lo tanto, cada nodo del árbol AVL debe tener el valor del factor de equilibrio como 0, -1 o 1.

Para saber más sobre el árbol AVL, haga clic en el enlace que figura a continuación:

https://www.javatpoint.com/avl-tree

El árbol rojo-negro es el árbol de búsqueda binaria. El requisito previo del árbol Rojo-Negro es que debemos conocer el árbol de búsqueda binaria. En un árbol de búsqueda binaria, el valor del subárbol izquierdo debe ser menor que el valor de ese nodo, y el valor del subárbol derecho debe ser mayor que el valor de ese nodo. Como sabemos, la complejidad temporal de la búsqueda binaria en el caso promedio es log2n, el mejor caso es O (1) y el peor caso es O (n).

Cuando se realiza cualquier operación en el árbol, queremos que nuestro árbol esté equilibrado para que todas las operaciones como búsqueda, inserción, eliminación, etc., tomen menos tiempo, y todas estas operaciones tendrán la complejidad de tiempo de Iniciar sesión2norte.

El árbol rojo-negro es un árbol de búsqueda binario autoequilibrado. El árbol AVL también es un árbol de búsqueda binaria de equilibrio de altura, entonces ¿Por qué necesitamos un árbol rojo-negro?. En el árbol AVL, no sabemos cuántas rotaciones se requerirían para equilibrar el árbol, pero en el árbol rojo-negro, se requiere un máximo de 2 rotaciones para equilibrar el árbol. Contiene un extra …

close