Conceptos Fundamentales y Operaciones en Árboles Binarios de Búsqueda (ABB)

Conceptos Básicos de Árboles

Un árbol es una estructura de datos jerárquica compuesta por nodos conectados por ramas. Los árboles se utilizan para representar relaciones de jerarquía y organizar datos de forma eficiente.

• Raíz: Es el nodo superior del árbol, aquel que no tiene antecesor.
• Rama: Es la arista o conexión que une dos nodos.
• Antecesor: Un nodo es antecesor de otro si está conectado directamente a él en un nivel superior.
• Sucesor: Un nodo es sucesor de otro si está conectado directamente a él en un nivel inferior. Un nodo x es sucesor de y si por alguna de las ramas de y se puede llegar a x.
• Grado: Es el número de descendientes directos que tiene un nodo.
• Hoja: Es un nodo que no tiene descendientes, es decir, su grado es 0.
• Nodo Interno: Es aquel nodo que tiene al menos un descendiente.
• Nivel: Es la distancia de un nodo a la raíz, medida en número de ramas. La raíz tiene nivel 0.
• Altura: Es la distancia entre el nodo más profundo (hoja más lejana) y la raíz, medida en número de nodos.
• Anchura: Es el número máximo de nodos en un mismo nivel.

Definición de la Estructura de un Árbol

A continuación, se presenta una posible definición de la estructura de un árbol en pseudocódigo:

  
    Type def ARBOL = Record
      clave: dato;
      *izquierda, *derecha: ARBOL;
    end record;
  

Árboles Binarios de Búsqueda (ABB)

Los árboles binarios de búsqueda (ABB) son un tipo especial de árbol binario que cumple con las siguientes propiedades:

• Cada nodo tiene como máximo dos hijos (izquierdo y derecho).
• Todas las claves del subárbol izquierdo de un nodo son menores que la clave del nodo.
• Todas las claves del subárbol derecho de un nodo son mayores que la clave del nodo.

Creación de un Nodo en un ABB

  
    Crear (rec: ARBOL)
      nuevo.clave = elemento;
      nuevo.izquierda = nuevo.derecha = NULL;
  

Reglas para Borrar un Nodo en un ABB

1. Si el nodo a borrar es una hoja (no tiene hijos), se elimina directamente.
2. Si el nodo a borrar tiene un solo descendiente, se sustituye el nodo por su hijo.
3. Si el nodo a borrar tiene dos descendientes, se puede optar por una de las siguientes estrategias:
   1. Buscar el menor de los mayores: Se busca el nodo con la clave menor en el subárbol derecho y se reemplaza el nodo a borrar por este.
   2. Buscar el mayor de los menores: Se busca el nodo con la clave mayor en el subárbol izquierdo y se reemplaza el nodo a borrar por este.

Función de Búsqueda en un ABB

  
    Búsqueda (rec: ARBOL)
      If rec == null then
        return (Falso);
      Else
        If rec.clave < elemento que busco then
          Búsqueda (rec -> derecha);
        Else
          If rec.clave > elemento que busco then
            Búsqueda (rec -> izquierda);
          Else
            return (Verdadero);
  

Función de Inserción en un ABB

  
    Insertar (rec: ARBOL)
      If rec == null then
        rec = nuevo;
      Else
        If rec -> clave == nuevo.clave then
          Insertar (rec -> derecha);
        Else
          If rec.clave > nuevo.clave then
            Insertar (rec -> izquierda);
  

Ejercicios y Preguntas sobre ABB

Ejercicio 1

Dada la secuencia 100, 50, 150, 120, 140, 40, 30, 145, la altura del árbol es:

• 4 (Correcta)
• 3
• Ninguna de las anteriores

Ejercicio 2

La siguiente función:

  
    void recorrer (*rec: arbol)
      If Rec= NULL then
        Return ();
      else {
        recorrer (rec.izquierda);
        recorrer (rec.derecha);
        visito 0;
      }
  

• Recorre el árbol en Postorder (Correcta)
• Recorre el árbol en Inorder
• Recorre el árbol en Preorder
• Ninguna de las anteriores

Ejercicio 3

Los árboles son estructuras:

• Que pueden tener múltiples enlaces
• Son recursivos
• Tienen estructuras denominadas subárboles
• Todas las anteriores (Correcta)

Ejercicio 4

¿Cuáles de las siguientes secuencias representan un árbol AVL?

• 15, 40, 2, 0, 3, 50, 30, 20, 4 (Correcta)
• 100, 50, 150, 120, 140, 40, 30, 145
• Ninguna de las anteriores
• Todas las anteriores

Ejercicio 5

Al número de descendientes que tiene un nodo en una estructura árbol se denomina:

• Grado (Correcta)
• Hoja
• Anchura
• Raíz
• Sucesor

Ejercicio 6

Dada la siguiente secuencia 15, 40, 2, 0, 3, 50, 30, 20, 4 del ABB, después del recorrido en Inorder se obtiene la siguiente secuencia de salida:

• 0, 2, 3, 4, 15, 20, 30, 40, 50 (Correcta)
• 15, 2, 0, 3, 4, 40, 30, 20, 50
• 0, 4, 3, 2, 20, 30, 50, 40, 15
• Ninguna de las anteriores

Ejercicio 7

En la siguiente secuencia 15, 40, 2, 0, 3, 50, 30, 20, 4, al eliminar la raíz dos veces de manera consecutiva, utilizando el algoritmo del menor de los mayores, se obtiene:

• Raíz = nodo 30 y árbol AVL (Correcta)
• Raíz = nodo 30 y árbol no AVL
• Raíz = nodo 40 y árbol AVL
• Raíz = nodo 20 y árbol AVL
• Ninguna de las anteriores

Ejercicio 8

En la secuencia 100, 50, 150, 120, 140, 40, 30, 145, el factor de equilibrio:

• En el nodo 120 es igual a 2 y en el nodo 150 es -3 (Correcta)
• En el nodo 120 es igual a 2 y en el nodo 150 es 3
• En el nodo 100 es igual a 2 y en el nodo 40 es -1
• Ninguna de las anteriores

Ejercicio 9

Dada la secuencia M, E, J, K, L, C, P, N, S, R, U, T, O, B, H, I, A, después de eliminar el nodo P utilizando el algoritmo de borrado "el menor de los mayores", el árbol AVL se obtiene después de aplicar:

• Un caso I y caso IV (Correcta)
• Un caso II y caso I
• Un caso II y caso IV

Árboles Equilibrados o AVL

Son aquellos árboles donde las claves que están a la derecha son mayores a las claves que se encuentran a su izquierda y la diferencia de altura entre los subárboles de cada nodo no difiere en más de 1.

• Árboles Binarios de Búsqueda
• Árboles Equilibrados (Correcta)
• Factor de Equilibrio
• Todas las anteriores

Factor de Equilibrio

Cuando se calcula la diferencia de alturas entre el subárbol derecho menos la del subárbol izquierdo, en cada nodo del árbol, corresponde a:

• Factor de Equilibrio (Correcta)
• Árboles Binarios de Búsqueda
• Árboles Equilibrados
• Todas las anteriores