06 Diccionarios.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6 Diccionarios\n",
    "\n",
    "El TDA Diccionario es uno de los más usados en la práctica, y se conocen mucha formas distintas de implementarlo.\n",
    "\n",
    "Un Diccionario es un conjunto de $n$ elementos, cada uno de los cuales tiene un campo que permite identificarlo de manera única (ese campo se llama su *llave primaria*), sobre el cual están definidas las operaciones de buscar, insertar, eliminar, y ocasionalmente otras que definiremos más adelante.\n",
    "Más precisamente, si $d$ es un diccionario, existirán las operaciones:\n",
    "\n",
    "* `r=d.search(x)`: buscar el elemento de llave `x`, retornar un resultado que permita ubicarlo, o `None` si no está\n",
    "* `d.insert(x)`: insertar un elemento de llave `x`, evitando crear una llave duplicada\n",
    "* `d.delete(x)`: eliminar el elemento de llave `x`, el cual debe estar en el diccionario"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diccionarios de Python\n",
    "\n",
    "El lenguaje Python posee un tipo `dict` que implementa la funcionalidad de diccionarios que hemos descrito (más operaciones adicionales). En un diccionario se busca por una llave y se obtiene un valor asociado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "distancia = {'Valparaíso':102, 'Concepción': 433, 'Arica': 1664, 'Puerto Montt': 912, 'Rancagua': 80}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La forma de buscar es simplemente usando la llave como subíndice:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1664\n"
     ]
    }
   ],
   "source": [
    "print(distancia['Arica'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Y la forma de agregar una nueva llave es asignándole un valor:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "distancia['Talca']=237"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Al buscar una llave inexistente se produce una excepción:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "'La Serena'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-14-0078e5a2585d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdistancia\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'La Serena'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m: 'La Serena'"
     ]
    }
   ],
   "source": [
    "print(distancia['La Serena'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pero hay una forma de buscar sin que dé un error, sino que retorne `None`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "80 None\n"
     ]
    }
   ],
   "source": [
    "print(distancia.get('Rancagua'), distancia.get('La Serena'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para eliminar un dato, se usa `pop` (lo elimina y retorna su valor):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "80"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distancia.pop('Rancagua')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aparte de esto, hay muchas otras operaciones que permiten obtener la lista de todas las llaves, etc.\n",
    "\n",
    "Dado que en Python ya existe una implementación de diccionarios, ¿por qué querríamos estudiar nosotros cómo implementarlos?\n",
    "\n",
    "La respuesta está en que, si nosotros controlamos todos los detalles de una implementación, sabremos exactamente cuan eficiente es, y para qué tipo de aplicaciones es más apropiada. Lo último es particularmente importante, porque no hay ninguna implementación de diccionarios que sea uniformemente mejor que las otras para todas las aplicaciones.\n",
    "\n",
    "Estudiaremos entonces cómo se puede implementar un diccionario, comenzando por las estrategias más sencillas, y avanzando hacia enfoques más sofisticados.\n",
    "\n",
    "En nuestros ejemplos supondremos que solo almacenamos la llave, pero en la práctica siempre habrá información adicional asociada a cada llave. También por simplicidad a menudo usaremos llaves numéricas, aunque en la práctica es más frecuente que las llaves sean strings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Búsqueda secuencial\n",
    "\n",
    "La manera más simple de implementar un diccionario es con una lista desordenada de llaves, en la cual se hace búsqueda secuencial. La inserción es especialmente eficiente si obviamos chequear por duplicados, y la eliminación es eficiente una vez que sabemos dónde está la llave."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Lista_secuencial:\n",
    "    def __init__(self, size=100):\n",
    "        self.a=np.zeros(size,dtype=int)\n",
    "        self.n=0\n",
    "    def insert(self,x):\n",
    "        assert self.n<len(self.a)\n",
    "        self.a[self.n]=x\n",
    "        self.n+=1\n",
    "    def search(self,x):\n",
    "        for k in range(0,self.n):\n",
    "            if self.a[k]==x:\n",
    "                return k\n",
    "        return None\n",
    "    def delete(self,x):\n",
    "        k=self.search(x)\n",
    "        self.a[k]=self.a[self.n-1] # movemos el último al lugar vacante\n",
    "        self.n-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "None\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "d=Lista_secuencial()\n",
    "d.insert(30)\n",
    "d.insert(10)\n",
    "d.insert(25)\n",
    "print(d.search(10))\n",
    "print(d.search(80))\n",
    "d.delete(30)\n",
    "print(d.search(30))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La búsqueda secuencial también se puede implementar con una lista enlazada, en cuyo caso será más simple insertar al inicio.\n",
    "\n",
    "En cualquier caso, la búsqueda demora tiempo $\\Theta(n)$.\n",
    "Para estimar el costo promedio, suponemos que todos los elementos son igualmente probables de ser accesados y que el costo de buscar a un elemento que es el $k$-ésimo de la lista es $k$. Por lo tanto, el costo promedio es\n",
    "\n",
    "$$\n",
    "\\frac{1}{n}\\sum_{1\\le k \\le n} k = \\frac{n+1}{2}=\\Theta(n)\n",
    "$$\n",
    "\n",
    "Por lo tanto, este tipo de implementación solo será adecuada para conjuntos muy pequeños."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Búsqueda secuencial con probabilidades de acceso no uniformes\n",
    "\n",
    "En la práctica, es muy raro que las probabilidades de acceso a los elementos sean uniformes. Con frecuencia hay algunos elementos que son mucho más populares que otros, y empíricamente a menudo se observan distribuciones de tipo \"ley de potencias\", con probabilidades de tipo\n",
    "\n",
    "$$\n",
    "p_k \\propto \\frac{1}{k^{\\alpha}}\n",
    "$$\n",
    "\n",
    "para algún $\\alpha$. Para el caso $\\alpha=1$ esto se llama Ley de Zipf.\n",
    "\n",
    "Si un conjunto de datos tiene elementos con probabilidades de acceso diferentes, entonces para la búsqueda secuencial el orden en que estén los elementos en la lista hace una diferencia.\n",
    "\n",
    "### Caso 1. Probabilidades conocidas\n",
    "\n",
    "Si las probabilidades de acceso son conocidas, es fácil ver que el orden óptimo es en orden decreciente de probabilidad.\n",
    "\n",
    "Más precisamente, si los elementos son $X_1, X_2,\\ldots,X_n$ con probabilidades de acceso $p_1,p_2,\\ldots,p_n$ respectivamente, y si están ordenados de modo que $p_1\\ge p_2\\ge p_3\\ge \\cdots$, entonces el costo esperado de búsqueda óptimo es\n",
    "\n",
    "$$\n",
    "C_{OPT} = \\sum_{1\\le k\\le n} k p_k\n",
    "$$\n",
    "\n",
    "Tomemos como ejemplo el capítulo 1 de \"El Quijote\" (en minúsculas y sin puntuación para simplificar su proceso), cuyo texto está en el archivo `cap1.txt`:\n",
    "\n",
    "```\n",
    "en un lugar de la mancha de cuyo nombre no quiero acordarme no ha mucho\n",
    "tiempo que vivía un hidalgo de los de lanza en astillero adarga antigua\n",
    "...\n",
    "peregrino y significativo como todos los demás que a él y a sus cosas\n",
    "había puesto\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Acceso al archivo desde Colab\n",
    "\n",
    "Si este notebook está usándose en Google Colab, el archivo se debe almacenar en la carpeta `Colab Notebooks` de Google Drive, y para que el código en Python pueda tener acceso a él se debe quitar los comentarios y ejecutar la siguiente celda: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [],
   "source": [
    "#from google.colab import drive\n",
    "#drive.mount(\"/content/gdrive\")\n",
    "#%cd \"/content/gdrive/My Drive/Colab Notebooks/\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El costo óptimo para un archivo dado se puede obtener con el siguiente código en Python, en el cual hacemos uso de los diccionarios provistos por el lenguaje:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcula_costo_optimo(archivo): # lee el archivo, calcula frecuencias en orden descendente\n",
    "    f=open(archivo,\"r\")\n",
    "    texto=f.read()\n",
    "    palabras=texto.split()\n",
    "    frec={}\n",
    "    for x in palabras:\n",
    "        frec[x] = 1 if not x in frec else frec[x]+1\n",
    "    lista=[]\n",
    "    Copt=0\n",
    "    costo=0\n",
    "    for x in sorted(frec,key=frec.get,reverse=True):\n",
    "        costo+=1\n",
    "        Copt+=costo*frec[x]\n",
    "        lista.append((frec[x],x))\n",
    "    Copt/=len(palabras)\n",
    "    f.close()\n",
    "    return (Copt,lista)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Como resultado, mostramos el costo esperado de búsqueda en una lista ordenada de manera óptima (C_OPT) y las palabras más frecuentes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C_OPT=157.81\n",
      "\n",
      "(120, 'de')\n",
      "(105, 'y')\n",
      "(88, 'que')\n",
      "(44, 'a')\n",
      "(40, 'el')\n",
      "(38, 'en')\n",
      "(35, 'su')\n",
      "(33, 'la')\n",
      "(30, 'se')\n"
     ]
    }
   ],
   "source": [
    "(c,L)=calcula_costo_optimo(\"cap1.txt\")\n",
    "print('C_OPT={:6.2f}\\n'.format(c))\n",
    "for k in range(0,9):\n",
    "    print(L[k])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Caso 2: Probabilidades desconocidas\n",
    "\n",
    "Cuando las probabilidades son desconocidas, existen estrategias adaptativas, que van reordenando la lista dinámicamente a medida que los elementos son buscados, de modo de tratar de aproximar el orden óptimo. Hay dos técnicas que dan buenos resultados: \"traspose\" (TR) y \"move to front\" (MTF)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Transpose\n",
    "\n",
    "Esta técnica consiste en que cada vez que un elemento es accesado, se le mueve un lugar más adelante en la lista (a menos que ya esté en el primer lugar).\n",
    "Esto se puede implementar ya sea en un arreglo o en una lista enlazada. En la siguiente implementación usaremos una lista enlazada con cabecera.\n",
    "\n",
    "Si un elemento no se encuentra, simulamos como si hubiese estado al final de la lista. Para esto, mantendremos siempre disponible un nodo extra al final de la lista, en donde almacenaremos tentativamente la llave de búsqueda.\n",
    "Si finalmente se encuentra en ese nodo, se le incorpora a la lista y se crea un nuevo nodo extra.\n",
    "\n",
    "Para contabilizar el costo, el método `search` retorna el número de comparaciones de llaves que se hizo en la búsqueda."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodoLista:\n",
    "    def __init__(self,info,sgte=None):\n",
    "        self.info=info\n",
    "        self.sgte=sgte\n",
    "        \n",
    "class Lista_TR:\n",
    "    def __init__(self):\n",
    "        self.extra=NodoLista(0)\n",
    "        self.cabecera=NodoLista(0,self.extra)\n",
    "        \n",
    "    def search(self,x): # busca x (si no está lo inserta al final) y lo adelanta un lugar\n",
    "                        # retorna el costo de búsqueda\n",
    "        self.extra.info=x # agregamos x al final, en caso que no estuviera antes\n",
    "        p=self.cabecera\n",
    "        q=p.sgte\n",
    "        \n",
    "        # k cuenta el número de comparaciones de llaves\n",
    "        if q.info==x: # x ya está primero en la lista, no hacemos nada\n",
    "            k=1\n",
    "        else:\n",
    "            # buscamos del segundo en adelante\n",
    "            r=q.sgte\n",
    "            k=2\n",
    "            while r.info!=x:\n",
    "                (p,q,r)=(q,r,r.sgte)\n",
    "                k+=1\n",
    "            # r apunta al elemento buscado, lo movemos un lugar hacia adelante\n",
    "            (p.sgte,q.sgte,r.sgte)=(r,r.sgte,q)\n",
    "        if q.sgte is None: # se utilizó el nodo extra, agregamos uno nuevo\n",
    "            self.extra=NodoLista(0)\n",
    "            q.sgte=self.extra\n",
    "        return k\n",
    "\n",
    "    def imprimir(self):\n",
    "        p=self.cabecera.sgte\n",
    "        print(\"[\",end=\" \")\n",
    "        while p is not self.extra:\n",
    "            print(p.info,end=\" \")\n",
    "            p=p.sgte\n",
    "        print(\"]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test(Lista_adaptativa): # test interactivo\n",
    "    a=Lista_adaptativa()\n",
    "    while True:\n",
    "        x=input(\"x=\")\n",
    "        if x==\"fin\":\n",
    "            return\n",
    "        print(\"costo=\",a.search(x),end=\" \")\n",
    "        a.imprimir()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x=hola\n",
      "costo= 1 [ hola ]\n",
      "x=chao\n",
      "costo= 2 [ chao hola ]\n",
      "x=casa\n",
      "costo= 3 [ chao casa hola ]\n",
      "x=hola\n",
      "costo= 3 [ chao hola casa ]\n",
      "x=hola\n",
      "costo= 2 [ hola chao casa ]\n",
      "x=hola\n",
      "costo= 1 [ hola chao casa ]\n",
      "x=gato\n",
      "costo= 4 [ hola chao gato casa ]\n",
      "x=fin\n"
     ]
    }
   ],
   "source": [
    "test(Lista_TR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [],
   "source": [
    "def procesa(archivo,Lista_adaptativa): # lee el archivo y calcula costo promedio de búsqueda\n",
    "    f=open(archivo,\"r\")\n",
    "    texto=f.read()\n",
    "    palabras=texto.split()\n",
    "    npalabras=0\n",
    "    costo_acum=0\n",
    "    a=Lista_adaptativa()\n",
    "    for x in palabras:\n",
    "        costo_acum+=a.search(x)\n",
    "        npalabras+=1\n",
    "    print(\"Costo promedio de búsqueda= {:6.2f}\".format(costo_acum/npalabras))\n",
    "    f.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Costo promedio de búsqueda= 208.74\n"
     ]
    }
   ],
   "source": [
    "procesa(\"cap1.txt\",Lista_TR)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Move-To-Front\n",
    "\n",
    "Esta técnica consiste en que cada vez que un elemento es accesado, se le mueve al primer lugar de la lista (a menos que ya esté en el primer lugar). Si un elemento no se encuentra, simulamos como si hubiese estado al final de la lista."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Lista_MTF:\n",
    "    def __init__(self):\n",
    "        self.extra=NodoLista(0)\n",
    "        self.cabecera=NodoLista(0,self.extra)\n",
    "        \n",
    "    def search(self,x): # busca x (si no está lo inserta al final) y luego lo mueve al primer lugar\n",
    "        # retorna el costo de búsqueda\n",
    "        self.extra.info=x # agregamos x al final, en caso que no estuviera antes\n",
    "        p=self.cabecera\n",
    "        q=p.sgte\n",
    "        k=1 # cuenta el número de comparaciones de llaves\n",
    "        while q.info!=x:\n",
    "            (p,q)=(q,q.sgte)\n",
    "            k+=1\n",
    "        if q.sgte is None: # se utilizó el nodo extra, agregamos uno nuevo\n",
    "            self.extra=NodoLista(0)\n",
    "            q.sgte=self.extra\n",
    "        if k>1:  # x no está primero, move to front\n",
    "            (self.cabecera.sgte,p.sgte,q.sgte)=(q,q.sgte,self.cabecera.sgte)         \n",
    "        return k\n",
    "\n",
    "    def imprimir(self):\n",
    "        p=self.cabecera.sgte\n",
    "        print(\"[\",end=\" \")\n",
    "        while p is not self.extra:\n",
    "            print(p.info,end=\" \")\n",
    "            p=p.sgte\n",
    "        print(\"]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x=hola\n",
      "costo= 1 [ hola ]\n",
      "x=casa\n",
      "costo= 2 [ casa hola ]\n",
      "x=chao\n",
      "costo= 3 [ chao casa hola ]\n",
      "x=hola\n",
      "costo= 3 [ hola chao casa ]\n",
      "x=casa\n",
      "costo= 3 [ casa hola chao ]\n",
      "x=casa\n",
      "costo= 1 [ casa hola chao ]\n",
      "x=gato\n",
      "costo= 4 [ gato casa hola chao ]\n",
      "x=fin\n"
     ]
    }
   ],
   "source": [
    "test(Lista_MTF)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Costo promedio de búsqueda= 188.82\n"
     ]
    }
   ],
   "source": [
    "procesa(\"cap1.txt\",Lista_MTF)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En resumen, tenemos que para este texto en particular, el costo óptimo es 157.81, el costo promedio de TR es 208.74 y el de MTF es 188.82.\n",
    "\n",
    "Si en lugar de considerar un caso se analiza matemáticamente el caso general, suponiendo que los accesos llegan independientemente siguiendo la distribución dada y que el algoritmo corre durante un tiempo que tiende a infinito, se puede demostrar que\n",
    "\n",
    "$$\n",
    "C_{OPT} \\le C_{TR} \\le C_{MTF} \\le \\frac{\\pi}{2} C_{OPT}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Búsqueda en un arreglo ordenado: Búsqueda Binaria\n",
    "\n",
    "Ya hemos visto anteriormente que si los datos están en un arreglo ordenado, podemos hacer una búsqueda binaria, la que demora tiempo $\\lceil\\log_2{(n+1)}\\rceil=\\Theta(\\log{n})$ en el peor caso.\n",
    "\n",
    "Esto es bastante eficiente, pero tiene el problema que agregar o eliminar datos del arreglo toma tiempo $\\Theta(n)$ en el peor caso, por la necesidad de mantener el conjunto ordenado y compacto.\n",
    "Un objetivo que perseguiremos en el resto de este capítulo es tratar de encontrar estructuras de datos que nos permitan buscar de manera tan eficiente como la búsqueda binaria, junto con inserciones y eliminaciones igualmente eficientes.\n",
    "\n",
    "Pero antes de avanzar en esa dirección, consideremos la pregunta de si es posible buscar má rápido que la búsqueda binaria en el peor caso.\n",
    "\n",
    "### Cota inferior para la búsqueda por comparaciones\n",
    "\n",
    "Consideremos el problema de buscar una llave $x$ en un conjunto de tamaño 4, digamos $\\{a,b,c,d\\}$, con $a<b<c<d$. La siguiente figura ilustra una manera como podría hacerse esa búsqueda:\n",
    "\n",
    "![decision-tree](decision-tree.png)\n",
    "\n",
    "Este tipo de figura se llama un *árbol de decisión*, y en él los rombos representan preguntas y los rectángulos, las salidas (outputs) del algoritmo.\n",
    "\n",
    "Este árbol de decisión es uno entre la infinidad de árboles que podrían resolver el problema de la búsqueda. Lo importante que hay que observar es que todo algoritmo que funcione mediante comparaciones binarias (comparaciones con salidas \"Sí/No\") se puede representar por un árbol de decisión.\n",
    "\n",
    "En este tipo de árbol tenemos que:\n",
    "\n",
    "* La altura representa el número de comparaciones que hace el algoritmo en el peor caso, y\n",
    "* El número de hojas (cajas rectangulares) debe ser mayor o igual al número de respuestas posibles que debe ser capaz de emitir el algoritmo.\n",
    "\n",
    "Recordemos que si $N$ es el número de hojas y $h$ la altura, siempre se tiene $N\\le 2^h$, de donde se deduce que\n",
    "$h \\ge \\lceil\\log_2{N}\\rceil$ (porque la altura es un número entero), y en consecuencia, tenemos que\n",
    "\n",
    "$$\n",
    "\\text{Peor caso} \\ge \\lceil\\log_2{(\\text{número de respuestas distintas})}\\rceil\n",
    "$$\n",
    "\n",
    "Para el caso de la búsqueda binaria, tenemos que $N=n+1$, porque el algoritmo de búsqueda debe poder identificar a cada uno de los $n$ elementos, más la respuesta negativa cuando el elemento buscado no está. En consecuencia:\n",
    "\n",
    "**Todo algoritmo que busque en un conjunto de tamaño $n$ mediante comparaciones binarias debe hacer al menos\n",
    "$\\lceil\\log_2{(n+1)}\\rceil$ comparaciones en el peor caso.**\n",
    "\n",
    "Por lo tanto, la búsqueda binaria es óptima."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## Árboles de Búsqueda Binaria (ABBs)\n",
    "\n",
    "Un *árbol de búsqueda binaria* (*ABB*) es un árbol binario en que todos sus nodos internos cumplen la siguiente propiedad: Si la llave almacenada en el nodo es $x$, entonces todas las llaves en su subárbol izquierdo son menores que $x$, y las llaves en el subárbol derecho son mayores que $x$.\n",
    "\n",
    "![esquema-ABB2](esquema-ABB2.png)\n",
    "\n",
    "Los ABBs permiten realizar de manera eficiente (en promedio) las operaciones de inserción y búsqueda.\n",
    "\n",
    "### Búsqueda en un ABB\n",
    "\n",
    "La búsqueda es similar a una búsqueda binaria (de  ahí el nombre de estos árboles). Para buscar una llave $x$ se comienza en la raíz. Si $x$ se encuentra ahí, la búsqueda termina exitosamente. Si no está ahí, se continúa buscando  en el subárbol izquierdo si $x$ es menor que la raíz, o en el subárbol derecho si $x$ es mayor que la raíz. Si se llega a una hoja (nodo externo), la búsqueda concluye infructuosamente.\n",
    "\n",
    "### Inserción en un ABB\n",
    "\n",
    "Para insertar una llave $x$ en un ABB, se realiza una búsqueda, que debe ser infructuosa, y la hoja en donde termina la búsqueda se reemplaza por un nodo interno conteniendo la llave $x$, con dos nuevas hojas como hijos.\n",
    "\n",
    "![insercioABB](insercionABB.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación recursiva\n",
    "\n",
    "Los algoritmos de un ABB se prestan de manera natural a ser programados de manera recursiva, especialmente con la representación explícita de los nodos externos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Nodoi:\n",
    "    def __init__(self, izq, info, der):\n",
    "        self.izq=izq\n",
    "        self.info=info\n",
    "        self.der=der\n",
    "        \n",
    "    def search(self,x):\n",
    "        if x==self.info:\n",
    "            return self\n",
    "        if x<self.info:\n",
    "            return self.izq.search(x)\n",
    "        else:\n",
    "            return self.der.search(x)\n",
    "        \n",
    "    def insert(self,x):\n",
    "        assert x!=self.info\n",
    "        if x<self.info:\n",
    "            return Nodoi(self.izq.insert(x),self.info,self.der)\n",
    "        else:\n",
    "            return Nodoi(self.izq,self.info,self.der.insert(x))\n",
    "        \n",
    "    def __str__(self):\n",
    "        return \"(\"+self.izq.__str__()+str(self.info)+self.der.__str__()+\")\"\n",
    "\n",
    "class Nodoe:\n",
    "    def __init__(self):\n",
    "        pass\n",
    "    \n",
    "    def search(self,x):\n",
    "        return None\n",
    "    \n",
    "    def insert(self,x):\n",
    "        return Nodoi(Nodoe(),x,Nodoe())\n",
    "    \n",
    "    def __str__(self):\n",
    "        return\"☐\"\n",
    "\n",
    "class Arbol:\n",
    "    def __init__(self,raiz=Nodoe()):\n",
    "        self.raiz=raiz     \n",
    "        \n",
    "    def insert(self,x):\n",
    "        self.raiz=self.raiz.insert(x)\n",
    "        \n",
    "    def search(self,x):\n",
    "        return self.raiz.search(x)\n",
    "    \n",
    "    def __str__(self):        \n",
    "        return self.raiz.__str__()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hemos incluído una función `__str__` para poder visualizar (de forma algo rudimentaria) el árbol construído."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((☐10☐)42((☐50☐)77☐))\n"
     ]
    }
   ],
   "source": [
    "a=Arbol()\n",
    "a.insert(42)\n",
    "a.insert(77)\n",
    "a.insert(50)\n",
    "a.insert(10)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para probar nuestra implementación, definiremos una función `test`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test(a,x):\n",
    "    print(x, \"está\" if a.search(x) is not None else \"no está\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "50 está\n",
      "90 no está\n"
     ]
    }
   ],
   "source": [
    "test(a,50)\n",
    "test(a,90)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((☐10☐)42((☐50☐)77(☐90☐)))\n",
      "90 está\n"
     ]
    }
   ],
   "source": [
    "a.insert(90)\n",
    "print(a)\n",
    "test(a,90)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación no recursiva\n",
    "\n",
    "Las operaciones de búsqueda e inserción en el árbol no necesitan programarse recursivamente, porque se pueden realizar en una sola pasada de arriba a abajo, sin necesidad de volver hacia arriba. En este caso, toda esa funcionalidad se implementa dentro de la clase `Arbol`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Nodoi:\n",
    "    def __init__(self, izq, info, der):\n",
    "        self.izq=izq\n",
    "        self.info=info\n",
    "        self.der=der\n",
    "        \n",
    "    def __str__(self):\n",
    "        return \"(\"+self.izq.__str__()+str(self.info)+self.der.__str__()+\")\"\n",
    "\n",
    "class Nodoe:\n",
    "    def __init__(self):\n",
    "        pass\n",
    "    \n",
    "    def __str__(self):\n",
    "        return\"☐\"\n",
    "\n",
    "class Arbol:\n",
    "    def __init__(self,raiz=Nodoe()):\n",
    "        self.raiz=raiz\n",
    "        \n",
    "    def insert(self,x):\n",
    "        if isinstance(self.raiz, Nodoe):\n",
    "            self.raiz=Nodoi(Nodoe(),x,Nodoe())\n",
    "            return\n",
    "        p=self.raiz\n",
    "        while True:\n",
    "            assert x!=p.info\n",
    "            if x<p.info:\n",
    "                if isinstance(p.izq, Nodoe):\n",
    "                    p.izq=Nodoi(Nodoe(),x,Nodoe())\n",
    "                    return\n",
    "                p=p.izq\n",
    "            else: # x>p.info\n",
    "                if isinstance(p.der, Nodoe):\n",
    "                    p.der=Nodoi(Nodoe(),x,Nodoe())\n",
    "                    return\n",
    "                p=p.der\n",
    "                \n",
    "    def search(self,x):\n",
    "        p=self.raiz\n",
    "        while not isinstance(p, Nodoe):\n",
    "            if x==p.info:\n",
    "                return p\n",
    "            p=p.izq if x<p.info else p.der\n",
    "        return None\n",
    "    \n",
    "    def __str__(self):        \n",
    "        return self.raiz.__str__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((☐10☐)42((☐50☐)77☐))\n"
     ]
    }
   ],
   "source": [
    "a=Arbol()\n",
    "a.insert(42)\n",
    "a.insert(77)\n",
    "a.insert(50)\n",
    "a.insert(10)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "50 está\n",
      "90 no está\n"
     ]
    }
   ],
   "source": [
    "test(a,50)\n",
    "test(a,90)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((☐10☐)42((☐50☐)77(☐90☐)))\n",
      "90 está\n"
     ]
    }
   ],
   "source": [
    "a.insert(90)\n",
    "print(a)\n",
    "test(a,90)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Costo de búsqueda en un ABB\n",
    "\n",
    "#### Peor caso\n",
    "\n",
    "El peor caso para un árbol dado es la altura del árbol, y el peor árbol posible tiene altura $n$.\n",
    "Por lo tanto, el costo de búsqueda en el peor caso es $\\Theta(n)$.\n",
    "\n",
    "Lo anterior ocurre, por ejemplo, si los elementos se insertan en orden ascendente, o descendente, o en algún orden tipo \"zig-zag\". Es muy improbable que esto ocurra por casualidad, pero sí puede suceder si los datos provienen de algún otro proceso en que resultan naturalmente ordenados, o bien porque la secuencia de inserciones es generada por un adversario malicioso que busca hacer que el algoritmo funcione de la manera más lenta posible.\n",
    "\n",
    "#### Caso promedio\n",
    "\n",
    "Para analizar el costo esperado de búsqueda en un ABB con $n$ nodos, supondremos que en una inserción y en una búsqueda infructuosa, los $n+1$ nodos externos son igualmente probables como punto de destino de la búsqueda y de la inserción, y que en una búsqueda exitosa, los $n$ nodos internos son igualmente probables como punto de destino de la búsqueda.\n",
    "\n",
    "Recordemos que anteriormente definimos el *largo de caminos internos* (*LCI*) como\n",
    "$\n",
    "I_n=\\sum_{x\\in \\text{Nodos internos}}\\text{distancia}(\\text{raiz},x)\n",
    "$,\n",
    "y el *largo de caminos externos* (*LCE*) como\n",
    "$\n",
    "E_n=\\sum_{y\\in \\text{Nodos externos}}\\text{distancia}(\\text{raiz},y)\n",
    "$,\n",
    "para los cuales se cumple que\n",
    "$\n",
    "E_n=I_n+2n\n",
    "$.\n",
    "\n",
    "Utilizaremos las notaciones $C_n$ y $C'_n$ para el número esperado de comparaciones de llaves en una búsqueda exitosa e infructuosa, respectivamente. Entonces, tenemos que\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C_n &= 1 + \\frac{I_n}{n}\\\\\n",
    "C'_n &= \\frac{E_n}{n+1}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Reemplazando $E_n=I_n+2n$ en la fórmula para $C_n$, tenemos que\n",
    "\n",
    "$$\n",
    "C_n=1+\\frac{E_n-2n}{n}=\\frac{E_n}{n}-1=\\frac{n+1}{n}C'_n-1\n",
    "$$\n",
    "\n",
    "Por lo tanto, tenemos la siguiente relación entre los costos esperados de búsqueda exitoso e infructuoso:\n",
    "\n",
    "$$\n",
    "C_n=\\left( 1 +\\frac{1}{n}\\right) C'_n - 1\n",
    "$$\n",
    "\n",
    "de modo que, cuando $n \\rightarrow \\infty$\n",
    "\n",
    "$$\n",
    "C_n \\approx C'_n-1\n",
    "$$\n",
    "\n",
    "Para poder completar este análisis necesitamos una segunda ecuación que vincule a estas incógnitas.\n",
    "Para esto, observemos que _el costo de buscar un elemento que acaba de ser insertado es exactamente 1 más que el costo de buscarlo infructuosamente antes de su inserción_. Por lo tanto, si consideramos y promediamos los costos de búsqueda de los elementos en orden de inserción, tenemos que\n",
    "\n",
    "$$\n",
    "C_n=\\frac{(1+C'_0)+(1+C'_1)+\\cdots+(1+C'_{n-1})}{n}=1+\\frac{1}{n}\\sum_{0\\le k \\le n-1}C'_k\n",
    "$$\n",
    "\n",
    "Multiplicando ambos lados por $n$, tenemos\n",
    "\n",
    "$$\n",
    "nC_n=n+\\sum_{0\\le k \\le n-1}C'_k\n",
    "$$\n",
    "\n",
    "Sustituyendo $n$ por $n+1$ en esta ecuación, tenemos\n",
    "\n",
    "$$\n",
    "(n+1)C_{n+1}=n+1+\\sum_{0\\le k \\le n}C'_k\n",
    "$$\n",
    "\n",
    "Restando ambas ecuaciones, tenemos:\n",
    "\n",
    "$$\n",
    "(n+1)C_{n+1} - nC_n = 1+C'_n\n",
    "$$\n",
    "\n",
    "La relación que habíamos obtenido antes entre $C_c$ y $C'_n$ se puede reescribir como\n",
    "\n",
    "$$\n",
    "nC_n=(n+1)C'_n-n\n",
    "$$\n",
    "\n",
    "Reemplazando en la ecuación anterior, obtenemos:\n",
    "\n",
    "$$\n",
    "(n+2)C'_{n+1}-(n+1)-(n+1)C'_n+n=1+C'_n\n",
    "$$\n",
    "\n",
    "Lo que se simplifica a\n",
    "\n",
    "$$\n",
    "(n+2)(C'_{n+1}-C'_n)=2\n",
    "$$\n",
    "\n",
    "obteniéndose la ecuación de recurrencia\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C'_{n+1} &= C'_n+\\frac{2}{n+2}\\\\\n",
    "C'_0 &= 0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Esta ecuación se puede resolver \"desenrrollándola\", para obtener\n",
    "\n",
    "$$\n",
    "C'_n=2\\left(\\frac{1}{2}+\\frac{1}{3}+\\cdots+\\frac{1}{n+1}\\right)\n",
    "$$\n",
    "\n",
    "Si definimos los _números armónicos_ $H_n=1+\\frac{1}{2}+\\frac{1}{3}+\\cdots+\\frac{1}{n}$, podemos expresar la solución como\n",
    "\n",
    "$$\n",
    "C'_n=2(H_{n+1}-1)\n",
    "$$\n",
    "\n",
    "Los números armónicos son muy cercanos al logaritmo natural. Se puede demostrar que\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "H_n & \\le 1+\\int_1^n \\frac{1}{x}dx = 1+\\ln{n}\\\\\n",
    "H_n & \\ge \\int_1^{n+1} \\frac{1}{x}dx = \\ln{(n+1)}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "de donde obtenemos que\n",
    "\n",
    "$$\n",
    "\\ln{(n+1)} \\le H_n \\le 1+\\ln{n}\n",
    "$$\n",
    "\n",
    "Más precisamente, se puede demostrar que\n",
    "\n",
    "$$\n",
    "H_n = \\ln{n} + \\gamma + O\\left(\\frac{1}{n}\\right)\n",
    "$$\n",
    "\n",
    "donde $\\gamma\\approx 0.577\\ldots$ es la constante de Euler-Mascheroni."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "%pylab inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3Xl81NW9//HXSci+74EsJCEhLGFPAQU3XHFDpdpata1abW/rrW29drm3vd4u99fb1tv1aq/YurQq17Xaail1B0WWoBACgewhCSHJJCHJZM/M+f1xhrXBJJCZ+c7M5/l4zGOSyTczn69feHs437MorTVCCCF8R5C3CxBCCDExEtxCCOFjJLiFEMLHSHALIYSPkeAWQggfI8EthBA+RoJbCCF8jAS3EEL4GAluIYTwMVPc8abJyck6JyfHHW8thBB+aefOnTatdcp4jnVLcOfk5FBSUuKOtxZCCL+klKof77HSVSKEED5GglsIIXyMBLcQQvgYt/Rxj2Z4eJjGxkYGBgY89ZFuEx4eTmZmJiEhId4uRQgRgDwW3I2NjcTExJCTk4NSylMfO+m01rS3t9PY2Ehubq63yxFCBCCPdZUMDAyQlJTk06ENoJQiKSnJL/7lIITwTR7t4/b10D7KX85DCOGbPNZVIoQQ/qarf5jGzj4aO/tp6uxncMTJP104w+2fK8EthBCnYR8cobGzj4aO/pOfO81zz8DIScenxoRJcLvDI488wu7du3n44YePvTZ37lxefPFFZs2a5cXKhBCeNjTi5NCRfho6+zjYYYK5oaOPhs4+Gjr66OwbPun4iJBgshIjyIiP4BM5CWQlRJKREEFmQgSZCZEkRHpmpFnABXdpaSmLFi069v3AwAAHDx6koKDAi1UJIdxBa01n3zD17b2uYDYBfTSkm7v6cerjx4cEKzITIslMiKBo3lSyEiLJSowgy/VaYlSoJe5xBVxw79mzhzvuuOOk72fOnElwcLAXqxJCnCmHU9Pc1c/B9j7qO/qoa+81X7eboO4ZPLk7IyUmjOzESJbmJpKVGElWQgTZiZFkJUaSFhtOcJD3g3ks4wpupVQd0AM4gBGtdbE7i3KnvXv3csMNNxz7v6bdbufqq6/2clVCiI8z4nDSdKSfWlsv9e0mnI8+N3b0M+RwHjs2JFiRlRBJdlIkn8hJIDspiuzESFc4RxAZ6vvt1YmcwUVaa9tkfOj3/7KXfYe6J+OtjpkzLZYHrpn7scc0NDSQkpLC/v37j712zz33kJeXN6m1CCEmzuHUNHX2U2OzU2frpc4VzHW2Xho7+xk5oU8jMjSY7MRICtNiuGxOOtOTIpmeaMJ6alyET7Saz4bv/69nAkpLS5k79+Rw37dvH2vWrKGxsZHbbruNa6+9lq1bt/Lss896qUoh/JfWmraeQarbeqm19VJrs1Nr66PWZudgRx/DjuPhHBUaTE5yFHOnxXHV/KlMT4oiJymKnORIUqLDLNHX7C3jDW4N/F0ppYFHtNbrTj1AKXU3cDdAdnb2x77ZWC1jd9mzZw9z5sw56bW9e/cyf/58SkpKuO6667j33nu55ZZbvFKfEP6ib2iEmrZeamy91LTZqTkW1L3YT+hzDp0SRG5SFAWpMVw6J5285ChykiWcxzLe4F6htT6klEoFXldK7ddabzrxAFeYrwMoLi7Wo72Jt+3Zs+ek/uyOjg601qSlpbF7925uuOEGQGZGCjEeWmtaewapbrVT3Wanuq3XPLfaOdR1fEkIpSAjPoLc5CjWLs4gLyWavJQocpOjmBYXQZCfd2u4w7iCW2t9yPXcqpT6E7AU2PTxv2U9Tz/99EnfJyYm0traCkBVVRUzZ87EZrORnp7ujfKEsCSHU9PQ0UdVq53KVjtVrXaq2uzUtNpPGrERFRrMjNRoluYmkpcSzYyUaGakmu6N8BAZtTWZxgxupVQUEKS17nF9fRnwA7dX5mGPPfYYAMnJyTz44INerkYIzxt2OKlv76OypYdKV0hXtvRQY+tlaOT4qI3UmDDyU6O5fnEGM1KiyU81IZ0WK10bnjKeFnca8CfXBZkCPKO1/ptbqxJCuI3Dqalv76WixU5FSw8VLT1UttipsdlPujmYmRBBQWo0589MIT8lmvw0E9BxEbIOvbeNGdxa6xpggQdqEUJMIq01zV0DHGjp4cDhHioO93CgpYeqVjuDJ7SgsxIjmJkaw0WzUilIjWZmWgwzUqP8Yryzv5IrI4QfsA+OcOBwD/sPd7O/uefY190nLIKUFhtGYXos585IYmZaDIXpMeSnRktA+yC5YkL4EKdT09jZz77mLsqbeyhv7mb/4R4OdvQdOyYmbAqF6TFcs2Aas9JjKEyPZWZaNPGRoV6sXEwmCW4hLGpwxEHFYTv7mrvYd6ibfc3dlDf3HBsHrRTkJkcxLyOOm4ozmZUeS2F6DJkJEXKT0M9JcAthAfbBEfYd6qasqYuyQyaoq1rtx6Z5R4UGM2tqLNcvymDOtFhmT42lMC2GiFAZZheIJLiF8LCu/mH2NnWxp6mLskPd7G3qosbWe+znKTFhzJ0Wy8WzU5kzNY6502LJToyUiSriGAluIdyoZ2CYsqZu9jQdobTRhHV9+/H+6Iz4CIoyYrluUQbzMkxIp8aGe7Fi4QskuIWYJAPDDsqbuylt7GJ3wxF2Nx6hxtaLdg2NzoiPcPVHZzEvI46ijDgSo+SGoZi4gAvu6Oho7Ha7t8sQPk5rTa2tl10NR449ypu7j01gSY4OY2FWHGsWZjAvM475GXEkRYd5uWrhLwIuuIU4E139w+xqOMJHBzv56KBpTR9x7UcYFRrM/Mx47liZy6KseBZkxZMeGy4jOwKFYwS6m6CrAQZ7oHC12z8yIIO7rq6O1atXs3LlSrZs2UJGRgavvPIKERERAFx//fXMnTuXd999l8rKSp566ikuueQSL1ctPEVrTY2tl531nXxY38nO+k4qW82/0pSCmakxXDE3nUXZ8SzMSiA/NdrvF+4PaE4H9DTDkYPQWW+ej9Qf/767CbTDHBuZBN+scXtJARncAJWVlaxfv55HH32Um266iRdffJFbb70VgLKyMlasWMHmzZt56aWXePrppyW4/djAsIOypi521HWys76DnfWdx3b3josIYVF2PNcumMbi6QnMz4wjJlzW6vArWkN/J3TWmiDurDPB3FnvCugGcJ682zvR6ZAwHbKXQ3wWxE+H+Gzz8ADvBPeGb8PhPZP7nunzYPV/jfvw3NxcFi5cCMCSJUuoq6sDoK+vj66uLr7+9a8DMDIyQnx8/OTWKryqe2CYnXWdbK/rYEdtB6WNXcf2LMxLjuKS2WkU5ySwZHoieclRMgzPH4wMma6MzloTzEcfHa7noZ6Tj49MMmE8dQHMvtaEdHw2xOdAXCaEeHfkT8C2uMPCjt8oCg4Opr+/HzA74ixZsuTYru+lpaUUFRV5pUYxOdrtg2yv7WBbbQfbazsoP9yN1jAlSFGUEcfnV+RQPD2BJdMT5AaiLxvsgY5aE84dNSd8XQfdjaCPL6zFlHATzAk5MP0c85yQ43ptOoTFeOccxsk7wT2BlrGnlZWVHWuJgwnuNWvWeLEiMVHt9kG21XawtaadrTXtVLSY/unwkCCWTE/g3osLWJqbyMKseFlgydf0dZhA7qg5/jga1L1tJx8bmQyJuaY742gwJ+ZCQi5Ep0FQkDfOYFLIn9pT7Nmzh2XLlh37vqysTFrcFtfVP8y2mna2VLfzQXU7B1rMP3sjQ4MpzklkzcIMluclMi8jntApvvuXNWAMdEF7FbTXQEc1tFeb544a0xd9othME8aFqyExz4Ty0XAOj/VO/R6gtJ787SGLi4t1SUnJSa+Vl5cze/bsSf8sb/G38/ElA8MOdtZ38l6VjS1VNvY0deHUpkVdPD2Rc2YksTwvifmZcYQES1Bb0vCACeL2Ktej+vjXfbYTDlSmTzkx7/gjaQYkzjBdGiERXjuFyaaU2qm1Lh7PsdLiFpantWZfczebK228X2Vje20HgyNOpgQpFmbFc8+qAlbMSGJhdjxhU2TRJcvQGroPga3CBLKtEtorzddHGoATGo3R6SaQZ10JSfkmmJNmmJazl28EWpEEt7CkdvsgmyttbKpoY1OlDZt9EICZadHcsmw6KwuSWJqbRHSY/BH2uuEB05VhqzDhbKtwPapg+PjiWYRGmzDOXAoLb3EFdJ559uNuDXeQP/XCEhxOze7GI7yzv5V3K9oobepCa0iMCmVlfjLnz0xhZX4y6XHS+vKagS5oq4C2/WA7YL62HTDjnY+1nhXEZUFyPiw+F5ILzCOpAGLSzQwmcdY8Gtxaa7+YBuyO+wKB6EjfEO9WtPHW/lY2VbTR2TdMkIJF2Ql845KZXFCYQtG0OBlH7Wl9HSac2/ZD24Hjzz3Nx48JDjMt5WmLYP6nXQE907wWGum92gOEx4I7PDyc9vZ2kpKSfDq8tda0t7cTHi4tvzNR3WbnjX0tvFneSkl9B04NSVGhXFSYykWzUjmvIFm22PKU/iMmlFvLzaOtHFr3Q2/r8WNCoiClEPIuNM8ps0xAJ+RAkNxP8BaPBXdmZiaNjY20tbWNfbDFhYeHk5mZ6e0yfILDqfnwYCev72vh9X0t1Lo2DJg9NZavXJTPqlmpLMiMl1a1Ow33mxZz6z7zaNlngrrn0PFjQqNNMBdcasI5dbb5PjbTp8c7+yuPBXdISAi5ubme+jjhRYMjDrZUt7Ox7DBvlLdgsw8REqxYnpfEHStyWDU7jYx4/xnGZRlOJ3QdhJa9rkeZee6oOT5rMDgMUmZC7nmQOscV0LNMv7QEtM+Qm5NiUvQPOXi3opUNZYd5q7yVnsERosOmcNGsVC6bk8YFhSnEyuJMk2fQblrPh/ccD+iWfSesuaHMRJTUOVC01hXSc8wojmD5a+/r5AqKM9Y/5OCdA628uqeZt8pb6R92kBAZwpXzpnJFUTrn5ifJuOqzpTXYW6C5FA6XmqA+vMe0oo+O5AiLg/QiWHizCef0eaYVHRbt1dKF+0hwiwkZHHGwqcLGX3Yf4o3yFvqGHCRHh3LD4gyumjeVpbmJTJHZimfG6TTrbjTvNiF9NKxPXIMjIccE8/xPmbBOn2e6OXz4hr+YOAluMSaHU7Otpp2XdzWxoewwPQMjJESGsGZhBtfMl7A+I06nmUHYvMsE9aFdJqQHu83Pg6ZAymwouAzS58PU+ZA2F8LjvFu3sAQJbnFa5c3d/OmjJl7Z1URL9yBRocFcPjedaxdOY0V+sqwDMl5am66NQx8dfzSXHu+PnhJuQnnejWb956nzTZfHFFliVoxOglucpK1nkFd2NfHCzkb2H+5hSpDiwsJUvnf1NC6elUZEqPRZj6n7EDTthKYPzXPzLjPrEExIp8+DBZ+GaQth6kIz7C5YbtyK8Rt3cCulgoESoElrfbX7ShKeNuxw8tb+Vp4vaeSdA62MODULsuL5wZq5XD1/GolRMiHmtAZ7TAu6scQV1juPzzAMmmJa0nOvh2mLIWOxuWkoIS3O0kRa3PcC5YCsBuMnqtvsPLejgRc/bMJmHyQ1Jow7z8vlxiWZ5KdaewcQr3A6zep2jTvMo2GHmW14dIx0Qi7krISMYhPS6fNlZTvhFuMKbqVUJnAV8J/AN9xakXCrwREHfys7zDPbDrKttoMpQYpVs1L51CeyuGBmitxkPNFgj2lBN2yHhm0mrI92eYTHQeYnYPY1kFkMGUsgMtG79YqAMd4W9y+BbwKnbYYppe4G7gbIzvbMTsdi/Bo6+nh620GeK2mgo3eI7MRIvnlFIZ9ckklqjLQKAehqhINbzaNhq5nUop2AMjMM51wHWUtNYCcVyExD4TVjBrdS6mqgVWu9Uyl14emO01qvA9aB2QFn0ioUZ8zp1GyusvHkljrePtBKkFJcOjuNW5Zns2JGcmCvD6K1Wb+j/n04+IEJ664G87OQKNOKPv/+40Etw/CEhYynxb0CuFYpdSUQDsQqpZ7SWt/q3tLEmeodHOGFnY08uaWOGlsvydFh/PNF+dy8LJupcQG6RojTYWYc1m8xYV2/Bfo7zM+i0yD7HDjnHrOxbFqRTAsXljbmn06t9XeA7wC4Wtz/IqFtTYeO9PPkljqe2X6QnoERFmTF88tPLeTKeVMDb5Pco0Fdtxnq3oP6D2DQ1T+dkGM2l51+rgnsxDyZeSh8ijQr/MC+Q92s21TNX0rNMLQritK5c2Uui7MTvFyZB2ltFl2q3QS1m6H+veM3EpPyYe51kHOeCeu4DO/WKsRZmlBwa63fAd5xSyViQrTWbKvt4OF3qtlU0UZUaDCfPzeH21fkkJkQIDuQHDkINe+YR+2m42t6JOTAnDWQc74Znhc71YtFCjH5pMXtY7TWvH2glYfermZnfSfJ0aHcf3khty6bTlykn0/sGOgyremat6H6bbNBLZg+6ryLIO8CyD0f4mVUk/BvEtw+QmvN6/ta+PVblZQ1dZMRH8EP1szlpuIswkP8dBq602EWX6p+E6reNOOotcOM+shZCUvvcm2pNUv6qEVAkeC2OK01b5a38os3Kth7qJvpSZH8dO18rl+c4Z+LPPXaTEhXvW6e+zsAZdb1WPk1mLEKMpfCFJmGLwKXBLdFaa15v6qdB/9+gF0NR5ieFMmDNy7guoXT/Gt2o9ZmWdPKv0PFRjNTEQ2RyWb/w/xLTFhHJXu7UiEsQ4Lbgkobj/BfG/azpbqdjPgIfrJ2HjcszvSfFvZwv7mhWPE3E9Y9zYAy63tc+B0ouASmLpKZiUKchgS3hdS39/LTjQd4rbSZxKhQHrhmDp9Zlu0f23/12uDABvOofgtG+s3O4jNWmTHV+ZdCdIq3qxTCJ0hwW0BX/zAPvV3FE+/XERyk+OqqfO46P48YX99c98hBKH8V9r9qppVrJ8RmwqJbTVjnrJTNAoQ4AxLcXuRwap7ZfpCf//0AR/qHuXFJJvddVkharA8v+mSrgn0vQ/lfzAYCAKlz4bx/gVlXmR1eZASIEGdFgttLdtR18MAre9nX3M3yvES+d/Uc5k7z0YWMbFWw90/m0brXvJZRDJd83yx7mjTDu/UJ4WckuD3MZh/k//21nJc+bGJqXDj/85lFXDVvKsrXWqGddVD2Eux9yawJApC1HC7/Mcy5FuIyvVqeEP5MgttDnE7NcyUN/HjDfvqGRvjyhTO4Z1U+kaE+dAnsraZVved5MxkGzJKnl//YrAUSO8279QkRIHwoNXxXTZudb7+4h+11HSzNTeQ/ryuiIM1HtgYb6oP9r0Hps2Y0iHaYZU8vfgCK1kLCdG9XKETAkeB2oxGHk9+9V8svXq8gbEoQP107nxuLM63fLeJ0wsEtsGu9udE4ZIe4LFhxL8y/yewGI4TwGgluN6lus/ON53azu+EIl81J40fXFZFq9dEiRw6asN71NByph9AY0wWy4GbIPlcmxAhhERLck8zp1Pxxaz0/3lBOeEgwv7l5EVfPt/DNx5EhOPAa7HzSzGZEQ+4FsOq7MOtqCA2QJWKF8CES3JOotWeA+57bzeZKGxcWpvCTtfOtOya7vRp2PgG7noE+m5kYc8G3YOFnpN9aCIuT4J4k7xxo5b7ndmMfHOGH1xVx67Js67WyHSNQsQF2/N6saa2CzQzGJbfDjIsgyA+m1gsRACS4z9Kww8nPNh5g3aYaCtNiWH/3cmZabcSIvQ0+fBJKHofuRtO6vui7Zuq57A4jhM+R4D4Lrd0D3PPMR2yv6+CWZdl87+o51trUoLkUtv2vGXftGDKbDlz5U5h5hbSuhfBhEtxnaFtNO/es/wj7wAi//NRCrltkkQ1onU6o3Ahb/sdsmBsSCYs/C0u/CCkzvV2dEGISSHCfgae31fPAK3vJTozkqTuXUZhuga6R4QHYvR4+eAjaK013yKU/hMW3QUQA7fYuRACQ4J6AYYeTH766jz98UM+FhSn8+uZFxHp76dWBLih5DD54GHpbYepCWPt7s8t5sI8vCyuEGJUE9zh1Dwzz5ac+5L0qG3efn8e3rphFcJAXR430tsPWh2H7OhjsNhsSrPw65Jwny6YK4eckuMehuauf2x/fQVWrnZ99cj43Fmd5rxh7G2z5tRnSN9xnlk097z6zma4QIiBIcI/hwOEePv/4dnoGRnji9qWsLPDSprW97bDlV7D9URgZgKJPmsBOneWdeoQQXiPB/TF21nfw+cd3EBkazHNfPIc502I9X8RAF2z5jenDHu6DeTfCBd+E5ALP1yKEsAQJ7tPYUmXjC38oIS02nD/euZTMBA+v2THcb1rX7/0c+jth7vVmB/SUQs/WIYSwHAnuUby1v4UvPfUhuUlR/PELS0mN8eB6I04n7HkO3vyhmeWYfwms+p70YQshjpHgPsUb+1r40lM7mT01lj/csZSEqFDPfXjtZtj4r3C41Azru/63kHu+5z5fCOETxgxupVQ4sAkIcx3/gtb6AXcX5g2bKtr48tMfMndaLH/8wjLPjdHurIO/f9fsjB6XBTf8zuwuI+tfCyFGMZ4W9yCwSmttV0qFAO8ppTZorbe6uTaP+qC6nbv+UEJ+ajR/uMNDoT3cD5t/Du//yqwdctF34dx7ICTC/Z8thPBZYwa31loDdte3Ia6HdmdRnrar4Qh3PrmD6UmR/PHOpcRFeiC0D2yADd80u84UfRIu/QHEWWS9EyGEpY2rj1spFQzsBPKBh7TW29xalQfV2Xq544kdJEeH8dQXlpEUHebeD+w+BH+9H/a/CsmF8Lm/SD+2EGJCxhXcWmsHsFApFQ/8SSlVpLUuO/EYpdTdwN0A2dnZk16oO9jsg3zu8e1orXnyDjePHnE6oeT38Mb3wTkMl/wHLP8KTPHgzU8hhF+Y0KgSrfURpdQ7wBVA2Sk/WwesAyguLrZ8V0rf0Ah3PrGDlu4BnrlrObnJUe77sPZqeOUrcPADs5/jNb+ExDz3fZ4Qwq+NZ1RJCjDsCu0I4BLgJ26vzI201tz/QimlTV2su62YxdluWvbU6TSLQL3xHxAcCmseNns6yiJQQoizMJ4W91TgSVc/dxDwnNb6VfeW5V6/fbea10qb+fbqWVw6J809H9LVCH/6EtRthoLL4JpfQew093yWECKgjGdUSSmwyAO1eMTbB1r52cYDXLNgGl88303dFWUvwatfA6cDrv0NLLpNWtlCiEkTUDMn62y9fHX9R8xOj+Wna+dP/i7sQ73w12/CrqcgoxjWPip92UKISRcwwT004uSe9R8SpBSP3LaEiNBJ3iy3dT88/zloOwDn3w8XfEt2oBFCuEXABPfPNu6nrKmbR25bQlbiJK/0t2s9vPYNCI2Cz75sdlMXQgg3CYjgfreijUc313Lb8ulcPjd98t7YMWwWhdq+zmwZtvZ3EDOJ7y+EEKPw++Bu6xnkvud2UZgWw79dNXvy3tjeCs99Dg5ugXPugUu+D8F+/59TCGEBfp803315D90DIzxz13LCQyapX/vwHnjm09DXblbym3/j5LyvEEKMg18H94Y9zWzc28K3rpjFzLSYyXnTir/DC7dDWCzc8TfZ4EAI4XF+u+BzV98w33tlL3OnxXLXebmT86bbH4X1nzJD/O56U0JbCOEVftvi/tFr++jsG+KJ2z/BlOCz/P+T1vDWj2DzgzDzClj7ewiLnpxChRBigvwyuN+vsvH8zkb+6cIZFGXEnd2bOR3w2n2w83EzA/LqX8pNSCGEV/ldAo04nPzHn/cyPSmSey8uOMs3G4KX7oJ9L8PKr8PFD8jUdSGE1/ldcK/f0UBlq53/vXXJ2Y0iGRmC5z8PB16Dy34E5/7zpNUohBBnw6+Cu3tgmF+8XsGy3EQun3sWq/6NDJox2hUb4MoHYeldk1ekEEKcJb8K7ofeqqKzb4jvXT3nzBeQGhmCZ2+Dyo0S2kIIS/Kb4D7Y3sfj79exdnHmmd+QdDpMn3blRrjq5/CJOye3SCGEmAR+M477v18/QHCQ4v7LC8/sDbQ2C0Xtexku/aGEthDCsvwiuGttvfxl9yE+e8500mLPcMPfN38AO5+Ald+AFV+d1PqEEGIy+UVw//adKkKCg7jzTGdIbn8U3vs5LLkdLv73yS1OCCEmmc8Hd9ORfl76sImbl2aTGnMGre2qN2DDt8yMyKv+W8ZpCyEsz+eD+5F3q1EK7j6T/SNby+H52yF1jpnGHjTJu+IIIYQb+HRwt3YP8H87GvjkkkymxUdM7Jd7bfDMTRASAZ/5P1l7RAjhM3x6OODv3qtlxOHkSxfMmNgvOh3w4hegpwXu2ABxme4pUAgh3MBng3tg2MGzOxpYXTSV6UlRE/vld38KNW/DNb+GjCXuKVAIIdzEZ7tK/rqnma7+YW5Zlj2xX6x6A979CSz4DCz+rHuKE0IIN/LZ4H5m20Fyk6M4Z0bS+H+pqxFevMvcjJQRJEIIH+WTwX3gcA8l9Z18Zmn2+NckcTrh5S+bBaRu+gOERrq3SCGEcBOf7ON+Zls9ocFBrF0ygZuKO34Hte+ajRCS891XnBBCuJnPtbj7hxy89FETq+elkxgVOr5fslXB6/8O+ZfCks+7tT4hhHA3nwvuv5QeomdghM8sHedNSccI/OmLMCUMrv2N9GsLIXzemMGtlMpSSr2tlCpXSu1VSt3ricJO5/mSBmakRLE0N3F8v7D1IWgqMTcjY6e6tzghhPCA8bS4R4D7tNazgeXAV5RSc9xb1uhauwcoqe/k2gUZ47sp2dUI7/wEZq6GeZ90f4FCCOEBYwa31rpZa/2h6+seoBzIcHdho9m4rwWtYfW89HH+wr+CdsDq/3JvYUII4UET6uNWSuUAi4Bt7ihmLH8rayYvJYqC1HGsK1L1Jux7Bc77F0jIcXttQgjhKeMObqVUNPAi8DWtdfcoP79bKVWilCppa2ubzBoB6OwdYmtNB1fMTR+7m2RkEP56PyTmyaYIQgi/M67gVkqFYEL7aa31S6Mdo7Vep7Uu1loXp6SkTGaNALxe3oLDqVldNI4bjFsfho5quPJnZjSJEEL4kfGMKlHA74FyrfXP3V/S6P5WdpiM+AiKMmI//sD+TnjvF1BwOeRf4pnihBDCg8bT4l4B3AasUkrtcj2udHNdJ+kZGOa9ShtXFI2jm2QG7RpQAAAKhElEQVTLb2CgCy7+nmeKE0IIDxtzyrvW+j3Aq7NW3trfypDDyeqiMUaT2Fth62+haC2kz/NMcUII4WE+MXNy497DpMSEsTg74eMP3Pzf5sbkhf/qmcKEEMILLB/cDqdmc6WNVYWpBAV9TMP/yEEoeQwW3SKLSAkh/Jrlg/vA4R56BkZYljfGFPfNrvumF3zL/UUJIYQXWT64t9e2A3z82iS97bB7PSy4WfaPFEL4PcsH9466TjLiI8hM+JiND0oeg5EBWP5lzxUmhBBeYung1lqzrbbj41vbI4Ow41GYcTGkzvJccUII4SWWDu5aWy82++DHB3fZS2BvgXOktS2ECAyWDu7ttR3Ax/Rva23W206ZZVrcQggRACwf3MnRoeQlR41+QN17cHgPLP8n2dlGCBEwLB3cR/u3TzvNffsjEJkE8z/l2cKEEMKLLBvcjZ19NB3pZ2nOabpJ+jqgYqMJ7ZAIzxYnhBBeZNng3lF3tH87afQD9r0MjiGYf5MHqxJCCO+zbHBvr+0gNnwKhekxox9Q+hwkF8LUhZ4tTAghvMzSwV2ck0jwaOuTdNbBwQ9gwafkpqQQIuBYMrgHhh3U2nopyogb/YDS58zzvBs9V5QQQliEJYO7rr0Xp4b80TYF1hpKn4XpKyE+2/PFCSGEl1kyuKta7QDkp4wS3E0fQnuV6SYRQogAZMngrmyxE6QgL2WUiTelz0JwGMy+1vOFCSGEBVgyuKva7GQlRhIeEnzyD7SG/a9BwaUQEe+d4oQQwsssGdzVrfbRu0lsFdDdKLu3CyECmuWCe8ThpKatd/Qbk1VvmOd8WVBKCBG4LBfcDZ39DDmcpw/u5EIZTSKECGiWC+5jI0pODe6hPqh7X1rbQoiAZ7ngrmztAWDGqcFd/z44BiW4hRABz3LBXdVqJz02nNjwkFN+8CZMCYfpK7xTmBBCWITlgru61X76/u2clbKEqxAi4FkquLXWVI0W3J110F4pwwCFEAKLBXdz1wC9Q45/7N+uetM8y76SQghhreA+OqKk4NTgrn4L4rIhucALVQkhhLWMGdxKqceUUq1KqTJ3FzPqUECtzdrbuefJ2ttCCMH4WtxPAFe4uQ4AKlvtxEeGkBQVevzFrkboa4dpizxRghBCWN6Ywa213gR0eKAWqlvtFKRGn7yre/Nu8yxblAkhBGC1Pu62UUaUNO8CFQzpRd4pSgghLGbKZL2RUupu4G6A7OyJryUy4nBy89IsFmUlnPyDQ7sgZZaM3xZCCJdJC26t9TpgHUBxcbGecCHBQdx/+axT39S0uAsum5QahRDCH1iqq+QfdB+C3jbp3xZCiBOMZzjgeuADoFAp1aiUutP9Zbk07zLPUxd47COFEMLqxuwq0Vrf7IlCRnVoF6ggSJ/ntRKEEMJqrN1V0rzLbJwQGuntSoQQwjKsG9xamxb3NOnfFkKIE1k3uHuaobdVbkwKIcQprBvch1w3JqXFLYQQJ7FucDfLjUkhhBiNdYP70C5IngmhUd6uRAghLMW6wd1SBunzvV2FEEJYjjWD2zFsZk0m5nq7EiGEsBxrBnf3IUBDbIa3KxFCCMuxaHA3mee4TO/WIYQQFmTN4O5qNM9xWd6tQwghLMiiwd1gnuOkq0QIIU5l0eBuhIhEGQoohBCjsG5wS2tbCCFGZdHgbpL+bSGEOA2LBnejjCgRQojTsF5wD3TBYJcEtxBCnIb1grvLNYZbJt8IIcSorBfcxybfSB+3EEKMxnrBfWwMt3SVCCHEaCwY3I2ggiEm3duVCCGEJVkzuGMzICjY25UIIYQlWTO4ZfKNEEKclkWDW/q3hRDidKwV3E6HWYtbglsIIU7LWsFtbwXnsAS3EEJ8DGsFt6zDLYQQY7JYcLvGcMusSSGEOC1rBbdsWSaEEGMaV3Arpa5QSh1QSlUppb7ttmq6GiE0BsLj3PYRQgjh68YMbqVUMPAQsBqYA9yslJrjlmqODgVUyi1vL4QQ/mA8Le6lQJXWukZrPQT8H7DGLdV0NcjkGyGEGMN4gjsDaDjh+0bXa5NPJt8IIcSYxhPco/Vb6H84SKm7lVIlSqmStra2iVfidEL+pZB97sR/VwghAsiUcRzTCJw4sDoTOHTqQVrrdcA6gOLi4n8I9jEFBcENj0z414QQItCMp8W9AyhQSuUqpUKBTwN/dm9ZQgghTmfMFrfWekQpdQ+wEQgGHtNa73V7ZUIIIUY1nq4StNZ/Bf7q5lqEEEKMg7VmTgohhBiTBLcQQvgYCW4hhPAxEtxCCOFjJLiFEMLHKK0nPldmzDdVqg2on8CvJAO2SS/E2gLxnCEwzzsQzxkC87zP5pyna61TxnOgW4J7opRSJVrrYm/X4UmBeM4QmOcdiOcMgXnenjpn6SoRQggfI8EthBA+xirBvc7bBXhBIJ4zBOZ5B+I5Q2Cet0fO2RJ93EIIIcbPKi1uIYQQ4+TV4PbYJsReppTKUkq9rZQqV0rtVUrd63o9USn1ulKq0vWc4O1aJ5tSKlgp9ZFS6lXX97lKqW2uc37WtVSwX1FKxSulXlBK7Xdd83P8/Vorpb7u+rNdppRar5QK98drrZR6TCnVqpQqO+G1Ua+tMn7tyrdSpdTiyarDa8Ht0U2IvW8EuE9rPRtYDnzFda7fBt7UWhcAb7q+9zf3AuUnfP8T4Beuc+4E7vRKVe71K+BvWutZwALM+fvttVZKZQBfBYq11kWY5Z8/jX9e6yeAK0557XTXdjVQ4HrcDfx2sorwZovbc5sQe5nWullr/aHr6x7MX+QMzPk+6TrsSeA671ToHkqpTOAq4Heu7xWwCnjBdYg/nnMscD7wewCt9ZDW+gh+fq0xS0RHKKWmAJFAM354rbXWm4COU14+3bVdA/xBG1uBeKXU1Mmow5vB7blNiC1EKZUDLAK2AWla62Yw4Q6keq8yt/gl8E3A6fo+CTiitR5xfe+P1zwPaAMed3UR/U4pFYUfX2utdRPwIHAQE9hdwE78/1ofdbpr67aM82Zwj2sTYn+ilIoGXgS+prXu9nY97qSUuhpo1VrvPPHlUQ71t2s+BVgM/FZrvQjoxY+6RUbj6tNdA+QC04AoTDfBqfztWo/FbX/evRnc49qE2F8opUIwof201vol18stR//p5Hpu9VZ9brACuFYpVYfpBluFaYHHu/45Df55zRuBRq31Ntf3L2CC3J+v9SVArda6TWs9DLwEnIv/X+ujTndt3ZZx3gzugNmE2NW3+3ugXGv98xN+9Gfgc66vPwe84una3EVr/R2tdabWOgdzbd/SWt8CvA180nWYX50zgNb6MNCglCp0vXQxsA8/vtaYLpLlSqlI15/1o+fs19f6BKe7tn8GPusaXbIc6DrapXLWtNZeewBXAhVANfBv3qzFzee5EvNPpFJgl+txJabP902g0vWc6O1a3XT+FwKvur7OA7YDVcDzQJi363PD+S4ESlzX+2Ugwd+vNfB9YD9QBvwRCPPHaw2sx/TjD2Na1Hee7tpiukoecuXbHsyom0mpQ2ZOCiGEj5GZk0II4WMkuIUQwsdIcAshhI+R4BZCCB8jwS2EED5GglsIIXyMBLcQQvgYCW4hhPAx/x/hpAMHNaOf6wAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "H=np.zeros(100)\n",
    "n=range(1,101)\n",
    "H[0]=1;\n",
    "for k in range(1,100):\n",
    "    H[k]=H[k-1]+1/(k+1)\n",
    "plt.plot(n,H,label='$H_n$')\n",
    "plt.plot(n,log(n), label='$\\ln{n}$')\n",
    "leg=plt.legend(loc='best')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Por lo tanto, el costo esperado de búsqueda (exitosa o infructuosa) en un ABB es aproximadamente $2H_n \\approx 2\\ln{n} \\approx 1.386 \\log_2{n}$, lo cual es solo $38.6$ por cierto peor que un árbol óptimo, cuyo costo de búsqueda es $\\log_2{n}$.\n",
    "\n",
    "Se puede demostrar que la varianza también es logarítmica, por lo que en la práctica el tiempo de búsqueda debería ser cercano al promedio.\n",
    "\n",
    "Sin embargo, este análisis supone que las inserciones llegan en orden aleatorio, lo cual no necesariamente se cumple en la vida real. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Eliminación en un ABB\n",
    "\n",
    "La eliminación de una llave $x$ es sencilla de efectuar en algunos casos, pero el caso complicado es cuando la llave tiene dos hijos:\n",
    "\n",
    "#### Eliminación de una llave sin hijos\n",
    "\n",
    "En este caso, el nodo interno que contiene a $x$ desaparece y en su lugar queda un nodo externo:\n",
    "\n",
    "![eliminacionABB1](eliminacionABB1.gif)\n",
    "\n",
    "#### Eliminación de una llave con 1 hijo\n",
    "\n",
    "En este caso, el padre de la llave $x$ pasa a apuntar al único hijo de $x$:\n",
    "\n",
    "![eliminacionABB2](eliminacionABB2.gif)\n",
    "\n",
    "#### Eliminación de una llave con 2 hijos\n",
    "\n",
    "Si $x$ tiene 2 hijos, no podemos eliminarla directamente, pero sí podemos eliminar a la que la sigue en orden ascendente, digamos $y$. Se puede demostrar que $y$ necesariamente es unos de los dos casos anteriores, de modo que es fácil de eliminar. Luego de concluído ese proceso, escribimos $y$ en lugar de $x$ en el campo `info` del nodo respectivo.\n",
    "\n",
    "![eliminacionABB3](eliminacionABB3.gif)\n",
    "\n",
    "Por simetría, esto mismo podría haberse hecho con la llave que sigue a $x$ en orden descendente.\n",
    "\n",
    "El análisis del costo esperado de búqueda que hicimos anteriormente es válido si solo hay inserciones. El análisis en el caso en que se incluyen eliminaciones es un un problema matemáticamente muy complicado, y sigue siendo un problema abierto. La evidencia experimental indica que se obtienen mejores resultados si se alterna o si se aleatoriza al elegir entre sucesor o el predecesor de $x$ en caso que haya que elegir."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación recursiva de la eliminación\n",
    "\n",
    "Por simplicidad, omitimos el código para la inserción y búsqueda, y en el caso de un nodo con 2 hijos, eliminamos siempre el sucesor. También ignoramos las eliminaciones de llaves que no están en el árbol."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Nodoi:\n",
    "    def __init__(self, izq, info, der):\n",
    "        self.izq=izq\n",
    "        self.info=info\n",
    "        self.der=der\n",
    "    \n",
    "    def deletemin(self): # Elimina llave mínima del árbol, retorna (llave_min,raiz_arbol_restante)\n",
    "        if isinstance(self.izq,Nodoe): # No hay hijo izquierdo\n",
    "            return (self.info,self.der)\n",
    "        # hay hijo izquierdo\n",
    "        (llave_min,izq_sin_min)=self.izq.deletemin()\n",
    "        return (llave_min,Nodoi(izq_sin_min,self.info,self.der))\n",
    "        \n",
    "    def delete(self,x):\n",
    "        if x<self.info:\n",
    "            return Nodoi(self.izq.delete(x),self.info,self.der)\n",
    "        if x>self.info:\n",
    "            return Nodoi(self.izq,self.info,self.der.delete(x))\n",
    "        # x==self.info\n",
    "        if isinstance(self.izq,Nodoe): # No hay hijo izquierdo\n",
    "            return self.der\n",
    "        if isinstance(self.der,Nodoe): # No hay hijo derecho\n",
    "            return self. izq\n",
    "        # Hay hijo izquierdo y derecho\n",
    "        (y,der_sin_min)=self.der.deletemin()\n",
    "        return(Nodoi(self.izq,y,der_sin_min))\n",
    "        \n",
    "    def __str__(self):\n",
    "        return \"(\"+self.izq.__str__()+str(self.info)+self.der.__str__()+\")\"\n",
    "\n",
    "class Nodoe:\n",
    "    def __init__(self):\n",
    "        pass\n",
    "    \n",
    "    def delete(self,x):\n",
    "        return self\n",
    "    \n",
    "    def __str__(self):\n",
    "        return\"☐\"\n",
    "\n",
    "class Arbol:\n",
    "    def __init__(self,raiz=Nodoe()):\n",
    "        self.raiz=raiz     \n",
    "        \n",
    "    def delete(self,x):\n",
    "        self.raiz=self.raiz.delete(x)\n",
    "    \n",
    "    def __str__(self):        \n",
    "        return self.raiz.__str__()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para probar este algoritmo utilizaremos el árbol que vimos en el capítulo 4:\n",
    "\n",
    "![ejemplo-ABB](ejemplo-ABB.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=Arbol(\n",
    "    Nodoi(\n",
    "        Nodoi(\n",
    "            Nodoi(Nodoe(),15,Nodoe()),\n",
    "            20,\n",
    "            Nodoi(\n",
    "                Nodoi(Nodoe(),30,Nodoe()),\n",
    "                35,\n",
    "                Nodoe()\n",
    "            )\n",
    "        ),\n",
    "        42,\n",
    "        Nodoi(\n",
    "            Nodoi(\n",
    "                Nodoi(\n",
    "                    Nodoi(Nodoe(),65,Nodoe()),\n",
    "                    72,\n",
    "                    Nodoi(Nodoe(),81,Nodoe())\n",
    "                ),\n",
    "                90,\n",
    "                Nodoe()\n",
    "            ),\n",
    "            95,\n",
    "            Nodoe()\n",
    "        )\n",
    "       )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20((☐30☐)35☐))42((((☐65☐)72(☐81☐))90☐)95☐))\n"
     ]
    }
   ],
   "source": [
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20(☐35☐))42((((☐65☐)72(☐81☐))90☐)95☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(30)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20(☐35☐))42(((☐65☐)72(☐81☐))90☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(95)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20(☐35☐))65((☐72(☐81☐))90☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(42)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20(☐35☐))65((☐72(☐81☐))90☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(44) # 44 no está en el árbol\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)35☐)65((☐72(☐81☐))90☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(20)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación no recursiva de la eliminación\n",
    "\n",
    "Al programar la eliminación de esta manera, necesitamos modificar el nodo padre de $x$. Para simplificar, asegurando que todo nodo tenga un padre, incluso la raíz, durante el proceso de eliminación simularemos que la raíz es hija derecha de un nodo con llave \"$-\\infty$\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Nodoi:\n",
    "    def __init__(self, izq, info, der):\n",
    "        self.izq=izq\n",
    "        self.info=info\n",
    "        self.der=der\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \"(\"+self.izq.__str__()+str(self.info)+self.der.__str__()+\")\"\n",
    "\n",
    "class Nodoe:\n",
    "    def __init__(self):\n",
    "        pass\n",
    "    \n",
    "    def __str__(self):\n",
    "        return\"☐\"\n",
    "\n",
    "import math\n",
    "class Arbol:\n",
    "    def __init__(self,raiz=Nodoe()):\n",
    "        self.raiz=raiz     \n",
    "        \n",
    "    def delete(self,x):\n",
    "        cabecera=Nodoi(None,-math.inf,self.raiz)\n",
    "        p=cabecera # padre del candidato a ser eliminado\n",
    "        q=cabecera.der # el candidato\n",
    "        while not isinstance(q,Nodoe):\n",
    "            if x<q.info:\n",
    "                (p,q)=(q,q.izq)\n",
    "            elif x>q.info:\n",
    "                (p,q)=(q,q.der)\n",
    "            else: # encontramos x\n",
    "                if isinstance(q.izq,Nodoe): # no hay hijo izquierdo\n",
    "                    r=q.der\n",
    "                elif isinstance(q.der,Nodoe): # no hay hijo derecho\n",
    "                    r=q.izq\n",
    "                else: # hay 2 hijos, eliminamos el mínimo del árbol derecho y lo movemos a q\n",
    "                    s=q.der\n",
    "                    if isinstance(s.izq,Nodoe): # encontramos el mín de inmediato\n",
    "                        q.info=s.info\n",
    "                        q.der=s.der\n",
    "                    else: # el mín está más abajo\n",
    "                        t=s.izq # s es el padre del candidato a min, t es el candidato\n",
    "                        while not isinstance(t.izq,Nodoe): # mientras no encontremos el final de la rama izquierda\n",
    "                            (s,t)=(t,t.izq)\n",
    "                        q.info=t.info\n",
    "                        s.izq=t.der\n",
    "                    r=q\n",
    "                if x<p.info:\n",
    "                    p.izq=r\n",
    "                else:\n",
    "                    p.der=r\n",
    "                self.raiz=cabecera.der\n",
    "                return        \n",
    "        # si llegamos acá, x no estaba, no hacemos nada\n",
    "    \n",
    "    def __str__(self):        \n",
    "        return self.raiz.__str__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=Arbol(\n",
    "    Nodoi(\n",
    "        Nodoi(\n",
    "            Nodoi(Nodoe(),15,Nodoe()),\n",
    "            20,\n",
    "            Nodoi(\n",
    "                Nodoi(Nodoe(),30,Nodoe()),\n",
    "                35,\n",
    "                Nodoe()\n",
    "            )\n",
    "        ),\n",
    "        42,\n",
    "        Nodoi(\n",
    "            Nodoi(\n",
    "                Nodoi(\n",
    "                    Nodoi(Nodoe(),65,Nodoe()),\n",
    "                    72,\n",
    "                    Nodoi(Nodoe(),81,Nodoe())\n",
    "                ),\n",
    "                90,\n",
    "                Nodoe()\n",
    "            ),\n",
    "            95,\n",
    "            Nodoe()\n",
    "        )\n",
    "       )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20((☐30☐)35☐))42((((☐65☐)72(☐81☐))90☐)95☐))\n"
     ]
    }
   ],
   "source": [
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20(☐35☐))42((((☐65☐)72(☐81☐))90☐)95☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(30)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20(☐35☐))42(((☐65☐)72(☐81☐))90☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(95)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20(☐35☐))65((☐72(☐81☐))90☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(42)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)20(☐35☐))65((☐72(☐81☐))90☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(44) # 44 no está en el árbol\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((☐15☐)35☐)65((☐72(☐81☐))90☐))\n"
     ]
    }
   ],
   "source": [
    "a.delete(20)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rotaciones en un ABB\n",
    "\n",
    "Una operación que es la base de muchos algoritmos es la *rotación* (o rotación simple, para diferenciarla de la rotación doble, que veremos más adelante).\n",
    "\n",
    "Una rotación entre los nodos $b$ y $d$ es la siguiente transformación:\n",
    "\n",
    "![rotacion-simple](rotacion-simple.png)\n",
    "\n",
    "Como lo sugiere la figura, por simetría esta operación también se puede hacer en la dirección inversa.\n",
    "\n",
    "Esta operación tiene costo constante, porque solo requiere modificar tres punteros, y preserva el orden de izquierda a derecha que caracteriza a un ABB. Su efecto es que $A$ y $b$ suben un nivel, mientras que $d$ y $E$ bajan un nivel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aplicación: Inserción en la raíz\n",
    "\n",
    "El método estándar de inserción en un ABB es inserción en las hojas.\n",
    "Veremos a continuación que existe un método alternativo, que deja al nuevo elemento como raíz del árbol.\n",
    "\n",
    "El método consiste en insertar el nuevo elemento de la manera usual, y luego hacer una secuencia de rotaciones que vayan haciéndolo ascender, hasta que llegue a estar en la raíz."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Nodoi:\n",
    "    def __init__(self, izq, info, der):\n",
    "        self.izq=izq\n",
    "        self.info=info\n",
    "        self.der=der\n",
    "    def right_rotation(self):\n",
    "        return(Nodoi(self.izq.izq,\n",
    "                     self.izq.info,\n",
    "                     Nodoi(self.izq.der,self.info,self.der)))   \n",
    "    def left_rotation(self):\n",
    "        return(Nodoi(Nodoi(self.izq,self.info,self.der.izq),\n",
    "                     self.der.info,\n",
    "                     self.der.der))\n",
    "    def root_insert(self,x):\n",
    "        assert x!=self.info\n",
    "        if x<self.info:\n",
    "            self.izq=self.izq.root_insert(x) # x queda como raíz del hijo izquierdo\n",
    "            return self.right_rotation() # la rotación deja a x como raíz\n",
    "        else:\n",
    "            self.der=self.der.root_insert(x) # x queda como raíz del hijo derecho\n",
    "            return self.left_rotation() # la rotación deja a x como raíz\n",
    "        \n",
    "    def __str__(self):\n",
    "        return \"(\"+self.izq.__str__()+str(self.info)+self.der.__str__()+\")\"\n",
    "\n",
    "class Nodoe:\n",
    "    def __init__(self):\n",
    "        pass\n",
    "    \n",
    "    def root_insert(self,x):\n",
    "        return Nodoi(Nodoe(),x,Nodoe())\n",
    "    \n",
    "    def __str__(self):\n",
    "        return\"☐\"\n",
    "\n",
    "class Arbol:\n",
    "    def __init__(self,raiz=Nodoe()):\n",
    "        self.raiz=raiz     \n",
    "        \n",
    "    def root_insert(self,x):\n",
    "        self.raiz=self.raiz.root_insert(x)\n",
    "    \n",
    "    def __str__(self):        \n",
    "        return self.raiz.__str__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(☐10☐)\n",
      "((☐10☐)20☐)\n",
      "(((☐10☐)20☐)30☐)\n",
      "(((☐10☐)20☐)25(☐30☐))\n",
      "((☐10☐)15((☐20☐)25(☐30☐)))\n"
     ]
    }
   ],
   "source": [
    "a=Arbol()\n",
    "a.root_insert(10)\n",
    "print(a)\n",
    "a.root_insert(20)\n",
    "print(a)\n",
    "a.root_insert(30)\n",
    "print(a)\n",
    "a.root_insert(25)\n",
    "print(a)\n",
    "a.root_insert(15)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aplicación: Árboles cartesianos y \"Treaps\"\n",
    "\n",
    "Un *árbol cartesiano* es un árbol binario en que cada nodo interno contiene un par ordenado $(x,y)$, tal que:\n",
    "\n",
    "* Si se consideran las coordenadas $x$, el árbol es un ABB\n",
    "* Si se consideran las coordenadas $y$, el árbol es un árbol de prioridad\n",
    "\n",
    "La siguiente figura muestra a un árbol cartesiano en que la máxima prioridad corresponde al valor mínimo de $y$:\n",
    "\n",
    "![cartesian-tree](cartesian-tree.png)\n",
    "\n",
    "Intuitivamente, podemos imaginar que la prioridad $y$ corresponde a la hora en que la llave $x$ ingresó al árbol. Esto explica que la raíz tenga el valor mínimo de $y$, y que estos valores vayan creciendo a medida que descendemos en el árbol.\n",
    "\n",
    "Sin embargo, _no estamos obligados a insertar las llaves en orden cronológico_. En efecto, veremos que un nuevo par $(x,y)$ se puede insertar en cualquier momento, aunque su $y$ no sea mayor que los de los nodos que ya están en el árbol..\n",
    "\n",
    "Para insertar un nuevo par ordenado en un árbol cartesiano, primero efectuamos una inserción como si fuera un ABB, con lo cual el nuevo nodo cumple con las restricciones \"izquierda-derecha\" en su coordenada $x$, pero posiblemente no con las restricciones de prioridad \"arriba-abajo\" de la coordenada $y$. Para corregir esto último, a continuación, hacemos una serie de rotaciones hasta conseguir que el nuevo nodo cumpla con las restricciones de prioridad.\n",
    "\n",
    "También es posible eliminar un nodo dado de un árbol cartesiano. Como al eliminar un nodo sus dos árboles hijos quedan \"huérfanos\", es necesario fusionarlos en uno solo. Para esto, elegimos a la raíz de mejor prioridad para que quede como raíz del árbol resultante. De los tres subárboles restantes, uno va a un lado de la nueva raíz, y los otros dos deben fusionarse recursivamente.\n",
    "\n",
    "Una vez que tenemos una implementación de árboles cartesianos, podemos utilizarla para obtener un nuevo tipo de diccionario, llamado un *Treap* (mezcla de \"tree\" y de \"heap\"), que posee las mismas características de desempeño promedio que un ABB, pero que es inmune a que las llaves lleguen ordenadas, o a que un adversario le entregue la secuencia de inserciones en un orden malicioso. Para esto, dado una nueva llave $x$ para insertar, generamos una prioridad $y$ *al azar*, e insertamos el par $(x,y)$ resultante. El efecto neto es equivalente a si las llaves hubieran llegado en un orden aleatorio."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Árboles AVL\n",
    "\n",
    "Veremos a continuación que es posible implementar diccionarios en que los costos de búsqueda, inserción y eliminación son garantizadamente $O(\\log{n})$ *en el peor caso*.\n",
    "\n",
    "Hay muchas maneras de conseguir esto a través de modificaciones del algoritmo básico de los ABBs, y hablamos en general de *árboles balanceados* para referirnos a este tipo de diccionarios.\n",
    "\n",
    "Comenzaremos viendo el más antiguo de estos algoritmos, inventado por Adelson-Velskii y Landis y conocido por sus iniciales como *árboles AVL*.\n",
    "\n",
    "Si queremos garantizar un costo de búsqueda logarítmico, lo ideal sería poder construir árboles perfectamente balanceados, en que siempre los elementos se repartieran en partes iguales a ambos lados de la raíz, y en que por lo tanto las alturas a ambos lados también fueran idénticas.\n",
    "Pero eso no es posible por varias razones.\n",
    "Por una parte, porque el costo de insertar un nuevo elemento en ese tipo de árbol sería muy grande en el peor caso, pero también porque a medida que bajamos en en árbol, a menos que el número de llaves sea exactamente uno menos que una potencia de $2$, necesariamente terminaremos encontrando subárboles de tamaño $2$, en los cuales a un lado hay un árbol de altura $1$, y al otro lado un árbol de altura $0$.\n",
    "\n",
    "Por lo tanto, es necesario relajar un poco la exigencia, para acomodar a ese tipo de subárboles.\n",
    "\n",
    "Los árboles AVL se definen como ABBs en que todos sus nodos internos cumplen además una condición de *altura balanceada*, que consiste en que sus subárboles hijos pueden tener alturas diferentes, pero la diferencia de sus alturas no puede ser mayor que 1.\n",
    "\n",
    "![condicion-AVL](condicion-AVL.png)\n",
    "\n",
    "Más precisamente, si la función $h(T)$ es la altura del árbol $T$, para cada nodo interno sus subárboles hijos, digamos $A$ y $B$, deben cumplir que $|h(A)-h(B)|\\le 1$.\n",
    "\n",
    "El siguiente ejemplo muestra un árbol en que en cada nodo (interno o externo) se ha anotado la altura del subárbol que lo tiene como raíz.\n",
    "Este árbol cumple la condición AVL en todos sus nodos, excepto en el que aparece marcado con asterisco, cuyos hijos tienen diferencia de altura 2, y por lo tanto el árbol no es AVL.\n",
    "\n",
    "![ejemplo-no-AVL](ejemplo-no-AVL.png)\n",
    "\n",
    "En cambio, este otro árbol, muy similar, sí cumple la condición en todos sus nodos, y es por lo tanto un árbol AVL.\n",
    "\n",
    "![ejemplo-AVL](ejemplo-AVL.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chequeando si un árbol es AVL\n",
    "\n",
    "Para determinar si un árbol es AVL, debemos calcular la altura de cada subárbol y comparar las alturas de todos los subárboles \"hermanos\" para ver si su diferencia excede o no 1. La siguiente implementación lo hace, pero veremos que de una manera ineficiente:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Nodoi:\n",
    "    def __init__(self, izq, info, der):\n",
    "        self.izq=izq\n",
    "        self.info=info\n",
    "        self.der=der\n",
    "    \n",
    "    def altura(self):\n",
    "        return 1+max(self.izq.altura(),self.der.altura())\n",
    "    \n",
    "    def es_AVL(self):\n",
    "        return abs(self.izq.altura()-self.der.altura())<=1 \\\n",
    "                and self.izq.es_AVL() and self.der.es_AVL()\n",
    "        \n",
    "    def __str__(self):\n",
    "        return \"(\"+self.izq.__str__()+str(self.info)+self.der.__str__()+\")\"\n",
    "\n",
    "class Nodoe:\n",
    "    def __init__(self):\n",
    "        pass\n",
    "\n",
    "    def altura(self):\n",
    "        return 0\n",
    "    \n",
    "    def es_AVL(self):\n",
    "        return True\n",
    "    \n",
    "    def __str__(self):\n",
    "        return\"☐\"\n",
    "\n",
    "class Arbol:\n",
    "    def __init__(self,raiz=Nodoe()):\n",
    "        self.raiz=raiz     \n",
    "    \n",
    "    def es_AVL(self):\n",
    "        return self.raiz.es_AVL()\n",
    "    \n",
    "    def __str__(self):        \n",
    "        return self.raiz.__str__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((☐1☐)2(☐3(☐4☐)))\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "a1=Arbol(Nodoi(Nodoi(Nodoe(),1,Nodoe()),\n",
    "            2,\n",
    "            Nodoi(Nodoe(),3,Nodoi(Nodoe(),4,Nodoe()))))\n",
    "print(a1)\n",
    "print(a1.es_AVL())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((☐1☐)2(☐3(☐4(☐5☐))))\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "a2=Arbol(Nodoi(Nodoi(Nodoe(),1,Nodoe()),\n",
    "            2,\n",
    "            Nodoi(Nodoe(),3,Nodoi(Nodoe(),4,Nodoi(Nodoe(),5,Nodoe())))))\n",
    "print(a2)\n",
    "print(a2.es_AVL())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lo anterior funciona, pero puede ser ineficiente. Por ejemplo, si el árbol fuera perfectamente balanceado, tendríamos que el costo de calcular la altura de un árbol de tamaño $n$ sería\n",
    "\n",
    "$$\n",
    "h(n)=1+2h\\left(\\frac{n}{2}\\right)\n",
    "$$\n",
    "\n",
    "que tiene solución $h(n)=\\Theta(n)$, lo cual es razonable, porque para calcular la altura se requiere recorrer todo el árbol. Pero determinar si el árbol es AVL demora un tiempo $a(n)$, donde\n",
    "\n",
    "$$\n",
    "a(n)= 2a\\left(\\frac{n}{2}\\right) + 2h\\left(\\frac{n}{2}\\right)\n",
    "$$\n",
    "\n",
    "y esto tiene solución $a(n)=\\Theta(n\\log{n})$ por el Teorema Maestro.\n",
    "\n",
    "Veremos a continuación que esto se puede hacer más eficientemente, en tiempo lineal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 6.1 (Chequear si un árbol es AVL en tiempo lineal)\n",
    "\n",
    "En este ejercicio usted debe modificar la implementación anterior para asegurar que cada nodo del árbol se visite solo una vez, asegurando de esta manera que el costo de determinar si un árbol es AVL sea $\\Theta(n)$.\n",
    "\n",
    "Para esto, usted debe fusionar las funciones ``altura`` y ``es_AVL``en una sola función ``altura_AVL``, que retorne una tupla $(h,a)$, donde $h$ es la altura y $a$ es un booleano que dice si el árbol es AVL. De esta manera, al invocar la función se tiene de una sola vez toda la información necesaria."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Escriba aquí la nueva definición de nodos y árbol\n",
    "# Los nodos deben implementar la función altura_AVL\n",
    "# pero la clase Arbol debe seguir implemmentando una función es_AVL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A continuación, pruébela con los dos árboles utilizados anteriormente:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a1=Arbol(Nodoi(Nodoi(Nodoe(),1,Nodoe()),\n",
    "            2,\n",
    "            Nodoi(Nodoe(),3,Nodoi(Nodoe(),4,Nodoe()))))\n",
    "print(a1)\n",
    "print(a1.es_AVL())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a2=Arbol(Nodoi(Nodoi(Nodoe(),1,Nodoe()),\n",
    "            2,\n",
    "            Nodoi(Nodoe(),3,Nodoi(Nodoe(),4,Nodoi(Nodoe(),5,Nodoe())))))\n",
    "print(a2)\n",
    "print(a2.es_AVL())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Altura mínima y máxima de un árbol AVL\n",
    "\n",
    "Consideremos un árbol AVL con $n$ llaves y altura $h$.\n",
    "Sabemos que su número de hojas es $n+1$, y también sabemos que el número de hojas es menor o igual a $2^h$.\n",
    "Por lo tanto, $h \\ge \\lceil\\log_2{(n+1)}\\rceil$.\n",
    "\n",
    "Para encontrar una cota superior, consideremos la familia $A_h$ de los árboles AVL de altura $h$ con el mínimo número de hojas. Si $h=0$, el único árbol posible es el árbol vacío (solo una hoja) y es AVL.\n",
    "Si $h=1$, el único árbol posible es el que tiene un nodo interno y dos hojas como hijos, y también es AVL.\n",
    "\n",
    "Consideremos el caso $h\\ge 2$. El árbol $A_h$ debe tener una raíz y dos subárboles hijos. Si queremos economizar al máximo el número de hojas, uno de ellos debe tener altura $h-1$, para que la altura del árbol completo sea $h$, y el otro debe tener altura $h-2$, para que se cumpla la condición AVL, y ambos deben tener el mínimo posible de hojas, es decir, deben pertenecer a la misma familia.\n",
    "\n",
    "Por lo tanto, la familia $A_h$ se puede construir recursivamente de la siguiente manera:\n",
    "\n",
    "![arboles-fibonacci](arboles-fibonacci.png)\n",
    "\n",
    "Los árboles así construídos se llaman *árboles de Fibonacci*.\n",
    "\n",
    "Si llamamos $N_h$ al número de hojas del árbol $A_h$, tenemos que\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "N_0 &= 1\\\\\n",
    "N_1 &= 2\\\\\n",
    "N_h &= N_{h-1} + N_{h-2}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Esta es la misma ecuación de Fibonacci, comenzando dos pasos más adelante. Por lo tanto, si denotamos $f_n$ al $n$-ésimo número de Fibonacci, tenemos que $N_h=f_{h+2}=\\Theta(\\phi^h)$.\n",
    "\n",
    "Como los árboles de Fibonacci son los árboles AVL con el mínimo de hojas, cualquier otro árbol AVL tendrá más hojas que ellos, y por lo tanto, tomando logaritmos, la altura de todo árbol AVL será $O(\\log_{\\phi}{(n+1)})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Operaciones sobre un árbol AVL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Búsqueda\n",
    "\n",
    "Un árbol AVL es un ABB (con una condición adicional de balance), así que el algoritmo de búsqueda es el mismo.\n",
    "El que la altura de todo árbol AVL sea logarítmica garantiza que las operaciones de búsqueda tomarán tiempo logarítmico en el peor caso."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inserción\n",
    "\n",
    "Veremos a continuación que se puede insertar una nueva llave en un árbol AVL, preservando la condición AVL, en tiempo a lo más proporcional a la altura del árbol.\n",
    "\n",
    "Supongamos que se inserta una nueva llave $x$ en un árbol AVL como el que muestra la siguiente figura:\n",
    "\n",
    "![AVL1](AVL1.png)\n",
    "\n",
    "Supongamos que se inserta la llave $x$, siguiendo una trayectoria desde la raíz hasta la hoja respectiva, y que luego se retorna hacia arriba revisando en cada nodo de esa trayectoria si la condición AVL se sigue cumpliendo. Si en todos ellos la condición se cumple, no es necesario hacer nada más. Si no, supongamos qie el nodo marcado con asterisco ($d$) es el primero (de abajo hacia arriba) en donde la condición no se cumple.\n",
    "\n",
    "Consideremos primero el caso en que a partir de $d$, los dos pasos siguientes hacia abajo fueron en la misma dirección (ambos hacia la izquierda, en la figura). Esto se llama una *inserción exterior*, y los dos pasos son de tipo \"zig-zig\" (o \"zag-zag\", en el caso simétrico en que los dos pasos fueron hacia la derecha).\n",
    "\n",
    "Para que la condición AVL no se cumpla en $d$ y sí se cumpla en $b$, es necesario que los tres subárboles $A$, $C$ y $E$ sean todos de la misma altura, digamos $h$, y que la inserción de $x$ haga que la altura de $A$ crezca a $h+1$. Nótese que la altura del árbol, antes de la inserción, era $h+2$.\n",
    "\n",
    "En este caso hacemos una rotación (simple) entre los nodos $b$y $d$, con el resultado que se muestra a la derecha. En el árbol resultante, los nodos $b$ y $d$ ahora cumplen la condición AVL (con diferencia cero) y, más aún, después de esta rotación, el árbol resultante tiene altura $h+2$. Por lo tanto, el árbol completo no ha cambiado de altura, lo cual implica que ningún nodo más arriba puede estar desbalanceado.\n",
    "\n",
    "Por lo tanto, en el caso de una inserción exterior, basta con a lo más una rotación para restaurar la condición AVL en todo el árbol.\n",
    "\n",
    "Consideremos ahora el caso de una *inserción interior*, en que los dos primeros pasos fueron en direcciones opuestas (\"zig-zag\" o el simétrico \"zag-zig\"):\n",
    "\n",
    "![AVL2](AVL2.png)\n",
    "\n",
    "En este caso, es necesario entrar a examinar la estructura interna del subárbol $C$:\n",
    "\n",
    "![AVL3](AVL3.png)\n",
    "\n",
    "En este caso, $x$ puede ir al subárbol $F$ o al subárbol $G$ indistintamente (¡pero no a ambos!).\n",
    "Para restaurar la condición de balance AVL, necesitamos hacer _dos_ rotaciones: primero entre $c$ y $b$, y luego entre $c$ y $d$. El resultado neto es que el zig-zag $d-b-c$ se transforma en el subárbol perfectamente balanceado $b-c-d$.\n",
    "El efecto combinado de estas dos rotaciones se llama una _rotación doble_.\n",
    "\n",
    "Tal como ocurrió en el caso anterior, los tres nodos involucrados quedan cumpliendo la condición AVL, y el árbol resultante tiene altura $h+2$, la misma que tenía antes de la inserción. Por lo tanto, no puede haber nodos desbalanceados más arriba.\n",
    "\n",
    "Esto, sumado a lo que vimos antes, demuestra que **a lo más una rotación (simple o doble) basta para recuperar el balance AVL después de una inserción**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Nodoi:\n",
    "    def __init__(self, izq, info, der):\n",
    "        self.izq=izq\n",
    "        self.info=info\n",
    "        self.der=der\n",
    "        self.height=1+max(izq.height,der.height)\n",
    "\n",
    "    def right_rotation(self):\n",
    "        return(Nodoi(self.izq.izq,\n",
    "                     self.izq.info,\n",
    "                     Nodoi(self.izq.der,self.info,self.der)))\n",
    "    \n",
    "    def left_rotation(self):\n",
    "        return(Nodoi(Nodoi(self.izq,self.info,self.der.izq),\n",
    "                     self.der.info,\n",
    "                     self.der.der))\n",
    "        \n",
    "    def insert(self,x):\n",
    "        assert x!=self.info\n",
    "        if x<self.info:\n",
    "            p=Nodoi(self.izq.insert(x),self.info,self.der)\n",
    "            if p.izq.height>p.der.height+1:\n",
    "                if x<p.izq.info: # inserción exterior\n",
    "                    p=p.right_rotation()\n",
    "                else: # inserción interior\n",
    "                    p=Nodoi(p.izq.left_rotation(),p.info,p.der).right_rotation()           \n",
    "        else: # x>self.info, simétrico del anterior\n",
    "            p=Nodoi(self.izq,self.info,self.der.insert(x))\n",
    "            if p.der.height>p.izq.height+1:\n",
    "                if x>p.der.info: # inserción exterior\n",
    "                    p=p.left_rotation()\n",
    "                else: # inserción interior\n",
    "                    p=Nodoi(p.izq,p.info,p.der.right_rotation()).left_rotation()         \n",
    "        return p\n",
    "        \n",
    "    def __str__(self):\n",
    "        return \"(\"+self.izq.__str__()+str(self.info)+self.der.__str__()+\")\"\n",
    "\n",
    "class Nodoe:\n",
    "    def __init__(self):\n",
    "        self.height=0\n",
    "    \n",
    "    def insert(self,x):\n",
    "        return Nodoi(Nodoe(),x,Nodoe())\n",
    "    \n",
    "    def __str__(self):\n",
    "        return\"☐\"\n",
    "\n",
    "class ArbolAVL:\n",
    "    def __init__(self,raiz=Nodoe()):\n",
    "        self.raiz=raiz     \n",
    "        \n",
    "    def insert(self,x):\n",
    "        self.raiz=self.raiz.insert(x)\n",
    "    \n",
    "    def __str__(self):        \n",
    "        return self.raiz.__str__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(☐20☐)\n",
      "(☐20(☐40☐))\n",
      "((☐20☐)40(☐80☐))\n",
      "(((☐10☐)20☐)40(☐80☐))\n",
      "(((☐10☐)15(☐20☐))40(☐80☐))\n"
     ]
    }
   ],
   "source": [
    "a=ArbolAVL()\n",
    "a.insert(20)\n",
    "print(a)\n",
    "a.insert(40)\n",
    "print(a)\n",
    "a.insert(80)\n",
    "print(a)\n",
    "a.insert(10)\n",
    "print(a)\n",
    "a.insert(15)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Eliminación\n",
    "\n",
    "La eliminación en árbol AVL se realiza de manera análoga a un ABB, pero también es necesario verificar que la condición de balance se mantenga una vez eliminado el elemento. En caso que dicha condición se pierda, será necesario realizar una rotación simple o doble dependiendo del caso, pero es posible que se requiera más de una rotación para reestablecer el balance del árbol."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Árboles 2-3\n",
    "\n",
    "Los árboles 2-3 son árboles cuyos nodos internos pueden ser _binarios_ o _ternarios_. Los nodos binarios tienen una llave en su interior, y los nodos ternarios tienen dos llaves.\n",
    "\n",
    "Las llaves contenidas en los nodos del árbol cumplen la siguiente relación de orden de izquierda a derecha:\n",
    "\n",
    "![orden-2-3](orden-2-3.png)\n",
    "\n",
    "En un nodo binario, la llave $X$ actúa como separador entre las llaves del subárbol izquierdo y las del derecho.\n",
    "En un nodo ternario, la llave $X$ separa el subárbol izquierdo del subárbol del medio, y la llave $Y$ separa el subárbol del medio del subárbol derecho.\n",
    "\n",
    "Gracias a este orden, se puede realizar una búsqueda utilizando una generalización del algoritmo de búsqueda en un ABB.\n",
    "\n",
    "Además de lo anterior, un árbol 2-3 debe tener a todas sus hojas en el mismo nivel. El siguiente es un ejemplo de un árbol 2-3 que satisface ambas condiciones:\n",
    "\n",
    "![ejemplo-2-3](ejemplo-2-3.png)\n",
    "\n",
    "Nótese que si un árbol 2-3 tiene $n$ llaves, ya no necesariamente se cumple que el número de hojas (nodos externos) sea uno más que el número de nodos internos, pero sí se cumple que el número de hojas es igual a $n+1$.\n",
    "\n",
    "Dado que la altura de un árbol 2-3 es mínima si todos sus nodos son ternarios y es máxima si todos sus nodos son binarios, es fácil ver que\n",
    "\n",
    "$$\n",
    "\\log_3{(n+1)} \\le \\text{ altura } \\le \\log_2{(n+1)}\n",
    "$$\n",
    "\n",
    "y por lo tanto el costo de búsqueda es logarítmico en el peor caso."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inserción en un árbol 2-3\n",
    "\n",
    "Para insertar una nueva llave $X$ en un árbol 2-3, se realiza una búsqueda infructuosa y se inserta dicha llave en el último nodo interno visitado durante la búsqueda. Esto puede conducir a dos casos distintos:\n",
    "\n",
    "* Si el nodo tenía solo una llave (era binario), ahora queda con dos llaves y pasa a ser ternario:\n",
    "\n",
    "![insercion-2-3-binario](insercion-2-3-binario.png)\n",
    "\n",
    "* Si el nodo tenía 2 llaves (era ternario), queda transitoriamente con 3 llaves y 4 hijos. Se dice que ese nodo está saturado, o que tiene *overflow*, y esto se corrige dividiendo el nodo en dos nodos binarios (*split*). Los 4 hijos se reparten entre esos dos nodos. Respecto a las llaves, la menor queda en el nodo izquierdo, la mayor en el nodo derecho, y la mediana sube y se inserta en el padre, para actuar como separador entre los dos subárboles resultantes del *split*.\n",
    "\n",
    "![insercion-2-3-ternario](insercion-2-3-ternario.png)\n",
    "\n",
    "Si el padre era binario, la llegada de una nueva llave lo transforma en ternario y el proceso concluye ahí. Pero si ya era ternario, el padre ahora está saturado y el proceso se repite.\n",
    "\n",
    "En el peor caso, es posible que la raíz llegue a dividirse. En ese caso, se crea una nueva raíz un nivel más arriba la altura del árbol crece en 1.\n",
    "\n",
    "#### Ejemplo de inserciones en un árbol 2-3\n",
    "\n",
    "![inserciones-2-3](inserciones-2-3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 6.2 (Número de operaciones *split*)\n",
    "\n",
    "Supongamos que comenzamos con un árbol 2-3 vacío y a continuación insertamos $n$ llaves. El objetivo de este ejercicio es calcular cuántas operaciones *split* se pueden llegar a ejecutar a lo largo de este proceso, en el peor caso.\n",
    "\n",
    "Una manera de acotar este número de operaciones es ver que una inserción puede gatillar la ejecución de $O(\\log{n})$ operaciones *split*, y como son $n$ inserciones, el número total de operaciones *split* es $O(n\\log{n})$.\n",
    "\n",
    "Lo anterior es una cota superior, pero en realidad está muy sobredimensionada.\n",
    "\n",
    "Demuestre que el número total de operaciones *split* ejecutadas al insertar $n$ llaves comenzando con un árbol 2-3 vacío es $O(n)$ en el peor caso. Escriba su demostración en el siguiente recuadro.\n",
    "\n",
    "*Indicación*: Considere el impacto de un *split* sobre el número de nodos del árbol."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Demostración:\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Eliminación en un árbol 2-3\n",
    "\n",
    "Supongamos que queremos eliminar una llave $Z$. Sin perder generalidad, podemos suponer que $Z$ está en el nivel más bajo de árbol. Si esto no es así, entonces el sucesor y el predecesor de $Z$ se encuentran necesariamente en el nivel inferior, en cuyo caso basta con eliminar uno de ellos, y luego sobreescribir esa llave en el lugar de $Z$.\n",
    "\n",
    "La eliminación presenta dos posibles casos:\n",
    "\n",
    "* El nodo en donde se encuentra $Z$ es ternario. En este caso, se elimina $Z$ junto con una hoja y el nodo queda como binario.\n",
    "![eliminacion2-3a](eliminacion2-3a.gif)\n",
    "\n",
    "* El nodo en donde se encuentra $Z$ es binario. En ese caso, al eliminar $Z$ y una hoja, el nodo queda como \"unario\" y sin llaves (*underflow*). Cuando esto sucede, tenemos dos casos:\n",
    "\n",
    "    * Si el nodo hermano es ternario, le quitamos una llave y una hoja y ambos quedan como binarios. Nótese que, para preservar el orden, se debe realizar un traspaso con la llave en el padre que separa a ambos nodos:\n",
    "    ![eliminacion2-3b](eliminacion2-3b.gif)\n",
    "    \n",
    "    * Si el nodo hermano es binario, no le podemos quitar nada. En ese caso, fusionamos a ambos hermanos, resultando un nodo ternario, y la llave del padre que actuaba como separador baja a este nuevo nodo:\n",
    "    ![eliminacion2-3c](eliminacion2-3c.gif)\n",
    "    \n",
    "    Cuando ocurre esto último, el padre pierde un hijo y una llave, lo cual podría dejarlo transformado en unario. En ese caso, se repite el procedimiento anterior, un nivel más arriba.\n",
    "    \n",
    "El peor caso es que finalmente la raíz quede como un nodo vacío unario. En ese caso, se elimina esa raíz y su hijo queda como raíz."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Costo de las operaciones\n",
    "\n",
    "Dado que el árbol 2-3 tiene altura logarítmica, y que las operaciones de inserción, eliminación y búsqueda hacen una cantidad de trabajo constante en cada nivel, el costo de dichas operaciones en el peor caso es $\\Theta(\\log{n})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Árboles B (*B-trees*)\n",
    "\n",
    "Los árboles 2-3 se pueden generalizar a árboles con un mayor número de hijos.\n",
    "La idea es que cuando un nodo excede el número máximo de hijos (y de llaves) permitidos, se divide en dos (*split*), con la mitad de los hijos cada uno.\n",
    "\n",
    "Más precisamente, supongamos que $t\\ge 2$ es un parámetro fijo, y permitimos que todo nodo tenga un mínimo de $t$ y un máximo de $2t-1$ hijos. Un nodo con $k$ hijos tiene $k-1$ llaves, que actúan como separadoras entre sus hijos.\n",
    "\n",
    "Los árboles 2-3 son árboles B con $t=2$. En la práctica, los árboles $B$ se implementan con valores mucho más grandes de $t$, por ejemplo $t=100$.\n",
    "\n",
    "La motivación para utilizar valores altos de $t$ es hacer coincidir el tamaño del nodo con la capacidad de un bloque de disco (memoria secundaria). Ésta es memoria masiva de acceso más lento que la memoria cental del computador (memoria RAM), y al tener un grado alto de ramificación, el árbol tiene muy pocos niveles. Gracias a esto, el número de accesos a disco para implementar las operaciones es también muy pequeño."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inserción en un árbol B\n",
    "\n",
    "* La nueva llave, junto con una nueva hoja, se agregan en el nodo correspondiente en el nivel inferior del árbol.\n",
    "\n",
    "* Si ese nodo queda saturado (*overflow*), es decir, si queda con $2t$ hijos y $2t-1$ llaves, se divide en dos nodos con $t$ hijos y $t-1$ llaves cada uno. La llave sobrante, que debe ser la mediana del conjunto de llaves, sube al padre como separador de estos dos nuevos nodos.\n",
    "\n",
    "* Si a causa de esto el padre queda saturado, se repite el procedimiento un nivel más arriba.\n",
    "\n",
    "* El peor caso es que la raíz llegue a estar saturada. En ese caso, la raíz se divide en dos nodos y se crea un nuevo nodo binario como padre de ellos. Este nodo es la nueva raíz.\n",
    "\n",
    "Nótese que, debido a lo anterior, la raíz es el único nodo que está exento de la obligación de tener al menos $t$ hijos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Eliminación en un árbol B\n",
    "\n",
    "* Tal como hicimos en el caso de los árboles 2-3, sin perder generalidad, suponemos que la llave a eliminar está en el nivel inferior. Se elimina la llave y una hoja.\n",
    "\n",
    "* Si a causa de esto el nodo queda con menos de $t$ hijos, tenemos dos casos:\n",
    "    * Si el hermano tiene más de $t$ hijos, redistribuimos los hijos y las llaves entre ambos hermanos, mitad y mitad.\n",
    "    * Si el hermano tiene solo $t$ hijos, no le podemos quitar nada. En ese caso, fusionamos ambos nodos, y la llave del padre que los separaba baja al nuevo nodo. Si a causa de eso el padre queda con menos del mínimo de hijos, se repite este procedimiento un nivel más arriba.\n",
    "    * Excepcionalmente, a la raíz se le permite que tenga menos de $t$ hijos, pero si llega a quedar como un nodo unario (sin llaves), se elimina y su hijo queda como nueva raíz.\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Costo de las operaciones en un árbol B\n",
    "\n",
    "En las estructuras de datos implementadas en memoria secundacia, el costo de las operaciones se aproxima por el número de bloques leídos o escritos, y se ignora el costo del procesamiento en memoria RAM. Esta aproximación se justifica porque el acceso a memoria secundaria es mucho más lento que a memoria RAM.\n",
    "\n",
    "En un árbol B, el número de accesos a bloques corresponde al número de niveles del árbol, el cual es logarítmico, pero ese logaritmo es en una base muy grande (entre $t$ y $2t-1$), de modo que en la práctica podemos decir que el costo es \"casi constante\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Variantes de los árboles B\n",
    "\n",
    "Veremos dos variantes de la definición anterior, que son importantes en la práctica.\n",
    "\n",
    "#### Árboles B*\n",
    "\n",
    "La idea es no hacer un _split_ apenas un nodo se satura, sino ver si el hermano tiene capacidad como para recibir que le enviemos llaves e hijos. El _split_ solo se hace cuando _ambos_ nodos están saturados, y en ese caso se crea un tercer nodo para distribuir entre los tres equitativamente el contenido.\n",
    "\n",
    "En los árboles B, la utilización del espacio (fracción ocupada de un nodo) varía entre 50% y 100%. En un árbol B* la utilización varía entre 66,6% y 100%. Al haber una mayor utilización, el grado de ramificación de los nodos es mayor, y por la altura del árbol es menor.\n",
    "\n",
    "#### Árboles B+\n",
    "\n",
    "En los árboles B+, los datos del conjunto se almacenan en orden ascendente de llave en las hojas. Cada hoja tiene una cierta capacidad máxima (correspondiente a la capacidad del bloque de disco en donde se almacena), y cuando se excede, la hoja se divide en dos, cada una 50% llena. Adicionalmente, las hojas se enlazan en una lista de doble enlace, que permite un recorrido secuencial de los datos en orden ascendente o descendente de llave.\n",
    "\n",
    "La máxima llave de cada hoja (excepto la de la hoja de más a la derecha) se toma como separador y se almacena dentro de los nodos internos del árbol. Nótese que en los nodos internos solo están las llaves y no toda la información que puede acompañarlas, en cambio en las hojas está la información completa.\n",
    "\n",
    "Debido a esto, al hacer una búsqueda, las preguntas se hacen con $\\le/>$ y se debe llegar siempre hasta el nivel de las hojas.\n",
    "\n",
    "El nivel de las hojas se llama en \"*B-file*\", y el conjunto de los nodos internos del árbol se llama el \"*B-index*\".\n",
    "\n",
    "Los árboles B+ son la versión más utilizada, porque permiten hacer tanto recorridos secuenciales como búsqueda eficientes en memoria secundaria."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Árboles Digitales\n",
    "\n",
    "En esta sección exploramos una manera distinta de almacenar un diccionario usando árboles.\n",
    "Hasta ahora hemos supuesto que las llaves pertenecen a algún conjunto ordenado, pero no hemos hecho ninguna suposición respecto de la estructura interna de las llaves. Ahora vamos a suponer que toda llave $X$ se representa como una secuencias de bits:\n",
    "\n",
    "$$\n",
    "X = b_0 b_1 \\ldots b_k\n",
    "$$\n",
    "\n",
    "Vamos a suponer también que ninguna secuencia de bits asociada a una llave es prefijo de la secuencia de bits de otra llave. Esto se cumple trivialmente si todas las llaves son del mismo largo.\n",
    "\n",
    "En los ejemplos vamos a considerar el siguiente conjunto de llaves:\n",
    "\n",
    "```\n",
    "A = 00100\n",
    "B = 01000\n",
    "C = 01111\n",
    "D = 11000\n",
    "E = 11101\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Árboles digitales o \"*tries*\"\n",
    "\n",
    "Un _trie_ es un árbol binario cuyos nodos internos solo se utilizan como puntos de ramificación, para separar las llaves según los bits que la componen.\n",
    "Por convención, supondremos que las llaves que tienen un bit $0$ en una posición dada se van hacia la izquierda, y las que tienen un $1$ se van hacia la derecha. Cuando se llega a que la secuencia de bits identifica a solo una posible llave, se coloca una hoja que contiene a dicha llave en su interior. Por ejemplo:\n",
    "\n",
    "![trie](trie.png)\n",
    "\n",
    "Nótese que una hoja puede ser vacía. Esto ocurre si no hay ninguna llave que comience con ese prefijo, pero en la rama opuesta hay más de una llave."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Búsqueda en un _trie_\n",
    "\n",
    "Para buscar una llave $X$ en un _trie_ se procede de la siguiente manera:\n",
    "\n",
    "* Se examinan los bits comenzando desde el bit $b_0$ en adelante.\n",
    "* Si $b_i=0$, se avanza por la rama izquierda y se pasa a examinar el siguiente bit, $b_{i+1}$.\n",
    "* Si $b_i=1$, se avanza por la rama derecha y se pasa a examinar el siguiente bit.\n",
    "* El proceso termina cuando se llega a una hoja, único lugar posible en donde puede estar $X$. Si la llave almacenada en esa hoja es igual a $X$, se encontró. Si la hoja está vacía, o contiene una llave distinta de $X$, no está."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inserción en un *trie*\n",
    "\n",
    "Para insertar una llave $X$ en un *trie*, se realiza una búsqueda infructuosa, y se almacena transitoriamente la llave $X$ en esa hoja.\n",
    "\n",
    "Si la hoja estaba vacía, la llave $X$ queda en ese lugar de manera definitiva.\n",
    "\n",
    "Si la hoja contenía otra llave $Y$, se divide la hoja en dos, colgando desde un nuevo nodo interno, y las llaves se trasladan hacia la hoja que corresponda, según si su siguiente bit es $0$ o $1$. Se repite este proceso en caso de ser necesario, hasta que en ninguna hoja quede más de una llave.\n",
    "\n",
    "Es importante notar que, para un conjunto dado de llaves, el _trie_ resultante es único, de modo que el orden de llegada de las llaves no cambia el resultado final. Uno podría suponer que al principio **todas** las llaves estaban en un única hoja, la cual se fue subdividiendo y subdividiendo hasta que en cada hoja quedó a lo más una llave."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Eliminación en un _trie_\n",
    "\n",
    "Para eliminar una llave $X$ primero se ubica la hoja que la contiene, y se borra la llave, con lo cual la hoja queda vacía. Luego se mira si esta hoja vacía es hermana de otra hoja (la necesariamente sería no vacía) y ambas se fusionan, quedando un nivel más arriba. Se repite este procedimiento hasta que ninguna hoja con una llave quede como hermana de una hoja vacía."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Costo esperado de búsqueda exitosa en un _trie_\n",
    "\n",
    "Los _tries_ tienden a ser mejor balanciados que los ABBs, porque si los bits son uniformemente distribuídos, la probabilidad de que una nueva llave vaya a la izquierda o a la derecha es $1/2$. En un ABB, en cambio, esa probabilidad es proporcional al tamaño del subárbol respectivo, de modo que si un árbol está desbalanceado, tiene una tendencia a desbalancearse más.\n",
    "\n",
    "El análisis matemático del costo esperado de búsqueda es muy complicado, por lo cual solo daremos el resultado sin demostrarlo:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C_n &= \\frac{H_n}{\\ln{2}}+\\frac{1}{2}+P(\\log_2{n})\\\\\n",
    "    & \\approx \\log_2{n}+1.3327\\ldots\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "donde $P()$ es una función periódica de muy pequeña amplitud (del orden de $10^{-6}$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Árboles de Búsqueda Digital\n",
    "\n",
    "Los árboles de búsqueda digital (ABD) son un híbrido entre los ABBs y los _tries_.\n",
    "\n",
    "Las llaves se almacenan en los nodos internos, al igual que en un ABB, pero la ramificación izquierda-derecha se hace según si el siguiente bit es $0$ o $1$.\n",
    "\n",
    "Como los elementos se van insertando en orden de llegada, este orden sí impacta en el resultado final.\n",
    "Por ejemplo, si el orden de llegada de las llaves fuera $B, A, C, D, E$, el resultado sería:\n",
    "\n",
    "![abd](abd.png)\n",
    "\n",
    "El costo esperado de búsqueda en un ABD es levemente menor al de un *trie*, y se puede demostrar que\n",
    "\n",
    "$$\n",
    "C_n \\approx \\log_2{n}-0.7166\\ldots\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Listas Saltadas (*Skip Lists*)\n",
    "\n",
    "Las listas saltadas son una estructura aleatorizada basada en listas enlazadas.\n",
    "\n",
    "Para motivar la idea, comencemos con una sencilla lista enlazada de menor a mayor, con una cabecera (que imaginamos que tiene una llave $-\\infty$) y un fin de lista (que imaginamos que tiene una llave $+\\infty$):\n",
    "\n",
    "![skip-list1](skip-list1.png)\n",
    "\n",
    "Una lista como ésta no es muy eficiente, dado que sabemos que una búsqueda en ella demora tiempo $\\Theta(n)$ tanto en promedio como en el peor caso.\n",
    "\n",
    "Para aumentar la eficiencia de la búsqueda, supongamos que enlazamos los elementos uno por medio en una segunda lista:\n",
    "\n",
    "![skip-list2](skip-list2.png)\n",
    "\n",
    "De esta manera, podemos buscar primero en la lista de más arriba para acotar en intervalo en que está la llave buscada, y luego usar la lista inferior para buscar en dicho intervalo. Con eso, el tiempo de búsqueda se reduce aproximadamente a la mitad.\n",
    "\n",
    "Dado que esto fue una buena idea, la podemos aplicar de nuevo, las veces que sea necesaria:\n",
    "\n",
    "![skip-list3](skip-list3.png)\n",
    "\n",
    "La estructura resultante permite hacer búsquedas tan eficientes como la búsqueda binaria, pero sirve solo como motivación para el diseño de un estructura verdaderamente eficiente, porque como está no admite inserciones ni eliminaciones de costo logarítmico.\n",
    "\n",
    "La clave para obtener una estructura flexible es abandonar la idea de que la altura de cada \"torre\" de punteros vaya variando regularmente, y concentrarse en que esas alturas solo sigan la misma distribución. Para eso, introduciremos aleatoriedad: para determinar cuántos punteros tendrá un elemento dado, lanzaremos una moneda repetidamente hasta obtener \"cara\", y el número de veces que fue necesario lanzar será el número de punteros para ese elemento.\n",
    "\n",
    "Así, todos los elementos tienen al menos un puntero, en promedio la mitad tiene al menos 2, la cuarta parte al menos 3, etc.\n",
    "\n",
    "El resultado podría ser, por ejemplo:\n",
    "\n",
    "![skip-list4](skip-list4.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Búsqueda en una lista saltada\n",
    "\n",
    "Supongamos que queremos buscar la llave $x$.\n",
    "Para esto, vamos a colocar una ficha inicialmente en el casillero correspondiente al tope de la torre de punteros de la cabecera (\"$-\\infty$\"), y la vamos a ir moviendo de acuerdo a las siguientes reglas.\n",
    "\n",
    "En cada paso, llamemos $y$ a la llave a la cual apunta el puntero donde está la ficha.\n",
    "\n",
    "* Si $x>y$, movemos la ficha horizontalmente hacia la derecha.\n",
    "* Si $x\\le y$, movemos la ficha verticalmente hacia abajo.\n",
    "\n",
    "Lo anterior continúa hasta que al tratar de ejecutar el paso 2, no se puede porque la ficha ya está en el nivel inferior. En ese caso, hacemos una comparación de igualdad entre $x$ e $y$. Si $x=y$, lo hemos encontrado, y si no, no está.\n",
    "\n",
    "La siguiente animación ilustra este proceso:\n",
    "\n",
    "![skip-search](skip-search.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inserción en una lista saltada\n",
    "\n",
    "Para insertar una nueva llave, se realiza primero una búsqueda infructuosa, y se conserva en una pila la lista de todos los punteros en donde se dio un paso vertical.\n",
    "Luego de determinar aleatoriamente cuántos punteros debe tener el nuevo elemento, éste se inserta en el lugar correspondiente y se recorre la pila, haciendo que todos esos puneros ahora apunten al nuevo elemento, y que éste apunte hacia adonde apuntaban ellos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Eliminación en una lista saltada\n",
    "\n",
    "Para eliminar una llave, se realiza una búsqueda y se conserva en una pila la lista de todos los punteros en donde se dio un paso vertical.\n",
    "Luego se recorre la pila, haciendo que todos esos punteros apunten hacia adonde apuntaba el elemento que se está eliminando."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Análisis de las listas saltadas\n",
    "\n",
    "El análisis matemático de las listas saltadas es muy complejo, por lo que solo daremos aquí los resultados.\n",
    "\n",
    "Para generalizar, vamos a suponer que la moneda no es necesariamente insesgada.\n",
    "Suponiendo que la probabilidad de que salga \"cara\" es $p$, un primer resultado interesante es la _altura_ de la lista saltada, esto es, el número de punteros que tiene la \"torre\" más alta, lo cual corresponde también al número de punteros que debe tener el elemento \"cabecera\" de las listas.\n",
    "\n",
    "Se puede demostrar que la altura espera de una lista saltada con $n$ llaves es\n",
    "\n",
    "$$\n",
    "\\log_{1/p}{n}+\\Theta(1)\n",
    "$$\n",
    "\n",
    "Más aún, su varianza es constante, y aproximadamente igual a\n",
    "\n",
    "$$\n",
    "\\frac{\\pi^2}{6\\ln^2{p}}+\\frac{1}{12}\n",
    "$$\n",
    "\n",
    "con lo cual resulta muy improbable que la altura pueda exceder por mucho a su valor esperado.\n",
    "\n",
    "Respecto al costo esperado de búsqueda, se puede demostrar que\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C_n &= \\frac{1}{p}\\log_{1/p}{n}+\\Theta(1)\\\\\n",
    "    &= \\frac{1}{p\\log_{2}{(1/p)}}\\log_{2}{n}+\\Theta(1)\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Si la moneda es insesgada ($p=1/2$), tenemos que la altura esperada es $\\log_{2}{n}+\\Theta(1)$ y que el costo esperado de búsqueda es $2\\log_{2}{n}+\\Theta(1)$.\n",
    "\n",
    "Pero el valor que minimiza la constante que multiplica al $\\log_{2}{n}$ no es $p=1/2$, sino que es $p=1/e=0.3678794412\\ldots$, y para este valor de $p$ se tiene que el costo esperado de búsqueda es\n",
    "\n",
    "$$\n",
    "C_n = (e\\ln{2})\\log_{2}{n}+\\Theta(1) \\approx 1.884 \\log_{2}{n}+\\Theta(1)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Árboles de búsqueda binaria óptimos\n",
    "\n",
    "Si todas las llaves de un ABB son igualmente probables de ser buscadas, el ábol que minimiza el costo esperado de búsqueda es el árbol perfectamente balanceado.\n",
    "\n",
    "Pero si las llaves tienen probabilidades no uniformes, o si las búsquedas infructuosas pueden caer en hojas con distinta probabilidad, el árbol que minimiza el costo esperado de búsqueda puede ser muy diferente.\n",
    "\n",
    "Supongamos que tenemos $n$ llaves $X_1 < X_2, \\ldots < X_n$ con probabilidades de acceso conocidas $p_1, p_2, \\ldots, p_n$ respectivamente, y supongamos que las hojas, numeradas de $0$ a $n$ de izquierda a derecha, tienen probabilidades de búsqueda infructuosa $q_0, q_1, \\ldots, q_n$ respectivamente.\n",
    "\n",
    "El problema es encontrar el árbol de búsqueda binaria que minimiza el costo esperado de búsqueda\n",
    "\n",
    "$$\n",
    "C(0,n) = \\sum_{1\\le i \\le n} (1+\\text{nivel}(\\text{llave }i))p_i +\n",
    "         \\sum_{0\\le i \\le n} \\text{nivel}(\\text{hoja }i)q_i\n",
    "$$\n",
    "\n",
    "donde los niveles del árbol se numeran de $0$ en adelante a partir de la raíz.\n",
    "\n",
    "Por ejemplo, consideremos en siguiente ABB con $6$ llaves, en donde en cada nodo (interno o externo) se ha anotado la probabilidad de que la búsqueda termine en él:\n",
    "\n",
    "![abbopt1](abbopt1.png)\n",
    "\n",
    "El costo esperado de búsqueda es\n",
    "\n",
    "$$\n",
    "C(0,6) = (2q_0+2p_1+4q_1+4p_2+4q_2+3p_3+4q_3+4p_4+4q_4)+p_5+(2q_5+2p_6+2q_6)\n",
    "$$\n",
    "\n",
    "donde hemos parentizado la parte que corresponde al subárbol izquierdo y derecho, respectivamente.\n",
    "\n",
    "Escribamos ahora las fórmulas análogos para los subáboles, suponiendo que ellos fueran árboles independientes:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C(0,4) & = q_0+p_1+3q_1+3p_2+3q_2+2p_3+3q_3+3p_4+3q_4\\\\\n",
    "C(5,6) & = q_5+p_6+q_6\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Si restamos esto a la fórmula para $C(0,6)$, la diferencia es la suma de todas las probabilidades, llamémosla $W(0,6)$ ($W$ por \"weight\", o peso).\n",
    "Por cierto, en el caso del árbol completo esta suma es igual a $1$, pero no así en los subárboles.\n",
    "\n",
    "Utilizando esta notación, tenemos que\n",
    "\n",
    "$$\n",
    "C(0,6) = W(0,6)+C(0,4)+C(5,6)\n",
    "$$\n",
    "\n",
    "Lo anterior es para un árbol con hojas numeradas de $0$ a $6$ y con la raíz ocupada por $X_5$.\n",
    "\n",
    "Más en general, si tenemos un árbol con hojas numeradas desde $i$ a $j$ y con $X_k$ en la raíz, se cumple que\n",
    "\n",
    "$$\n",
    "C(i,j) = W(i,j)+C(i,k-1)+C(k,j)\n",
    "$$\n",
    "\n",
    "Nótese que si éste fuera el árbol óptimo, los subárboles también deberían ser óptimos, porque de lo contrario podríamos reemplazar ese subárbol por uno de costo menor, y el costo total disminuiría estrictamente, contradicción con la hipótesis de que el árbol era óptimo.\n",
    "\n",
    "Pero al revés no necesariamente es cierto: los subárboles pueden ser óptimos, pero el árbol completo no, si es que hemos elegido mal la raíz.\n",
    "Para asegurarnos de que el árbol completo sea óptimo, debemos minimizar sobre todas las raíces posibles:\n",
    "\n",
    "$$\n",
    "\\hat{C}(i,j) = W(i,j)+\\min_{i+1\\le k \\le j}(\\hat{C}(i,k-1)+\\hat{C}(k,j))\n",
    "$$\n",
    "\n",
    "y el costo de buscar en un árbol vacío es $0$:\n",
    "\n",
    "$$\n",
    "\\hat{C}(i,i)=0 \\text{ para }0 \\le i \\le n\n",
    "$$\n",
    "\n",
    "Finalmente, el costo del árbol óptimo para el conjunto completo de llaves es $\\hat{C}(0,n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Un algoritmo de Programación Dinámica para encontrar un ABB óptimo\n",
    "\n",
    "A partir de la recurrencia anterior se puede formular fácilmente un algoritmo recursivo para el árbol óptimo y su costo, pero eso sería equivalente a un algoritmo de fuerza bruta que examina todos los árboles posibles.\n",
    "Como el número de árboles es el número de Catalan, que crece exponencialmente con $n$, es sería un algoritmo muy ineficiente.\n",
    "\n",
    "En cambio, si utilizamos *tabulación*, podemos resolver el problema de manera mucho más rápida.\n",
    "La tabulación es posible porque hay solo $\\Theta(n^2)$ valores $\\hat{C}(i,j)$ distintos por calcular, los cuales podemos almacenar en una matriz, y la podemos ir llenando de manera que todos los casilleros necesarios para calcular el casillero $(i,j)$ ya hayan sido llenados previamente.\n",
    "\n",
    "Para implementar el algoritmo, definamos una nueva variable $d=j-i$ que calcula el número de llaves del subárbol $(i,j)$, y vamos a ir llenando una matriz ``C`` en orden creciente de $d$.\n",
    "\n",
    "Al mismo tiempo que vamos llenando esa matriz, vamos a ir llenando una matriz paralela ``R`` que almacenará el valor del $k$ para el cual se alcanza el óptimo en el subárbol $(i,j)$.\n",
    "Éste será el subíndice de la raíz óptima para dicho subárbol, lo cual nos permitirá construir el árbol óptimo y también, como veremos pronto, acelerar significativamente el algoritmo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import numpy as np\n",
    "\n",
    "def calculaABBoptimo(p,q):\n",
    "    n=len(q)-1\n",
    "    C=np.zeros((n+1,n+1)) # Esto ya deja la diagonal en cero\n",
    "    W=np.zeros((n+1,n+1))\n",
    "    R=np.zeros((n+1,n+1),dtype=int)\n",
    "    for i in range(0,n+1):\n",
    "        W[i,i]=q[i]\n",
    "    for d in range(1,n+1):\n",
    "        for i in range(0,n-d+1):\n",
    "            j=i+d\n",
    "            W[i,j]=W[i,j-1]+p[j]+q[j]\n",
    "            C[i,j]=math.inf # +infinito\n",
    "            for k in range(i+1,j+1):\n",
    "                m=W[i,j]+C[i,k-1]+C[k,j]\n",
    "                if m<C[i,j]:\n",
    "                    C[i,j]=m\n",
    "                    R[i,j]=k # anotamos dónde se alcanza el min\n",
    "    return (C[0,n],R)\n",
    "\n",
    "def ABBoptimo(R,i,j):\n",
    "    return \"☐\" if i==j else \"(\"+ABBoptimo(R,i,R[i,j]-1)+\"X\"+str(R[i,j])+ABBoptimo(R,R[i,j],j)+\")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Costo óptimo= 2.35\n",
      "Arbol óptimo= (((☐X1☐)X2(☐X3☐))X4(☐X5☐))\n"
     ]
    }
   ],
   "source": [
    "p=[0,0.15,0.10,0.05,0.10,0.20]\n",
    "q=[0.05,0.10,0.05,0.05,0.05,0.10]\n",
    "(Copt,R)=calculaABBoptimo(p,q)\n",
    "print(\"Costo óptimo=\", Copt)\n",
    "print(\"Arbol óptimo=\", ABBoptimo(R,0,5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Análisis del algoritmo\n",
    "\n",
    "El algoritmo rellena todos los casilleros $(i,j)$ de la matriz, con $0\\le i \\le j \\le n$, y para cada casillero recorre el rango $(i+1)..j$.\n",
    "\n",
    "Dado que hay aproximadamente $n^2/2$ casileros que se deben llenar, y que para cada uno de ellos el rango es de tamaño a lo más $n$, es evidente que el tiempo de ejecución del algoritmo es $O(n^3)$.\n",
    "\n",
    "Sin embargo, esta cota podría ser exagerada, porque el tamaño de muchos rangos es mucho menor que $n$.\n",
    "Como el tamaño del rango que va desde $i+1$ hasta $j$ es $j-i$, una contabilidad más precisa sería decir que el tiempo del algoritmo es\n",
    "\n",
    "$$\n",
    "\\sum_{0\\le i \\le j \\le n}{(j-i)} = \\frac{n(n+1)(n+2)}{6} = \\Theta(n^3)\n",
    "$$\n",
    "\n",
    "de modo que el tiempo que demora el algoritmo en realidad es cúbico."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Un algoritmo más eficiente\n",
    "\n",
    "Supongamos que hemos calculado que la raíz óptima para un subárbol $(i,j)$ es $k=R[i,j]$.\n",
    "\n",
    "Imaginemos ahora que quitamos la llave de más a la derecha y obtenemos la nueva raíz óptima $R[i,j-1]$. Se puede demostrar que, al ser el subárbol de la derecha más \"liviano\", la nueva raíz no puede estar a la derecha de $k$: o se mantiene donde mismo, o se mueve a la izquierda.\n",
    "Por lo tanto,\n",
    "\n",
    "$$\n",
    "R[i,j-1]\\le R[i,j]\n",
    "$$\n",
    "\n",
    "Por un razonamiento análogo, se puede demostrar que\n",
    "\n",
    "$$\n",
    "R[i+1,j] \\ge R[i,j]\n",
    "$$\n",
    "\n",
    "Juntando ambos resultados, tenemos que para buscar la raíz óptima para $(i,j)$ ya no es necesario buscar en el rango $i+1 \\le k \\le j$, sino que basta buscar en\n",
    "\n",
    "$$\n",
    "R[i,j-1]\\le k \\le R[i+1,j]\n",
    "$$\n",
    "\n",
    "con los valores de borde $R[i,i+1]=i+1$.\n",
    "\n",
    "Para la implementación de este algoritmo optimizado, debemos manejar aparte el caso $d=1$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import numpy as np\n",
    "\n",
    "def calculaABBoptimo2(p,q):\n",
    "    n=len(q)-1\n",
    "    C=np.zeros((n+1,n+1)) # Esto ya deja la diagonal en cero\n",
    "    W=np.zeros((n+1,n+1))\n",
    "    R=np.zeros((n+1,n+1),dtype=int)\n",
    "    for i in range(0,n+1):\n",
    "        W[i,i]=q[i]\n",
    "    # Caso d=1\n",
    "    for i in range(0,n):\n",
    "        W[i,i+1]=W[i,i]+p[i+1]+q[i+1]\n",
    "        C[i,i+1]=W[i,i+1]\n",
    "        R[i,i+1]=i+1\n",
    "    # Casos de d=2 en adelante\n",
    "    for d in range(2,n+1):\n",
    "        for i in range(0,n-d+1):\n",
    "            j=i+d\n",
    "            W[i,j]=W[i,j-1]+p[j]+q[j]\n",
    "            C[i,j]=math.inf # +infinito\n",
    "            for k in range(R[i,j-1],R[i+1,j]+1):\n",
    "                m=W[i,j]+C[i,k-1]+C[k,j]\n",
    "                if m<C[i,j]:\n",
    "                    C[i,j]=m\n",
    "                    R[i,j]=k # anotamos dónde se alcanza el min\n",
    "    return (C[0,n],R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Costo óptimo= 2.35\n",
      "Arbol óptimo= (((☐X1☐)X2(☐X3☐))X4(☐X5☐))\n"
     ]
    }
   ],
   "source": [
    "p=[0,0.15,0.10,0.05,0.10,0.20]\n",
    "q=[0.05,0.10,0.05,0.05,0.05,0.10]\n",
    "(Copt,R)=calculaABBoptimo2(p,q)\n",
    "print(\"Costo óptimo=\", Copt)\n",
    "print(\"Arbol óptimo=\", ABBoptimo(R,0,5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Análisis del algoritmo optimizado\n",
    "\n",
    "En este nuevo algoritmo, el tamaño del rango que hay que examinar para llenar el casillero $(i,j)$ es $R[i+1,j]-R[i,j-1]+1$. Al sumar todos estos tamaños, todos los elementos del interior de la matriz $R$ se cancelan, porque aparecen en la suma una vez con signo positivo y una vez con signo negativo. Solo sobreviven diferencias entre elementos de los bordes. Como hay $\\Theta(n)$ casilleros en los bordes y cada diferencia es a lo más $n$, la suma total es $O(n^2)$. El término \"$+1$\" aporta un término cuadrático a la suma total, y por lo tanto el tiempo total de ejecución del algoritmo es $\\Theta(n^2)$.\n",
    "\n",
    "Por lo tanto, con esta optimización el algoritmo cúbico se transformó en un algoritmo cuadrático."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Splay Trees\n",
    "\n",
    "Los Splay Trees son una estrategia para garantizar que cualquier secuencia de $m$ operaciones en un árbol que llega a tener tamaño $n$, comenzando con un árbol vacío, toma tiempo $O(m\\log{n})$.\n",
    "\n",
    "Esto no garantiza que el costo de una operación individual no pueda tener costo $O(n)$, sino que el costo acumulado dividido por el número de operaciones da un promedio de $O(\\log{n})$ por operación. Se dice que una estructura de este tipo es eficiente en el sentido _amortizado_.\n",
    "\n",
    "La idea básica de un splay tree es que cuando una llave es accesada, se haga una secuencia de rotaciones para llevarla hasta la raíz. Si estas rotaciones se hacer de a un nivel a la vez, el resultado es lo que se llama \"move to root\", pero esa estrategia es vulnerable a que una secuencia de $m$ operaciones bien escogidas pueda hacerla tener un costo acumulado de $O(mn)$.\n",
    "\n",
    "La idea del \"splaying\" es hacer las rotaciones de a dos niveles a la vez. Supongamos que la llave accesada es $k$, y que las dos llaves siguientes hacia aarriba son $p$ (padre) y $a$ (abuelo). Hay tres casos:\n",
    "\n",
    "**Caso zig-zag**\n",
    "\n",
    "En este caso, se hace la misma rotación doble de los árboles AVL:\n",
    "\n",
    "![splay1](splay1.png)\n",
    "\n",
    "**Caso zig-zig**\n",
    "\n",
    "En este caso, el zig-zig se transforma en un zag-zag. Esto *no* es lo mismo que si se hubiesen hecho dos rotaciones simples:\n",
    "\n",
    "![splay2](splay2.png)\n",
    "\n",
    "El análisis de los splay trees es complejo, porque debe considerar la estructura cambiante del árbol en cada acceso realizado. Por otra parte, los splay trees son más fáciles de implementar que un AVL dado que no hay que verificar una condición de balance.\n",
    "\n",
    "**Caso zig**\n",
    "\n",
    "Esto solo aplica cuando la llave accesada está a un paso de la raíz. En este caso, se hace una rotación simple para llevarla a la raíz del árbol."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hashing\n",
    "\n",
    "En esta sección vamos a ver un enfoque llamado _Hashing_ que permite hacer búsquedas en tiempo esperado *constante*, en la medida que estemos dispuestos a no hacer uso del 100% de la memoria reservada para la estructura de datos.\n",
    "\n",
    "Antes de ver hashing propiamente tal, veremos una estructura más sencilla y más eficiente, pero de utilidad más limitada, que nos servirá como motivación."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bitmaps\n",
    "\n",
    "Supongamos que queremos almacenar $n$ números enteros no negativos, sabiendo que todos ellos están contenidos en el rango $[0..m-1]$, para algún valor de $m$.\n",
    "\n",
    "Una forma muy simple de poder almacenar estos números y hacer búsquedas, inserciones y eliminaciones eficientes es utilizar un arreglo $a[0],\\ldots,a[m-1]$, marcando con un $1$ los lugares correspondientes a los números que están presentes, y con $0$ a los que no.\n",
    "\n",
    "Por ejemplo, si $m=8$ y el conjunto de números a almacenar es $\\{1,4,7\\}$, el arreglo contendría lo siguiente:\n",
    "\n",
    "![bitmap](bitmap.png)\n",
    "\n",
    "Con esta representación, insertar la llave $x$ es hacer $a[x]=1$, para eliminarla hacemos $a[x]=0$ y para buscarla preguntamos si $a[x]==1$. Todas estas operaciones toman tiempo $\\Theta(1)$.\n",
    "\n",
    "¿Cómo es posible que se pueda violar la cota logarítmica que demostramos cuando vimos Búsqueda Binaria?\n",
    "\n",
    "La razón es porque esa cota se demostró para cualquier algoritmo que funcione en base a comparaciones, y este algoritmo de Bitmaps no hace comparaciones de llaves, sino que las usa como subíndice, lo cual en realidad es equivalente a hacer aritmética con las llaves.\n",
    "\n",
    "El motivo por el cual esta no es una solución muy usada es porque solo es aplicable si las llaves son enteros en un rango relativamente pequeño, porque de lo contrario el tamaño del arraglo $a$ podría ser exageradamente grande.\n",
    "\n",
    "El método de hashing trata de aproximar la eficiencia de los Bitmaps sin tener esa limitación sobre las llaves."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Funciones de hashing\n",
    "\n",
    "Una función de hashing es una función que transforma una llave $x$ en un valor $h(x) \\in [0..m-1]$, para un valor dado de $m$, donde $m$ es mucho menor que el tamaño del universo al cual pertenece $x$.\n",
    "La idea es utilizar la idea de un bitmap, utilizando $h(x)$ en lugar de $x$.\n",
    "\n",
    "La función $h$ debe ser de tipo *pseudoaleatorio*, esto es, debe distribuir sus valores uniformemente sobre el rango $[0..m-1]$, pero debe ser reproducible.\n",
    "\n",
    "Considerando que toda llave $x$ se codifica como una secuencia (posiblemente muy larga) de bits, y puede ser interpretada por lo tanto como un número entero, una familia de funciones de hashing puede obtenerse con la fórmula\n",
    "\n",
    "$$\n",
    "h(x) = (cx \\bmod p) \\bmod m\n",
    "$$\n",
    "\n",
    "donde $c$ es una constante y $p$ es un número primo. Distintos valores de estos parámetros producen distintas funciones de hashing.\n",
    "\n",
    "Python tiene una función ``hash()`` que se vamos a utilizar en nuestros ejemplos."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m=1000\n",
      "x=Patricio Poblete\n",
      "h(x)= 165\n"
     ]
    }
   ],
   "source": [
    "m=int(input(\"m=\"))\n",
    "x=input(\"x=\")\n",
    "print(\"h(x)=\",hash(x)%m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dado un conjunto de $n$ llaves, suponiendo por el momento que $n\\le m$, es posible que todas ellas sean mapeadas por la función $h$ a valores distintos. Si fuera ese el caso, podríamos utilizar los $h(x)$ con un bitmap sin problemas. Sin embargo, en la práctica esto es muy improbable, y seguramente vamos a encontrarnos con llaves distintas $x, y$ tales que $h(x)=h(y)$. Esto se llama una _colisión_.\n",
    "\n",
    "El que alguna colisión sea probable que exista viene de la *paradoja de los cumpleaños*, que veremos a continuación. Por otra parte, en promedio no puede haber muchas colisiones, porque para un valor de $k$ dado, el múmero promedio de llaves $x$ que tienen $h(x)=k$ es $n/m\\le 1$, dado que suponemos que $h(x)$ distribuye las llaves uniformemente."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### La Paradoja de los Cumpleaños\n",
    "\n",
    "Supongamos que en una sala hay $n$ personas. ¿Cuán grande debe ser $n$ para que sea probable que existan dos o más personas con cumpleaños el mismo día? Más precisamente, ¿para qué valor de $n$ la probabilidad de que haya alguna colisión de cumpleaños es $\\ge 1/2$?\n",
    "\n",
    "Resulta más fácil calcular la probabilidad opuesta $d_n$ de que _no_ haya colisión de cumpleaños. Esta probabilidad es igual a\n",
    "\n",
    "$$\n",
    "d_n = \\left( \\frac{365}{365} \\right) \\left( \\frac{364}{365} \\right) \\cdots \\left( \\frac{365-n+1}{365} \\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "%pylab inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x117ea24e0>]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAH4xJREFUeJzt3Xl8VPW9//HXZ2aykEAIkLAlQIBEFlEUIuCuaCtYBbVuqLetF+VaQW31V6u3rT+rvV30utatqNVqW63VXuVSWkTEXYTgwr6EPaxhX0LI9r1/zGBjDGSAmZzMmffz8cgjOSdfMu/zOPDm5Mw552vOOURExF8CXgcQEZHYU7mLiPiQyl1ExIdU7iIiPqRyFxHxIZW7iIgPqdxFRHxI5S4i4kMqdxERHwp59cI5OTmuoKDAq5cXEUlIc+bM2eKcy21qnGflXlBQQElJiVcvLyKSkMxsdTTjdFpGRMSHVO4iIj6kchcR8SGVu4iID6ncRUR8qMlyN7Pfm9lmM5t/kO+bmT1qZqVmNtfMBsU+poiIHI5ojtyfB0Yc4vsjgaLIxzjgyaOPJSIiR6PJ69ydc++ZWcEhhowGXnDh+fpmmlm2mXVxzm2IUcavmLN6Gx+VbqVP5zb07ZxFfrtWBAIWj5cSEUlYsbiJKQ9YW2+5LLLua+VuZuMIH93TvXv3I3qxklXbeWDa0i+Xs9JDjBjQmdEn5DGsVweCKnoRkZiUe2Nt2uis2865icBEgOLi4iOamfs/zuzN1cN6sHTTbpZs3M3sVduYMm8jr5SU0SkrjRvO7M1VQ7uTFgoeyY8XEfGFWJR7GdCt3nI+sD4GP/egWqeFGNS9HYO6t2PMkO5UVtfy9uLNvPDxKn7+vwt55v2V3HJuEZcOytcpGxFJSrG4FHIS8J3IVTPDgJ3xOt9+MOkpQc4/rgsvXT+MP44dSk7rVG5/dS5jnp5J2faK5owiItIiRHMp5EvAx0AfMyszs7FmdoOZ3RAZMgVYAZQCTwM3xi1tE8yM04pyeH38qdx36fEsWL+LkQ+/z6tzygi/3ysikhzMq9IrLi528X4q5NptFdz2yhfMWrWNMUO6cc/oAaQEdd+WiCQuM5vjnCtuapyvm65b+wxeGjeM8Wf35qVZa/n352ezq7La61giInHn63IHCAaMH53Xl/suPZ6Pl2/l2098xLod+7yOJSISV74v9wMuL+7GC2OHsHFXJWMmzmS9Cl5EfCxpyh3glN45vDh2KNv3VnHV0zPZuLPS60giInGRVOUOcEK3bP4wdghb9oQLfvMuFbyI+E/SlTvAoO7t+MO/n8TGXZVc+/xs9u6v8TqSiEhMJWW5Awzu0Z7Hrx7Eog27uPmlz6it03XwIuIfSVvuAGf36cjPRx3L9MWbuXfyQq/jiIjETCyeLZPQ/u3kAlZtreDZD1bSOzeTfzu5wOtIIiJHLamP3A/4z/P7MbxvR+6ZvJDP1mz3Oo6IyFFTuRO+0enBywfSKSud8X/6lO17q7yOJCJyVFTuEdkZqTxx9SC27KniB3/5nDq9wSoiCUzlXs/x+dn8/1H9eXdpOU+8U+p1HBGRI6Zyb+CqId0ZNbArD721jC/W7vA6jojIEVG5N2Bm3Dt6AB3bpPHDVz5nX1Wt15FERA6byr0RbTNSeOCygawo38uv/rHI6zgiIodN5X4QpxTmMPa0nrzw8WreWbLZ6zgiIodF5X4IPzqvD8d0as0dr81jtyb5EJEEonI/hPSUIPddOpDNuyv5zT8Xex1HRCRqKvcmnNAtm2tP7ckfZ65h1sptXscREYmKyj0Kt33zGPLbteKO1+ZSWa2rZ0Sk5VO5RyEjNcQvLz6OFVv28tu3l3kdR0SkSSr3KJ1xTC6XnJjHxPdWsLx8j9dxREQOSeV+GO48vx/poSB3T1qAc3r2jIi0XCr3w5DbJo3bvnkM7y/bwj/mb/Q6jojIQancD9M1w3rQr0sW905eSEWV5l4VkZZJ5X6YQsEA944+lg07K/nt23pypIi0TCr3I1Bc0J5vD8rnmfdXsHrrXq/jiIh8jcr9CP14RB9SggF+NUV3ropIy6NyP0Ids9K58aze/HPBRmau2Op1HBGRr4iq3M1shJktMbNSM7ujke93N7MZZvaZmc01s/NjH7Xlue70XuRlt+LeyQup1bR8ItKCNFnuZhYEHgdGAv2BMWbWv8GwnwKvOOdOBK4Enoh10JYoPSXIj0f2ZcH6Xbz2aZnXcUREvhTNkfsQoNQ5t8I5VwW8DIxuMMYBWZGv2wLrYxexZbvw+C4M6p7N/VOX6NJIEWkxoin3PGBtveWyyLr67gauMbMyYApwU0zSJQAz4yff6k/57v08+/5Kr+OIiADRlbs1sq7hCeYxwPPOuXzgfOBFM/vazzazcWZWYmYl5eXlh5+2hRrcox3nHduJ3723gq179nsdR0QkqnIvA7rVW87n66ddxgKvADjnPgbSgZyGP8g5N9E5V+ycK87NzT2yxC3U7SP6sq+6Vjc2iUiLEE25zwaKzKynmaUSfsN0UoMxa4BzAMysH+Fy98+heRR657bm8uJu/OmT1bqxSUQ812S5O+dqgAnAVGAR4atiFpjZPWY2KjLsNuB6M/sCeAn4nkvCxyb+8NwiQoEA909d4nUUEUlyoWgGOeemEH6jtP66u+p9vRA4NbbREk/HrHSuO70nv327lBvO3MmAvLZeRxKRJKU7VGPs+jN60bZVCg+8qaN3EfGOyj3GstJTuOHM3sxYUk7JKk2oLSLeULnHwXdP6UFumzTum7pEMzaJiCdU7nGQkRripuGFzFq5jfeXbfE6jogkIZV7nFx5Unfysltxv47eRcQDKvc4SQ0FuOXcIuat28m0hZu8jiMiSUblHkeXnJhHQYcMHnprGXV6JLCINCOVexyFggFuPqeIRRt28ebCjV7HEZEkonKPs1EDu9IrN5OHpunoXUSaj8o9zkLBALecU8SSTbv5x3wdvYtI81C5N4MLju9KYcfWPPzWUk3HJyLNQuXeDIIB4wfnFrFs8x6mzNvgdRwRSQIq92Zy/oAuFHVszW/f1rl3EYk/lXszCQSMm84pYummPTr3LiJxp3JvRt86rgu9czN5dLqO3kUkvlTuzSgYMG4aHr5yZuoCHb2LSPyo3JvZhQO70isnk0d09C4icaRyb2bBgDFheCGLN+5m2iI9c0ZE4kPl7oFRA7vSo0MGj71dqidGikhcqNw9EAoGuPGs3sxbt5N3lpZ7HUdEfEjl7pGLT8wnL7sVv52+TEfvIhJzKnePpIYC3HBWbz5ds4OPl2/1Oo6I+IzK3UOXDc6nU1Yaj769zOsoIuIzKncPpacE+Y8zejNzxTZmr9rmdRwR8RGVu8fGDOlOh8xUHnu71OsoIuIjKnePtUoNct3pvXh3aTlzy3Z4HUdEfELl3gJcM6w7WekhHb2LSMyo3FuANukpXHtqT95cuInFG3d5HUdEfEDl3kJce2oBmalBnpix3OsoIuIDKvcWIjsjlWtO7sHkuetZUb7H6zgikuBU7i3Idaf1IiUY4Ml3dPQuIkcnqnI3sxFmtsTMSs3sjoOMudzMFprZAjP7c2xjJofcNmmMGdKd//lsHWXbK7yOIyIJrMlyN7Mg8DgwEugPjDGz/g3GFAF3Aqc6544FfhCHrElh3Bm9MIOJ763wOoqIJLBojtyHAKXOuRXOuSrgZWB0gzHXA48757YDOOc2xzZm8uia3YpLTszn5dlr2by70us4IpKgoin3PGBtveWyyLr6jgGOMbMPzWymmY1o7AeZ2TgzKzGzkvJyPer2YL5/Vm9qaut49v2VXkcRkQQVTblbI+saPqM2BBQBZwFjgGfMLPtrf8i5ic65YudccW5u7uFmTRoFOZlcOLArL85czfa9VV7HEZEEFE25lwHd6i3nA+sbGfOGc67aObcSWEK47OUIjT+7kIqqWp77aJXXUUQkAUVT7rOBIjPraWapwJXApAZjXgfOBjCzHMKnafSO4FE4plMbvtm/E89/uJLdldVexxGRBNNkuTvnaoAJwFRgEfCKc26Bmd1jZqMiw6YCW81sITAD+JFzTjNQHKUJwwvZVVnDizNXex1FRBKMeTXFW3FxsSspKfHktRPJd34/iwXrdvLBj4fTKjXodRwR8ZiZzXHOFTc1TneotnA3DS9k694qXpq1xusoIpJAVO4t3EkF7RnSsz0T31vB/ppar+OISIJQuSeACWcXsnFXJa/NWed1FBFJECr3BHB6UQ4D89vyxDulVNfWeR1HRBKAyj0BmBkThhdRtn0fkz5veIuBiMjXqdwTxLn9OtKvSxaPv1NKbZ03VziJSOJQuScIM2PC2YWsKN/LlHkbvI4jIi2cyj2BjBjQmd65mTz2dil1OnoXkUNQuSeQYMCYMLyQJZt2M23RJq/jiEgLpnJPMBce35UeHTJ47O1SvLq7WERaPpV7ggkFA4w/q5B563YyY4nmRBGRxqncE9DFg/LIy27FI9N19C4ijVO5J6CUYIDxZxfyxdodvLdsi9dxRKQFUrknqEsH59O1bTqPvLVUR+8i8jUq9wSVGgrw/bML+XTNDj5arkfni8hXqdwT2OXF+XTOSueRt5bp6F1EvkLlnsDSQkG+f1ZvZq3axsc6eheRelTuCe6Kk7rROSudh3X0LiL1qNwTXHpKkBvP1tG7iHyVyt0HLi/W0buIfJXK3Qd09C4iDancfeLA0fuD03Tdu4io3H0jPSXI+OGFlKzerrtWRUTl7idXFHcjL7sVD765REfvIklO5e4jqaEAN59TyBdlO5m+SE+MFElmKnefuWRQPj06ZPDgtKWarUkkiancfSYlGOAH5xaxcMMupi7Y6HUcEfGIyt2HRg3Mo7Bjax6ctpRaHb2LJCWVuw8FA8at3ziGZZv38Ppn67yOIyIeULn71MgBnTkury0PvbWUqpo6r+OISDOLqtzNbISZLTGzUjO74xDjLjUzZ2bFsYsoR8LM+H/n9aFs+z5enr3G6zgi0syaLHczCwKPAyOB/sAYM+vfyLg2wM3AJ7EOKUfmjKIchvZsz6PTS6moqvE6jog0o2iO3IcApc65Fc65KuBlYHQj4+4F7gMqY5hPjoKZcfuIvmzZs5/nPlzldRwRaUbRlHsesLbecllk3ZfM7ESgm3NucgyzSQwM7tGOc/t15Kl3l7N9b5XXcUSkmURT7tbIui+vrzOzAPAQcFuTP8hsnJmVmFlJeXl59CnlqPzovL7s3V/D4zNKvY4iIs0kmnIvA7rVW84H1tdbbgMMAN4xs1XAMGBSY2+qOucmOueKnXPFubm5R55aDkufzm349qB8Xvh4NWu3VXgdR0SaQTTlPhsoMrOeZpYKXAlMOvBN59xO51yOc67AOVcAzARGOedK4pJYjsit3zwGM3hw2lKvo4hIM2iy3J1zNcAEYCqwCHjFObfAzO4xs1HxDiix0aVtK649tSevf76OBet3eh1HROLMvHo0bHFxsSsp0cF9c9q5r5oz75/BcXlteXHsUK/jiMgRMLM5zrkm7yXSHapJpG2rFCacXcj7y7bwzhI9EljEz1TuSeY7JxdQ0CGD//r7Impq9VgCEb9SuSeZ1FCAO0b2Y9nmPbw8e23Tf0BEEpLKPQmdd2wnhvZsz0PTlrKrstrrOCISByr3JGRm/OyC/myrqNKNTSI+pXJPUgPy2nLJifk898EqVm/d63UcEYkxlXsSu31EH1KCxr2TF3kdRURiTOWexDplpXPTOUW8tWiTLo0U8RmVe5K79tQCeuZkcs/khZqxScRHVO5JLi0U5K4L+rOifC/Pf7TS6zgiEiMqd+Hsvh0Z3rcjj7y1jE27NNeKiB+o3AWAuy7oT3Wd497JC72OIiIxoHIXAApyMrnxrN5MnruB95dpIhWRRKdyly/dcGZvCjpk8LPX51NZXet1HBE5Cip3+VJ6SpB7LxrAqq0VPPXucq/jiMhRULnLV5xelMsFx3fhiXeWs3KL7lwVSVQqd/mauy7oT1oowB2vzaWuzpvJXETk6Kjc5Ws6ZqXzk/P78cnKbfylRI8FFklEKndp1BUndePkXh345ZRFuvZdJAGp3KVRZsavLjmOqpo6fvb6fLyaa1dEjozKXQ6qICeTW79xDG8u3MTkuRu8jiMih0HlLoc09rSeDOyWzc/emM/m3To9I5IoVO5ySKFggAcuG8i+qlrufG2eTs+IJAiVuzSpsGNrbh/Rl+mLN/PqnDKv44hIFFTuEpVrTylgaM/23PO/CynbXuF1HBFpgspdohIIGP992UDqnOPWv3xBrW5uEmnRVO4StW7tM7j3ogHMWrWNJ2aUeh1HRA5B5S6H5eIT8xh9Qlcenr6MOau3ex1HRA5C5S6Hxcy496IBdGmbzi0vf8auymqvI4lII1Tuctiy0lN45MoT2bCzkjtem6vLI0VaIJW7HJHBPdrxo/P6MGXeRp7/aJXXcUSkgajK3cxGmNkSMys1szsa+f6tZrbQzOaa2XQz6xH7qNLSjDu9F+f268R//X0Rn67R+XeRlqTJcjezIPA4MBLoD4wxs/4Nhn0GFDvnjgdeBe6LdVBpeQIB44HLBtIlO50Jf/qUbXurvI4kIhHRHLkPAUqdcyucc1XAy8Do+gOcczOccwfubJkJ5Mc2prRUbTNSePLqwWzZW8VNL31KTW2d15FEhOjKPQ+oP2NDWWTdwYwF/tHYN8xsnJmVmFlJeXl59CmlRRuQ15ZfXnwcH5Zu5Rd/X+R1HBEhunK3RtY1enmEmV0DFAP3N/Z959xE51yxc644Nzc3+pTS4l06OJ+xp/Xk+Y9W8cpszd4k4rVoyr0M6FZvOR9Y33CQmZ0L/AQY5ZzbH5t4kkjuHNmX04ty+Mnr85izepvXcUSSWjTlPhsoMrOeZpYKXAlMqj/AzE4Efke42DfHPqYkglAwwGNjBpHfLoPrX5jDqi17vY4kkrSaLHfnXA0wAZgKLAJecc4tMLN7zGxUZNj9QGvgr2b2uZlNOsiPE59rm5HCc987Cecc33tulq6gEfGIeXV3YXFxsSspKfHktSX+5qzezlVPz+TYrln8+fphpKcEvY4k4gtmNsc5V9zUON2hKnExuEc7Hr7iBD5bu4ObXvpMl0iKNDOVu8TNyOO6cPeFxzJt4SZuf3UudXoGvEizCXkdQPztu6cUsGtfNQ9MW0qb9BB3jzoWs8aurhWRWFK5S9xNGF7Irspqnn5/JRlpIW4/r48KXiTOVO4Sd2bGf57fj71VtTz5znKcgx+PUMGLxJPKXZqFmfGL0QMw4Kl3l1NbV8d/nt9PBS8SJyp3aTaBgPGLiwYQChhPv7+S6lrHXRf0JxBQwYvEmspdmpWZcfeoYwkFAzz7wUp2VFRx36UDSQ3pwi2RWFK5S7MzM376rX60z0zl/qlL2FZRzZNXDyIzTX8dRWJFh0viCTNj/NmF/PqS4/hgWTlXPT2TzbsqvY4l4hsqd/HUlUO689Q1g1m6aQ+jH/+Q+et2eh1JxBdU7uK5bx7bmb/ecDIAlz31Mf+cv9HjRCKJT+UuLcKAvLa8MeFU+nRuww1/nMOv/7FYz6MROQoqd2kxOrZJ5+Vxw7hqaHeeenc5Vz/zCZt36zy8yJFQuUuLkp4S5JcXH8eDlw/ki7IdnP/IB8xYovlfRA6Xyl1apEsG5fPG+NPokJnKtc/N5mevz2dfVa3XsUQShspdWqw+ndvwxoRTue60nrw4czXfevR9Zq3U3Kwi0VC5S4uWnhLkpxf058/XDaWqto7Lf/cxd/5tHjv3VXsdTaRFU7lLQjilMIc3f3gG153Wk7/MXsM3HnyXv31apglARA5C5S4JIyM1xE8v6M8b40+jS9t0bn3lCy558iM+XbPd62giLY7KXRLOcflt+Z8bT+WBywayfsc+LnniI77/xzks27Tb62giLYae1CQJKRAwvj04nxEDOjPxvRU8+8FKpi7YyEUn5DF+eCG9c1t7HVHEU+acN+csi4uLXUlJiSevLf6zbW8Vv3t3OX/4eBX7a+o4r39nbjirNyd0y/Y6mkhMmdkc51xxk+NU7uInW/bs5/kPV/HCx6vYVVnD4B7t+M7JPRg5oIueGS++oHKXpLZnfw0vz1rDizNXs3prBTmt0/j24DwuG5xPYcc2XscTOWIqdxGgrs7x3rJy/jhzNTOWlFNb5zihWzYXndCVkcd1oVNWutcRRQ6Lyl2kgc27K5n0+XpenVPG4o27MYPiHu0479jODO/bkV56E1YSgMpd5BBKN+9hyrwNTJm3gcUbw5dQFnTI4MxjcjmlMIdhvTrQtlWKxylFvk7lLhKltdsqeGfJZqYv3swnK7axr7qWgEH/rlkU92jP4B7tGNSjHV3bpmNmXseVJKdyFzkCVTV1fLZmOx8u38rsldv4fO0O9lWHn0bZITOVAXltGZCXRZ/OWfTt3IaeOZmkBHUVjjSfaMs9qpuYzGwE8AgQBJ5xzv26wffTgBeAwcBW4Arn3KrDDS3itdRQgKG9OjC0VwcAqmvrWLRhF1+s3cHcsp3MW7eTD0q3UBt5pk1K0OjePoNeua3plZNJ9w4Z9GifSbf2rejcNp20UNDLzZEk1mS5m1kQeBz4BlAGzDazSc65hfWGjQW2O+cKzexK4DfAFfEILNKcUoIBjs/P5vj8f90Mtb+mluWb97Jk0y6WbtrDivI9rCjfy7tLyqlqMDVgbps0urZNp2NWOh3bpNGxTTo5bVLpkJlK+8w02memkJ2RSnarFEL6DUBiKJoj9yFAqXNuBYCZvQyMBuqX+2jg7sjXrwKPmZk5r875iMRRWihI/65Z9O+a9ZX1tXWOTbsqWbOtgjXbKtiwo5L1O/axfuc+1m6roGTVNrZXHPxRxZmpQbJapdAmPUSb9BRap4VonRYiIzVIZlqIVqlBMlKCtEoNkpYSJD0UIC0lSFooQGooQFow/Dk1FCAUCJAaMkKBAKGgkRIMEAwYoYBFPgcIBCBo4WW9l+A/0ZR7HrC23nIZMPRgY5xzNWa2E+gAbIlFSJFEEAwYXbNb0TW7FcMip3UaqqqpY3tFFVv27Gfrniq2V1Sxo6Ka7RVV7K6sYde+anbuq2ZvVQ07Kqoo215BRVUte/fXUFFVS02cHnFsFi76gBmBAOHPZpiBEX6WT8AMA6ze+vDn+sv25c878P9F+E/9azm8rv5rW6PrOcj4g29D/P+DitUr3HxOERcO7Bqjn9a4aMq9se1p+DcsmjGY2ThgHED37t2jeGkRf0kNBeiUlX7EN09V19ZRWV3Lvupa9lfXsb+mjv01teyvqaOq3kdNXR1VtY7qmjpq6xw1dY6auvDXtXWO6lpHnXNfLte5A8vg6n+Nwzmoc//6HP7/Jbzs3L/GOP61fOBf/4ESqP9LfP1iqP+7/VfXNz7+oJrhHIGL4Ys0x2W20ZR7GdCt3nI+sP4gY8rMLAS0Bb42H5pzbiIwEcJXyxxJYJFklhIMkBIM0CZd1+DLoUXzDs5soMjMeppZKnAlMKnBmEnAdyNfXwq8rfPtIiLeafLIPXIOfQIwlfClkL93zi0ws3uAEufcJOBZ4EUzKyV8xH5lPEOLiMihRXWdu3NuCjClwbq76n1dCVwW22giInKkdGGtiIgPqdxFRHxI5S4i4kMqdxERH1K5i4j4kGeP/DWzcmD1YfyRHJLzcQbJuN3JuM2QnNudjNsMR7fdPZxzuU0N8qzcD5eZlUTzDGO/ScbtTsZthuTc7mTcZmie7dZpGRERH1K5i4j4UCKV+0SvA3gkGbc7GbcZknO7k3GboRm2O2HOuYuISPQS6chdRESilBDlbmYjzGyJmZWa2R1e54kHM+tmZjPMbJGZLTCzWyLr25vZNDNbFvnczuussWZmQTP7zMwmR5Z7mtknkW3+S+RR075iZtlm9qqZLY7s85OTZF//MPL3e76ZvWRm6X7b32b2ezPbbGbz661rdN9a2KORbptrZoNilaPFl3u9CbpHAv2BMWbW39tUcVED3Oac6wcMA8ZHtvMOYLpzrgiYHln2m1uARfWWfwM8FNnm7YQnYPebR4B/Ouf6AgMJb7+v97WZ5QE3A8XOuQGEHyF+Jf7b388DIxqsO9i+HQkURT7GAU/GKkSLL3fqTdDtnKsCDkzQ7SvOuQ3OuU8jX+8m/I89j/C2/iEy7A/ARd4kjA8zywe+BTwTWTZgOOGJ1sGf25wFnEF4HgScc1XOuR34fF9HhIBWkRnbMoAN+Gx/O+fe4+sz0R1s344GXnBhM4FsM+sSixyJUO6NTdCd51GWZmFmBcCJwCdAJ+fcBgj/BwB09C5ZXDwM3A7URZY7ADucczWRZT/u715AOfBc5HTUM2aWic/3tXNuHfDfwBrCpb4TmIP/9zccfN/Grd8SodyjmnzbL8ysNfAa8APn3C6v88STmV0AbHbOzam/upGhftvfIWAQ8KRz7kRgLz47BdOYyHnm0UBPoCuQSfi0REN+29+HEre/74lQ7tFM0O0LZpZCuNj/5Jz7W2T1pgO/pkU+b/YqXxycCowys1WET7cNJ3wknx35tR38ub/LgDLn3CeR5VcJl72f9zXAucBK51y5c64a+BtwCv7f33DwfRu3fkuEco9mgu6EFznX/CywyDn3YL1v1Z98/LvAG82dLV6cc3c65/KdcwWE9+vbzrmrgRmEJ1oHn20zgHNuI7DWzPpEVp0DLMTH+zpiDTDMzDIif98PbLev93fEwfbtJOA7katmhgE7D5y+OWrOuRb/AZwPLAWWAz/xOk+ctvE0wr+OzQU+j3ycT/gc9HRgWeRze6+zxmn7zwImR77uBcwCSoG/Amle54vD9p4AlET29+tAu2TY18DPgcXAfOBFIM1v+xt4ifB7CtWEj8zHHmzfEj4t83ik2+YRvpIoJjl0h6qIiA8lwmkZERE5TCp3EREfUrmLiPiQyl1ExIdU7iIiPqRyFxHxIZW7iIgPqdxFRHzo/wD5hNSRHavQhgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "n=range(1,101)\n",
    "d=zeros(100)\n",
    "d[0]=1\n",
    "for k in range(1,100):\n",
    "    d[k]=d[k-1]*(365-k)/365\n",
    "plt.plot(n,d,label='$d_n$')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para $n=23$ se tiene $d_n = 0.4927 < 1/2$, por lo tanto para $n=23$ la probabilidad de que exista alguna colisión es mayor que $1/2$.\n",
    "\n",
    "Nótese que $23$ es relativamente pequeño comparado con $365$, lo cual indica, en general, que no es necesario que $n$ sea muy grande en relación a $m$ para que sea probable que exista alguna colisión. Por otra parte, el número total de colisiones no puede ser muy grande, y ambos hechos son los que debemos tener en consideración al aplicar la idea de hashing al diseño de diccionarios."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Métodos de resolución de colisiones\n",
    "\n",
    "Dado que es inevitable que existan colisiones (aunque esperamos que sean pocas), debe haber alguna manera de resolver el problema que se produce cuando dos o más llaves son enviadas por la función de hashing al mismo casillero de la tabla.\n",
    "\n",
    "Existen dos grandes familias de métodos:\n",
    "\n",
    "* *Encadenamiento*: Utilizar punteros para enlazar los elementos que coinciden en su función de hashing.\n",
    "\n",
    "* *Direccionamiento abierto (Open addressing)*: Utilizar una secuencia de funciones de hashing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hashing con Encadenamiento\n",
    "\n",
    "La idea en este método es que todos los elementos que caen en el mismo lugar de la tabla se enlazan en una lista secuencial, y en cada casillero se almacena el puntero al inicio de la lista respectiva.\n",
    "\n",
    "![encadenamiento](encadenamiento.gif)\n",
    "\n",
    "Para analizar la eficiencia de este método, recordemos que para un conjunto de $n$ llaves hemos definido $C_n$ y $C'_n$ como respectivamente el número esperado de comparaciones de llaves en una búsqueda exitosa y en una búsqueda infructuosa.\n",
    "\n",
    "Si suponemos que $n$ llaves se lanzan al azar sobre una tabla de tamaño $m$, el número esperado de llaves por casillero es $n/m$, y eso es también el largo esperado de una lista aleatoria. En una búsqueda infructuosa hay que recorrer toda la lista, y por lo tanto tenemos que\n",
    "\n",
    "$$\n",
    "C'_n = \\frac{n}{m}\n",
    "$$\n",
    "\n",
    "Para analizar el costo esperado de búsqueda exitosa $C_n$, consideremos las llaves en orden de inserción. Supongamos que hay $k$ llaves en la tabla e insertamos una más. El largo esperado de la lista en que le toca almacenarse es $k/m$, y supongamos que la nueva llave se agrega al final de su lista. Si ahora hacemos una búsqueda exitosa de llave recién insertada, su costo esperado de búsqueda será $1+k/m$. Para calcular el costo esperado de búsqueda exitosa sobre todas las llaves de la tabla, tenemos que sumar esos costos individuales y dividir por $n$:\n",
    "\n",
    "$$\n",
    "C_n = \\frac{1}{n} \\sum_{0\\le k\\le n-1} \\left( 1 + C'_k \\right) = \\frac{1}{n} \\sum_{0\\le k\\le n-1} \\left( 1 + \\frac{k}{m} \\right) = 1 + \\frac{n-1}{2m}\n",
    "$$\n",
    "\n",
    "Se define el *factor de carga de la tabla* $\\alpha$ como el cuociente\n",
    "\n",
    "$$\n",
    "\\alpha = \\frac{n}{m}\n",
    "$$\n",
    "\n",
    "Se dice que una tabla está $\\alpha$-llena si el cuociente $n/m$ se mantiene constante a medida que $n$ y $m$ crecen.\n",
    "\n",
    "Para una tabla de hashing con encadenamiento que está $\\alpha$-llena, se tiene que\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C'_n & = \\alpha \\\\\n",
    "C_n & \\approx 1+\\frac{\\alpha}{2}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Esto ilustra un hecho que caracteriza a las tablas de hashing: cuando el factor de carga $\\alpha$ se mantiene constante, los costos esperados de búsqueda son constantes, y no dependen de $n$ y $m$ por separado, sino de su cuociente $\\alpha$.\n",
    "\n",
    "Una debilidad de muchas tablas de hashing es que su peor caso puede ser muy malo. En el caso de las tablas de hashing con encadenamiento, el peor caso se da cuando todas las llaves caen en el mismo casillero, y en ese caso los costos de búsqueda serían $\\Theta(n)$, porque la estructura degenera a una simple lista lineal.\n",
    "\n",
    "Sin embargo, una buena función de hashing hace que ese peor caso sea extremadamente improbable, de modo que en la práctica no hay problema en confiar en que el costo observado será cercano al costo esperado que predice el modelo.\n",
    "\n",
    "La *eliminación* de una llave es sencilla, porque basta desenlazarla de la lista en que se encuentra."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hashing con Direccionamiento abierto\n",
    "\n",
    "Otra forma de resolver colisiones es disponer de una *secuencia* de funciones de hashing $\\{ h_0(x), h_1(x),\\ldots\\}$, donde cada valor es distinto de todos los anteriores. Para insertar una nueva llave primero se prueba en el casillero $h_0(x)$, si está ocupado se intenta en $h_1(x)$ y así sucesivamente. Para hacer una búsqueda, se sigue el mismo itinerario.\n",
    "\n",
    "Lo anterior en realidad define una familia de métodos, los cuales dependen de cómo se defina esa secuencia de funciones de hashing. A continuación veremos los dos más importantes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Probing\n",
    "\n",
    "Este es un método muy sencillo, que consiste en probar primero en el casillero $h(x)$, y si está ocupado, continuar buscando secuencialmente hacia la derecha, hasta encontrar un lugar libre. Si llegamos al extremo derecho de la tabla, continuamos en el extremo izquierdo, como si la tabla fuera circular.\n",
    "\n",
    "Más formalmente, la secuencia de funciones de hashing se define como\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "h_0(x) & = h(x)\\\\\n",
    "h_{i+1}(x) & = (h_i(x)+1) \\bmod m\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "![LinearProbing](LinearProbing.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 6.3 (Inserciones en una tabla de hashing con Linear Probing)\n",
    "\n",
    "Suponga que se tiene una tabla de hashing con Linear Probing, de tamaño 10, inicialmente vacía, con la función de hashing $h(x) = x \\bmod 10$ (por ejemplo, $h(64)=4$). Muestre en la siguiente tabla el resultado de insertar (a mano) la siguiente secuencia de llaves:\n",
    "\n",
    "```\n",
    "34, 59, 45, 27, 14, 22, 75, 25\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![EjercicioLinearProbing](EjercicioLinearProbing.png)\n",
    "\n",
    "Utilizaremos la siguiente función para ver si su respuesta está correcta:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def chequea_tabla(lista):\n",
    "    h=0\n",
    "    for x in lista:\n",
    "        h = (h*100+x) % 100000007\n",
    "    print(\"OK\" if h==60375958 else \"Error\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En el siguiente recuadro reemplace la lista de ceros por la lista de los elementos resultantes en la tabla. Si un casillero queda vacío, escriba un cero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error\n"
     ]
    }
   ],
   "source": [
    "chequea_tabla([0,0,0,0,0,0,0,0,0,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El análisis de este método de Linear Probing es complicado, por lo que solo daremos los resultados.\n",
    "\n",
    "Para una tabla $\\alpha$-llena, tenemos que\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C'_n & \\approx \\frac{1}{2}\\left(1+\\frac{1}{(1-\\alpha)^2} \\right) \\\\\n",
    "C_n & \\approx \\frac{1}{2}\\left(1+\\frac{1}{1-\\alpha} \\right)\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "En el caso de una tabla llena ($\\alpha\\to 1$), estas fórmulas no nos sirven, porque los denominadores tienden a cero. Se puede hacer obtener fórmulas precisas para ese caso, esto es, para el caso $n=m$ cuando la búsqueda es exitosa, o $n=m-1$ para una búsqueda infructuosa o inserción (porque en ambos casos debe haber al menos un casillero vacío):\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C'_{m-1} & = \\Theta(m) \\\\\n",
    "C_m & = \\Theta(\\sqrt{m})\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Cuando una tabla de hashing con Linear Probing se va acercando a estar llena, el método se vuelve muy lento:\n",
    "\n",
    "$\\alpha$ | $C_n$ | $C'_n$\n",
    "--------|--------|-------\n",
    "0.6 | 1.75 | 3.63\n",
    "0.7 | 2.17 | 6.06\n",
    "0.8 | 3.00 | 13.00\n",
    "0.9 | 5.50 | 50.50\n",
    "0.99 | 50.50 | 5000.50\n",
    "0.999 | 500.50 | 500000.50\n",
    "\n",
    "Si observamos la tabla a medida que se va llenando, veremos que empiezan a aparecer bloques (*clusters*) de casilleros ocupados.\n",
    "\n",
    "![clusters](clusters.gif)\n",
    "\n",
    "Idealmente, querríamos que los *clusters* fueran pequeños, porque así una llave que viene llegando necesita recorrer un camino corto hasta encontrar un casillero vacío. Pero en realidad ocurre todo lo contrario.\n",
    "En efecto, si la función de hashing distribuye los elementos uniformemente dentro de la tabla, *la probabilidad que un cluster crezca es proporcional a su tamaño*. Esto implica que una mala situación se vuelve peor cada vez con mayor probabilidad. Sin embargo, este no es todo el problema. La situación empeora cuando dos clusters están separados solo por un casillero libre y ese casillero es ocupado por la llave entrante: ambos clusters se fusionan en uno mucho más grande.\n",
    "\n",
    "Otro problema que surge con linear probing es conocido como *clustering secundario*: si al realizar la búsqueda de dos elementos en la tabla se encuentran con el mismo casillero ocupado, entonces toda la búsqueda subsiguiente es la misma para ambos elementos.\n",
    "\n",
    "El peor caso de Linear Probings es muy malo, y también increíblemente improbable. Se da cuando todas las llaves colisionan en un solo casillero, y en ese caso la estructura degenera a una simple búsqueda secuencial, con costos de búsqueda $\\Theta(n)$.\n",
    "\n",
    "Respecto de la eliminación de elementos, es importante notar que no se puede eliminar un elemento y simplemente dejar su casillero vacío, puesto que las búsquedas terminarían en dicho casillero. Existen dos maneras para eliminar elementos de la tabla:\n",
    "\n",
    "* Marcar el casillero como \"eliminado\", pero sin liberar el espacio (excepto cuando se necesita para una inserción). Esto produce que las búsquedas puedan ser lentas incluso si el factor de carga de la tabla es pequeño.\n",
    "* Eliminar el elemento, liberar el casillero y mover elementos dentro de la tabla hasta que un casillero \"verdaderamente\" libre sea encontrado. Implementar esta operación es complejo y costoso."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hashing Doble\n",
    "\n",
    "Este es un método que evita el problema del clustering secundario, reemplazándolo por clustering terciario, que afecta menos el desempeño.\n",
    "\n",
    "La idea es generar la secuencia de funciones de hashing usando **dos** funciones de hashing independientes: $h(x)$ y $s(x)$ (\"step\"), tales que $h(x) \\in [0..m-1]$ y $s(x) \\in [1..m-1]$. Si el casillero $h(x)$ está ocupado, se intenta en $h(x)+s(x)$, $h(x)+2s(x)$ y así sucesivamente, todo esto módulo el tamaño de la tabla.\n",
    "\n",
    "Más precisamente,\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "h_0(x) & = h(x)\\\\\n",
    "h_{i+1}(x) & = (h_i(x)+s(x)) \\bmod m\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Si $s(x)$ fuera mayor que 1 y divisor de $m$, la secuencia se repetiría después de $m/s(x)$ pasos, sin haber visitado todos los casilleros de la tabla. Para evitar esto, se debe escoger $m$ como un número **primo**.\n",
    "\n",
    "El análisis exacto de la eficiencia de este método es muy complicado, pero se obtienen buenos resultados usando modelos idealizados, ya sea suponiendo que la tabla se recorre usando muestreo sin reemplazo (llamado *uniform probing*) o muestreo con reemplazo (llamado *random probing*). Bajo estos modelos, se obtiene que los costos esperados de búsqueda para una tabla $\\alpha$-llena son:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C'_n & \\approx \\frac{1}{1-\\alpha} \\\\\n",
    "C_n & \\approx \\frac{1}{\\alpha}\\ln{\\frac{1}{1-\\alpha}}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Para una tabla llena, tenemos:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C'_{m-1} & = \\Theta(m) \\\\\n",
    "C_m & = \\Theta(\\log{m})\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "La siguiente tabla muestra que este método se desempeña mejor que Linear Probing desde el punto de vista del número esperado de comparaciones:\n",
    "\n",
    "$\\alpha$ | $C_n$ | $C'_n$\n",
    "--------|--------|-------\n",
    "0.6 | 1.53 | 2.50\n",
    "0.7 | 1.72 | 3.33\n",
    "0.8 | 2.01 | 5.00\n",
    "0.9 | 2.56 | 10.00\n",
    "0.99 | 4.65 | 100.00\n",
    "0.999 | 6.91 | 1000.00\n",
    "\n",
    "El peor caso de Hashing Doble es muy malo, pero incluso más improbable que el de Linear Probing. Se da cuando todas las llaves colisionan en un solo casillero y además todas tienen el mismo valor de $s(x)$, en cuyo caso la estructura degenera a una simple búsqueda secuencial, con costos de búsqueda $\\Theta(n)$.\n",
    "\n",
    "Respecto de las eliminaciones, la única posibilidad es marcar el elemento como \"eliminado\", con lo cual se considera ocupado para efecto de las búsquedas, pero libre para efectos de una inserción. Esto funciona, pero estos elementos contaminan la tabla y hacen que las búsquedas sean más lentas incluso cuando el factor de carga efectivo es bajo.\n",
    "\n",
    "Cuando dos llaves colisionan, el método de inserción le da preferencia a la que llegó primero (a este método se le llama también *First-Come-First-Served*, o *FCFS*), pero en realidad cualquiera de las dos llaves podría ocupar el casillero en disputa, y la otra tendría que buscar en otro lugar.\n",
    "\n",
    "A partir de esta observación, existen heurísticas para resolver el problema de las colisiones en hashing con direccionamiento abierto, como por ejemplo *Last-Come-First-Served* o *LCFS* hashing (el elemento que se mueve de casillero no es el que se inserta sino el que ya lo ocupaba) y *Robin Hood* hashing (el elemento que se queda en el casillero es aquel que se encuentre más lejos de su posición original), que si no cambian el promedio del costo de búsqueda con respecto al método original *FCFS*, sí disminuyen dramáticamente su varianza."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}