Teoremas I Y II Para Árboles Binarios

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho. Existen tipos de árboles binarios que suelen usarse para fines específicos, como:

• Árbol binario de búsqueda
• Árbol de Fibonacci

     Árbol binario de búsqueda

     Sea A un árbol binario de raíz R e hijos izquierdo y derecho (posiblemente nulos) H_I y H_D , respectivamente. Se dice que A es un árbol binario de búsqueda (ABB) si y solo si se satisfacen las dos condiciones al mismo tiempo:

·         "H_I es vacío" {\displaystyle \lor }V ("R es mayor que todo elemento de H_I" {\displaystyle \land }۸ "H_I es un ABB").

·         "H_D es vacío" {\displaystyle \lor }V ("R es menor que todo elemento de H_D" {\displaystyle \land }۸ "H_D es un ABB").

Donde "۸{\displaystyle \land } " es la conjunción lógica "y", y "{\displaystyle \lor } v" es la disyunción lógica "o".

       Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores. Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación esté definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos. La altura h en el peor de los casos es siempre el mismo tamaño que el número de elementos disponibles. Y en el mejor de los casos viene dada por la expresión h=[log2 (c+1)*]. Un árbol binario de búsqueda no deja de ser un caso particular de árbol binario, así usando la siguiente especificación de árbol binario en maude:

fmod ARBOL-BINARIO {X :: TRIV}is

   sorts ArbolBinNV{X} ArbolBin{X} .

   subsort ArbolBinNV{X} < ArbolBin{X} .

   *** generadores

   op crear : -> ArbolBin{X} [ctor] .

   op arbolBin : X$Elt ArbolBin{X} ArbolBin{X} -> ArbolBinNV{X} [ctor] .

   endfm

       Se puede hacer la siguiente definición para un árbol binario de búsqueda (también en maude):

fmod ARBOL-BINARIO-BUSQUEDA {X :: ORDEN} is

       protecting ARBOL-BINARIO{VOrden}{X} .

       sorts ABB{X} ABBNV{X} .

       subsort ABBNV{X} < ABB{X} .

       subsort ABB{X} < ArbolBin{VOrden}{X} .

       subsort ABBNV{X} < ArbolBinNV{VOrden}{X} .

   *** generadores

   op crear : -> ArbolBin{X} [ctor] .

   op arbolBin : X$Elt ArbolBin{X} ArbolBin{X} -> ArbolBinNV{X} [ctor] .

   endfm

       Con la siguiente teoría de orden:

fth ORDEN is

    protecting BOOL .

    sort Elt .

    *** operaciones

    op _<_ : Elt Elt -> Bool .

    endfth

       Para que un árbol binario pertenezca al tipo árbol binario de búsqueda debe cumplir la condición de ordenación siguiente que iría junto al módulo ARBOL-BINARIO-BUSQUEDA:

var  R : X$Elt .

   vars INV DNV : ABBNV{X} .

   vars I D : ABB{X} .

   mb crear : ABB{X} .

   mb arbolBin(R, crear, crear) : ABBNV{X} .

   cmb arbolBin(R, INV, crear) : ABBNV{X} if R > max(INV) .

   cmb arbolBin(R, crear, DNV) : ABBNV{X} if R < min(DNV) .

   cmb arbolBin(R, INV, DNV) : ABBNV{X} if (R > max(INV)) and (R < min(DNV)) .

   ops min max : ABBNV{X} -> X$Elt .

   eq min(arbolBin(R, crear, D)) = R .

   eq min(arbolBin(R, INV, D)) = min(INV) .

   eq max(arbolBin(R, I, crear)) = R .

   eq max(arbolBin(R, I, DNV)) = max(DNV) .

class nodo:

    izq , der, dato = None, None, 0

   

    def __init__(self, dato):

        # crea un nodo

        self.izq = None

        self.der = None

        self.dato = dato

class arbolBinario:

    def __init__(self):

        # inicializa la raiz

        self.raiz = None

   

    def agregarNodo(self, dato):

        # crea un nuevo nodo y lo devuelve

        return nodo(dato)

    def insertar(self, raiz, dato):

        # inserta un dato nuevo en el árbol

        if raiz == None:

            # si no hay nodos en el árbol lo agrega

            return self.agregarNodo(dato)

        else:

            # si hay nodos en el árbol lo recorre

            if dato <= raiz.dato:

                # si el dato ingresado es  menor que el dato guardado va al subárbol izquierdo

                raiz.izq = self.insertar(raiz.izq, dato)

            else:

                # si no, procesa el subárbol derecho

                raiz.der = self.insertar(raiz.der, dato)

            return raiz

       Árbol de Fibonacci

       Árboles de Fibonacci de orden 1, 2, 3 y 4.

     Se llama árbol de Fibonacci a una variante de árbol binario con la propiedad que el orden de un nodo se calcula como la sucesión de Fibonacci. El árbol de Fibonacci se define de la siguiente manera:

• El árbol nulo (no contiene ningún nodo) es de orden 0.
•  El árbol que consta de un único nodo es de orden 1.

       Para n > 1, el árbol de Fibonacci de orden n consta de un nodo raíz con el árbol de Fibonacci de orden n-1 como hijo izquierdo y el árbol de Fibonacci de orden n-2 como hijo derecho. Dado que este tipo de árbol es un caso particular de un árbol AVL, ya que el factor de equilibrio de todo nodo es -1, un árbol de Fibonacci es balanceado con altura O(log n). 

TArbinDinamico<int> arbolFibonacci (int n){

TArbinDinamico<int> res;

if (n==0)

 res = TArbinDinamico(0, n, 0);

else if (n==1)

 res = TArbinDinamico(1, n, 0);

else

 res = TArbinDinamico(arbolFibonacci(n-1), n, arbolFibonacci(n-2));

return res;

}