2022-04-11

Representación de Conjuntos y Diccionarios a través de Árboles Binarios

¿Qué es un Árbol Binario de Búsqueda (ABB)?

Para todo nodo, los valores de los elementos en su sub-árbol izquierdo son menores que el valor del nodo, y los valores de los elementos de su sub-árbol derecho son mayores que el valor del nodo.

De esta manera todo lo que me queda “a la derecha” del nodo es mayor a éste, y todo lo que me queda “a la izquierda” es menor.

Invariante de Representación

$$ ABB(e) \equiv \text{nil?}(e) \lor_L \\ \bigg[\big\{(\forall c: \text{clave})(\text{Está?}(c, \text{Izq}(e)) \implies (c <{\text{clave}} \text{LaClave}(\text{Raíz}(e))) \land \\ (\text{Está?}(c, \text{Der}(e)) \implies (c >{\text{clave}} \text{LaClave}(\text{Raíz}(e)))\big\} \land \\ ABB(\text{Izq}(e)) \land \\ ABB(\text{Der}(e))\bigg] $$

Algoritmos en ABBs

Insertar

El costo de inserción depende de la distancia del nodo a la raíz.

• En el peor caso: $O(n)$
• En el caso promedio, suponiendo la distribución uniforme de las claves: $O(\log(n))$

Borrado

Si $u$ es el nodo a borrar y $A$ es un $ABB$ tengo tres casos posibles:

• $u$ es una hoja
• $u$ tiene un sólo hijo
• $u$ tiene dos hijos