Introducción a los Árboles

Created in January 06, 2023 by Alan Yahir Juárez Rubio , last updated in June 04, 2024

2023   ·   arbol   nodo   recorridos-de-arboles   tipos-de-arboles   ·   matematicas   matematicas-discretas   arboles

Un árbol consiste en una agrupación de nodos, el cuál parte de un nodo raíz y se desgloza jerarquicamente en más nodos.

Los Árboles nos permiten organizar o estructurar información. Si tenemos un nodo A y un nodo B, solo existirá una conexión entre ellos.

NOTA

En los árboles solo puede haber una conexión entre dos nodos.

Estructura de un Árbol
Fig. 1: Estructura de un Árbol

Cuando el orden de los nodos importa, entonces forman una lista y se le denomina árbol ordenado.

En informática los arboles son estructuras de datos no lineales. Cada uno de sus nodos guarda información de sí mismo y, a su vez, guarda la dirección de cada uno de los nodos que le suceden (nodos hijos).

Características de un Nodo

  • Brazo: Conexión entre un nodo y otro.

  • Altura: Longitud del camino más largo que comienza en el nodo y termina en una hoja. Se dice que la altura del nodo raíz es la altura del árbol.

  • Nivel o profundidad: Longitud del camino (único) que comienza en la raíz (como nivel 0) y termina en dicho nodo.

Partes de un árbol (tipos de nodos)

Un árbol es una agrupación de nodos ordenados jerarquicamente. Estos nodos se catalogan de la siguiente manera:

  • Raíz: Nodo del cuál se desprenden todos los demás nodos.

  • Padre: Nodo que engloba a dicho nodo.

  • Hijo: Nodo que se desprende un nodo padre. Todos los nodos son nodos hijos a excepción del nodo raíz.

  • Ancestro: Nodo que engloba al padre de dicho nodo.

  • Nieto: Nodo que se desprende del padre del nodo padre, es decir, del ancestro.

  • Hermanos: Aquellos que tienen un nodo padre en común.

  • Terminal, hoja o externo: Aquellos que no tiene hijos y, por lo tanto, marcan el final del árbol. En caso contrario se le denomina nodo interno.

  • Internos o rama: Todos aquellos que son nodos padres o, dicho de otra manera, todos a quellos que no son terminales. En este tipo se excluye el nodo raíz.

Subárboles

Un subárbol es una sección de un árbol, una parte de un ábol. Estos subárboles están conformados desde un nodo padre de dicho árbol y todos sus descendientes; si se dividiera desde un nodo padre n, se llamaría subárbol raíz n.

Tipos de árboles

Tipos de Árbol
Fig. 2: Tipos de Árbol
  • Libres: Aquellos en los que se desconoce el nodo raíz.
  • Degenerado: Todos sus nodos tienen como máximo un hijo.
  • Expansión: Aquel árbol (generalmente extraído de un grafo) el cual representa una conexión ponderada (un recurso asociado) con cada uno de los nodos.
Tipos de Árbol Binario
Fig. 3: Tipos de Árbol Binario
  • M-nario: Cada uno de sus nodos tiene como máximo \(m\) hijos. Entre estos se encuentran los binarios (2 hijos), los ternarios (3 hijos), entre otros.
    • Completo: Sus nodos tienen o \(m\) hijos o ninguno.
      • Lleno: Todos sus nodos terminales llegan a un mismo nivel.
Arboles M-narios
Fig. 4: Árboles M-narios

Referencias



    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • Introducción a los Comandos
  • Interfaces de Usuario en los Sistemas Operativos
  • Introducción a Linux
  • Introducción a los Sistemas Operativos
  • Vim CheatSet
  • Sistemas Numéricos