Árboles
Un árbol (tree) es una estructura de datos que consiste en nodos conectados entre sí de manera que cada nodo tiene un valor y referencias a nodos hijos. La estructura tiene una raíz y los nodos están organizados de tal manera que se forman niveles o capas.
Usos
- Búsqueda rápida: Árboles como los árboles binarios de búsqueda (BST, Binary Search Tree) permiten buscar elementos de forma eficiente.
- Gestión de datos: Usados para mantener datos ordenados y facilitar operaciones como inserción y eliminación.
Características
Las características principales de los árboles son:
- Nodos: Elementos del árbol que contienen un valor y referencias a sus nodos hijos.
- Nodo raíz: El nodo superior del árbol, que no tiene padre.
- Hijos: Nodos que están directamente conectados a un nodo padre.
- Nodos hoja: Nodos que no tienen nodos hijos.
- Profundidad/Nivel: El nivel de un nodo es la distancia desde la raíz hasta ese nodo.
- Altura: La altura del árbol es la profundidad del nodo más profundo.
- Subárbol: Un subárbol en un árbol binario de búsqueda es cualquier nodo del árbol junto con todos sus descendientes. En otras palabras, un subárbol es un árbol que está contenido dentro de otro árbol más grande.
Tipos
Podemos diferenciar algunos tipos de árboles interesantes dentro de la programación.
Árboles binarios
Los árboles binarios son un tipo específico de árbol donde cada nodo tiene como máximo dos hijos: un hijo izquierdo y un hijo derecho.
Árboles binarios de búsqueda
Los árboles binarios de búsqueda (BST, Binary Search Tree) son un tipo de árbol binario donde, para cada nodo, todos los valores en el subárbol izquierdo son menores y todos los valores en el subárbol derecho son mayores.
En esta imagen podemos observar un ejemplo de árbol binario de búsqueda:
De este ejemplo podemos observar que hay varios subárboles. De hecho, hay uno por cada nodo, en el que cada uno de ellos funciona como nodo raíz de cada uno de los subárboles.
Árboles binarios completos
En los árboles binarios completos (full binary trees) cada nivel del árbol está completamente lleno, y todos los nodos son tan completos como sea posible.
Árboles binarios balanceados
Los árboles binarios balanceados (balanced binary trees) son árboles donde las alturas de los subárboles izquierdo y derecho de cada nodo difieren por como máximo una unidad.
