Introducción a los árboles en la estructura de datos
Antes de comprender los tipos de árboles en la estructura de datos, primero estudiaremos los árboles en la estructura de datos. El árbol en el campo de la computadora también se conoce como el árbol del mundo real, sin embargo, la diferencia entre el mundo real y el árbol del campo de la computación es que se visualiza al revés y la raíz encima y se ramifica desde la raíz hasta las hojas del árbol. Entre varias aplicaciones del mundo real, se utiliza la estructura de datos del árbol, ya que puede demostrar relaciones entre diferentes nodos con la jerarquía padre-hijo. También se le llama estructura de datos jerárquica debido a esto. Es más popular para simplificar y acelerar la búsqueda y la clasificación. Es considerada como una de las estructuras de datos más fuertes y avanzadas. Un árbol es una representación de la estructura de datos no lineal. Se puede mostrar un árbol utilizando diferentes tipos de datos definidos por el usuario o primitivos. Podemos usar matrices, listas conectadas de clases u otro tipo de estructuras de datos para implementar el árbol. Es un grupo de nodos que están interrelacionados. Los nodos están unidos a los bordes para demostrar la relación.
Relaciones en un árbol: en el diagrama anterior, P es la raíz del árbol y P es padre de Q, R y S. Q es hijo de P. Por lo tanto, Q, R y S son hermanos. Mientras que P es abuelo de A, B, C, D y E.
¿Qué son los árboles?
Un árbol es una estructura de datos jerárquica que almacena naturalmente la información de forma jerárquica. La estructura de datos del árbol es una de las más eficientes y maduras. Los nodos conectados por los bordes están representados.
Propiedades del árbol: cada árbol tiene un nodo raíz específico. Cada nodo del árbol puede ser cruzado por un nodo raíz. Se llama raíz, ya que el árbol era la única raíz. Cada niño tiene un solo padre, pero el padre puede tener muchos hijos.
Tipos de árboles en la estructura de datos
A continuación se muestran los tipos de árboles en una estructura de datos:
1. Árbol general
Si no se coloca ninguna restricción en la jerarquía del árbol, un árbol se llama árbol general. Cada nodo puede tener un número infinito de hijos en General Tree. El árbol es el superconjunto de todos los demás árboles.
2. Árbol binario
El árbol binario es el tipo de árbol en el que se pueden encontrar la mayoría de los dos hijos para cada padre. Los niños son conocidos como el niño izquierdo y el niño derecho. Esto es más popular que la mayoría de los otros árboles. Cuando se aplican ciertas restricciones y características en un árbol binario, también se utilizan otras como árbol AVL, BST (árbol de búsqueda binario), árbol RBT, etc. Cuando avancemos, explicaremos todos estos estilos en detalle.
3. Árbol de búsqueda binaria
Binary Search Tree (BST) es una extensión de árbol binario con varias restricciones opcionales. El valor secundario izquierdo de un nodo en BST debe ser menor o igual que el valor primario y el valor secundario derecho siempre debe ser mayor o igual que el valor primario. Esta propiedad del árbol de búsqueda binaria lo hace ideal para las operaciones de búsqueda, ya que podemos determinar con precisión en cada nodo si el valor está en el subárbol izquierdo o derecho. Por eso se nombra el Árbol de búsqueda.
4. Árbol AVL
El árbol AVL es un árbol de búsqueda binario que se autoequilibra. En nombre de los inventores Adelson-Velshi y Landis, se le da el nombre AVL. Este fue el primer árbol que se equilibró dinámicamente. Se asigna un factor de equilibrio para cada nodo en el árbol AVL, en función de si el árbol está equilibrado o no. La altura de los niños del nodo es como máximo 1. AVL vine. En el árbol AVL, el factor de equilibrio correcto es 1, 0 y -1. Si el árbol tiene un nuevo nodo, se rotará para garantizar que esté equilibrado. Luego se rotará. Las operaciones comunes, como la visualización, la inserción y la eliminación, llevan tiempo O (log n) en el árbol AVL. Se aplica principalmente cuando se trabaja con operaciones de búsqueda.
5. Árbol rojo-negro
Otro tipo de árbol de equilibrio automático es rojo-negro. El nombre rojo-negro se da porque el árbol rojo-negro tiene rojo o negro pintado en cada nodo de acuerdo con las propiedades del árbol rojo-negro. Mantiene el equilibrio del bosque. Aunque este árbol no es un árbol completamente equilibrado, la operación de búsqueda solo toma tiempo O (log n). Cuando los nuevos nodos se agregan en Red-Black Tree, los nodos se rotarán nuevamente para mantener las propiedades del Red-Black Tree.
6. Árbol N-ary
El número máximo de hijos en este tipo de árbol que puede tener un nodo es N. Un árbol binario es un árbol de dos años, como máximo 2 hijos en cada nodo de árbol binario. Un árbol N-ary completo es un árbol donde los hijos de un nodo son 0 o N.
Ventajas de Tree
Ahora entenderemos las ventajas del árbol:
- El árbol se refleja en las conexiones estructurales de datos.
- El árbol se usa para la jerarquía.
- Ofrece un eficiente procedimiento de búsqueda e inserción.
- Los arboles son flexibles. Esto permite que los subárboles se reubiquen con un esfuerzo mínimo.
Conclusión: tipos de árboles en la estructura de datos
Entonces, aquí en este artículo, hemos visto qué es la estructura de árbol, cuáles son los diferentes tipos de árboles en la estructura de datos y sus beneficios. Espero que tenga una idea de algunos de los árboles comunes en la estructura de los datos.
Artículos recomendados
Esta es una guía de tipos de árboles en la estructura de datos. Aquí discutimos qué son los árboles, 6 tipos de árboles en la estructura de datos, con ventajas. También puede consultar nuestros otros artículos relacionados para obtener más información:
- Tubería de datos de AWS
- Oracle Data Warehousing
- Base de datos multidimensional
- Estructura de datos Preguntas de la entrevista Java