Junior
¿Qué es un árbol binario?
sobes.tech AI
Respuesta de la IA
Un árbol binario es una estructura de datos en forma de árbol en la que cada nodo tiene como máximo dos descendientes: izquierdo y derecho.
Propiedades principales:
- Raíz (Root): El nodo superior del árbol.
- Nodo (Node): Elemento del árbol que contiene datos y enlaces a sus descendientes.
- Hijo (Child): Nodo que está directamente debajo de otro nodo (padre).
- Padre (Parent): Nodo que tiene uno o más descendientes directamente debajo de él.
- Hoja (Leaf): Nodo que no tiene descendientes.
- Rama (Branch): Camino desde la raíz hasta una hoja.
- Subárbol (Subtree): Árbol que consiste en un nodo y todos sus descendientes.
Tipos diferentes de árboles binarios:
- Árbol binario completo (Full Binary Tree): Cada nodo tiene 0 o 2 descendientes.
- Árbol binario perfecto (Perfect Binary Tree): Todos los niveles, excepto el último, están completamente llenos, y en el último nivel todos los nodos están lo más a la izquierda posible.
- Árbol binario balanceado (Balanced Binary Tree): La altura de los subárboles izquierdo y derecho de cualquier nodo difiere como mucho en 1. Ejemplo: árbol AVL, árbol rojo-negro.
- Árbol binario degenerado (Degenerate Binary Tree): Cada nodo tiene como máximo un descendiente. Esencialmente, es una lista enlazada.
Se aplica en diversos algoritmos y estructuras de datos, como árboles binarios de búsqueda, montículos, árboles sintácticos.