Árbol binario de búsqueda

Un árbol binario de búsqueda también llamado BST (acrónimo del inglés Binary Search Tree) es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.

Descripción

Veamos la definición de árbol binario de búsqueda:

Árbol binario de búsqueda

Sea A un árbol binario de raíz R e hijos izquierdo y derecho (posiblemente nulos) HI y HD , respectivamente.

Decimos que A es un árbol binario de búsqueda (ABB) si y solo si se satisfacen las dos condiciones al mismo tiempo:

  • "HI es vacío" ("R es mayor que todo elemento de HI" "HI es un ABB").
  • "HD es vacío" ("R es menor que todo elemento de HD" "HD es un ABB").

Donde "" es la conjunción lógica "y", y "" es la disyunción lógica "o".

Un árbol binario de búsqueda de tamaño 9 y profundidad 3, con raíz 8 y hojas 1, 4, 7 y 13

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 .

El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en in orden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.

Dependiendo de las necesidades del usuario que trate con una estructura de este tipo, se podrá permitir la igualdad estricta en alguno, en ninguno o en ambos de los subárboles que penden de la raíz. Permitir el uso de la igualdad provoca la aparición de valores dobles y hace la búsqueda más compleja.

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

podemos 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
Other Languages