notas/arbol/arboles.md (25805B)
1 # Arboles 2 3 Algoritmos y Estructuras de Datos (CB100) - FIUBA 4 Martin Klöckner - [mklockner@fi.uba.ar](mailto:mklockner@fi.uba.ar) 5 6 \vspace{-1.25em} 7 \rule{\linewidth}{0.5pt} 8 \vspace{-1.25em} 9 10 Un árbol es una estructura de datos que posee ramificaciones pero no sigue con 11 una estructura lineal, como las listas enlazadas por ejemplo (salvo en casos 12 particulares) en esta estructura es posible poseer mas de una posición 13 siguiente, aunque típicamente se tienen dos (arboles binarios). Un árbol 14 obligatoriamente debe cumplir que cada nodo tenga un solo padre. 15 16 Dentro de la estructura se asigna diferentes nombres a los nodos con diferentes 17 características, como la **raíz**, el cual es el nodo que no tiene 18 "ancestros" y la **hoja** que es un nodo que no tiene hijos. Otras definiciones 19 incluyen el **grado** que es el numero de hijos máximo que puede tener un 20 subárbol o nodo, y la **altura** de un nodo que es la longitud del camino más 21 largo desde el nodo a la raíz (por convención la raíz tiene altura 1). 22 23 En la figura 1.1 se muestra un ejemplo de un árbol binario, en el cual la raíz 24 es el nodo A, las hojas los nodos D, E, F y G, el grado 2 (ya que es binario) y 25 la altura 3. 26 27 \begin{figure}[H] 28 \centering 29 \begin{subfigure}[t]{0.45\linewidth} 30 \centering 31 \includegraphics[width=\linewidth]{img/bin/binario_letras.png} 32 \caption{Árbol binaria} 33 \end{subfigure} 34 \hspace*{1mm} 35 \begin{subfigure}[t]{0.45\linewidth} 36 \centering 37 \includegraphics[width=\linewidth]{img/bin/binario_de_busqueda.png} 38 \caption{Árbol binario de búsqueda} 39 \end{subfigure} 40 \vspace{0.5em} 41 \caption{Ejemplos de arboles binarios} 42 \end{figure} 43 44 En la figura 2 se ve un ejemplo de la estructura típica de un árbol binario de 45 altura 2 junto con el contenido de los nodos, cada nodo tiene un dato asociado 46 que almacena y a su vez una referencia al nodo izquierdo y derecho que le 47 preceden. 48 49 \begin{figure}[H] 50 \centering 51 \begin{subfigure}[t]{0.55\linewidth} 52 \centering 53 \includegraphics[width=\linewidth]{img/bin/nodo_arbol_busqueda_binario.png} 54 \label{fig:ej-abb} 55 \end{subfigure} 56 \vspace{-1em} 57 \caption{Estructura de nodo de un árbol binario} 58 \label{fig:ej-arboles} 59 \end{figure} 60 61 Para insertar o eliminar un elemento no hay un orden particular y depende la 62 implementación, lo general es **insertar** elementos en las hojas, creando un 63 nuevo nodo, y para **eliminar** un elemento, en el peor caso caso (cuando un 64 nodo tiene dos hijos) insertar en el espacio el ultimo nodo insertado (nodo 65 hoja). 66 67 ## Arboles de búsqueda binaria 68 69 Un árbol de búsqueda binaria o ABB por sus siglas, es un árbol binario, es decir 70 que tiene un máximo de dos hijos por cada nodo, pero que además está ordenado, 71 esto es, el nodo izquierdo contiene un dato menor en comparación con el nodo 72 actual, y el nodo derecho un dato mayor. Un ejemplo de un árbol de búsqueda 73 binaria se puede ver en la figura 1.2. 74 75 Tener un árbol binario ordenado permite reducir el numero de pasos requeridos 76 para encontrar un dato almacenado en el árbol. Los ABB deben cumplir que el dato 77 de la raíz sea mayor al dato de todos los valores almacenados en los nodos hijos 78 del lado izquierdo y menor a todos los datos almacenados en los hijos del lado 79 derecho. En el mejor de los casos la altura de un ABB es $log(n)$ y en el peor 80 de los casos la altura es $n$, esto ultimo en este tipo de arboles ABB determina 81 el tiempo mínimo y máximo para acceder a un nodo[^1] (el peor de los casos que es 82 cuando el dato esta en una hoja). 83 84 [^1]: Abdul Bari. (2018, Marzo 16). 10.1 AVL Tree - Insertion and Rotations. 85 [https://www.youtube.com/watch?v=jDM6_TnYIqE&t=239s](https://www.youtube.com/watch?v=jDM6_TnYIqE&t=239s). 86 87 Cuando se **inserta** o **elimina** un elemento en el árbol se lo hace siguiendo 88 un orden. El caso en que el nodo a eliminar tiene uno o ningún hijo es trivial, 89 cuando el nodo tiene dos hijos, se debe reemplazar el nodo eliminado por el 90 sucesor inorden, esto es, el nodo que se debería visitar si se acabara de 91 visitar el nodo eliminado (con recorrido inorden) esto resulta en el nodo más a 92 la izquierda del subárbol derecho del nodo eliminado, otras implementaciones 93 utilizan el predecesor inorden, lo que resulta en el nodo mas a la derecha del 94 subárbol izquierdo. 95 96 ### Maneras de recorrer un árbol binario 97 98 Existen varias formas de recorrer un árbol binario siendo las más típicas 99 Depth-First Search (DFS o recorrido en profundidad) y Breath-First Search (BFS o 100 recorrido en anchura). En la primera (recorrido en profundidad) se puede 101 realizar en preorden, inorden o postorden; para la segunda se 102 recorren los nodos por niveles. 103 104 Para el método en profundidad, en el recorrido en preorden, primero se accede a 105 la raíz, luego al nodo izquierdo y luego al derecho, si alguno de los nodos es 106 un subárbol entonces se realiza el mismo procedimiento. Para el recorrido 107 inorden, primero se accede al nodo izquierdo, luego a la raíz, y por ultimo al 108 nodo derecho, este recorrido típicamente se usa en arboles de búsqueda binaria 109 (ABB). Por ultimo en el recorrido postorden, primero se accede a ambos nodos, 110 izquierdo y derecho, y luego a la raíz. 111 112 Para el método en anchura, se recorre el nodo en orden por niveles de arriba 113 hacia abajo y de izquierda a derecha, primero la raíz, luego todos los nodos, 114 luego los nodos de los nodos, etc. 115 116 Por ejemplo, en el árbol de la figura 1.1, el recorrido utilizando los 4 métodos 117 mencionados resultan como se ve en la tabla 1. 118 119 \begin{table}[H] 120 \renewcommand{\arraystretch}{1.2} % Espaciado entre filas 121 \noindent\begin{minipage}{\columnwidth} 122 \centering 123 \begin{tabular}{|p{3cm}|l|} 124 \hline 125 \textbf{Recorrido} & \textbf{Nodos} \\ 126 \hline 127 Preorden & $A-B-D-E-C-F-G$ \\ 128 \hline 129 Inorden & $D-B-E-A-C-F-G$ \\ 130 \hline 131 Postorden & $D-E-B-F-G-C-A$ \\ 132 \hline 133 Nivel por nivel & $A-B-C-D-E-F-G$ \\ 134 \hline 135 \end{tabular} 136 \caption{Recorridos de un árbol binario} 137 \end{minipage} 138 \end{table} 139 140 ### Características de los arboles 141 142 #### Árbol lleno 143 144 Se dice que un árbol esta lleno si todas las hojas tienen el mismo nivel y 145 todos los nodos anteriores tienen el número máximo de hijos (en un árbol binario 146 2) los arboles de la figura 1 están llenos, si en alguno de los dos faltase 147 alguna hoja, no lo estarían. 148 149 #### Árbol completo 150 151 Se dice que un árbol esta completo, si todas sus hojas están llenas excepto el 152 ultimo nivel, que debe estar casi-completo de izquierda a derecha, es decir, 153 puede haber hojas vacías pero deben estar lo más a la derecha posible y solo en 154 el ultimo nivel. En la figura 1 ambos arboles están completos. A un árbol 155 incompleto también se le dice **desequilibrado**. 156 157 #### Árbol degenerado o patológico 158 159 Un árbol degenerado (también llamado árbol patológico) es un tipo especial de 160 árbol en el que cada nodo tiene a lo sumo un hijo. Es decir, se comporta como 161 una lista enlazada en lugar de un árbol ramificado. Esto ocurre por ejemplo al 162 insertar datos ordenados en un árbol de búsqueda binaria 163 164 #### Árbol balanceado 165 166 Un árbol se dice balanceado si para cada nodo la diferencia de alturas entre el 167 subárbol izquierdo y derecho (el factor de equilibrio) es pequeña, típicamente 168 se toma menor o igual a $1$ en valor absoluto. 169 170 #### Factor de equilibrio 171 172 El factor de equilibrio se define para cada nodo como la diferencia entre las 173 alturas del subárbol derecho e izquierdo, como se muestra a continuación: 174 175 $$\boxed{F_{equilibrio} = h_{derecho} - h_{izquierdo}}$$ 176 177 El reciproco, es decir, la diferencia de alturas del subárbol izquierdo y 178 derecho de un nodo también vale, pero se debe respetar la convención elegida 179 para todo el árbol, o tomar el valor absoluto. 180 181 ### Árbol AVL (Adelson-Velski y Landis) 182 183 Un árbol AVL, es una caso particular de un árbol de búsqueda binaria en el que 184 cada vez que se inserta o elimina un nuevo elemento se lo hace de manera que el 185 árbol resulte balanceado, esta es una mejora a los ABB ya que si se insertan los 186 datos ordenados en el árbol ABB se degenera. Para que el árbol AVL resulte 187 balanceado al insertar o eliminar un elemento se comprueba si el árbol resulta 188 balanceado mediante el calculo del factor de equilibrio para cada nodo, en caso 189 de que el factor de equilibrio no pertenezca a $[-1, 0, 1]$, se lo 190 balancea. 191 192 Si bien los arboles AVL son mucho más eficientes que los arboles ABB, tienen la 193 particularidad de que por cada nivel pueden tener una mínima cantidad de nodos 194 (en el peor de los casos) que no es la máxima, y en particular se verifica que 195 para un árbol AVL de altura $h$ (o $h$ niveles) la cantidad mínima de nodos es 196 $F(n)$, siendo $F$ la serie de Fibonacci de $n$ términos, es por esto que 197 también a los arboles AVL se los conoce como **arboles de Fibonacci**. 198 199 #### Algoritmos de rotación 200 201 Las rotaciones se realizan para balancear arboles AVL. El punto clave es 202 entender que las rotaciones se aplican solo a 3 nodos y modifican los nodos 203 hijos. Se determina que un nodo debe ser balanceado calculando el factor de 204 equilibrio de cada nodo, el primer nodo de abajo hacia arriba que esta 205 desbalanceado debe ser balanceado. 206 207 ##### Rotación simple a derecha (o LL[^2]) 208 209 [^2]: LL (por left-left en ingles) es porque el que causa el desbalanceo del 210 nodo esta en el hijo izquierdo del hijo izquierdo. 211 212 En las rotaciones simples a derecha sobre un nodo, se rota ese nodo a su hijo 213 izquierdo y en su lugar se toma el hijo derecho del nodo previo; en el lugar del 214 nodo previo "asciende" su hijo derecho. En la figura 3.1 se muestra un árbol 215 desbalanceado, cuyo primer nodo desbalanceado de abajo hacia arriba es A, ya que 216 tiene un factor de equilibrio $-2$ lo cual en valor absoluto es mayor estricto 217 que $1$, en la figura 3.2 se muestra el resultado luego de realizar una rotación 218 simple a derecha sobre el nodo A. 219 220 \begin{figure}[H] 221 \centering 222 \hspace*{1mm} 223 \begin{subfigure}[t]{0.45\linewidth} 224 \centering 225 \includegraphics[width=\linewidth]{img/bin/arbol_avl_desbalanceado_rsd.png} 226 \caption{Arbol desbalanceado} 227 \end{subfigure} 228 \hspace*{1mm} 229 \begin{subfigure}[t]{0.45\linewidth} 230 \centering 231 \raisebox{5mm}{\includegraphics[width=\linewidth]{img/bin/arbol_avl_rsd.png}} 232 \caption{Luego de RSD} 233 \end{subfigure} 234 \hspace*{0.05\linewidth} 235 \caption{Rotación simple a derecha} 236 \label{fig:ej-arboles} 237 \end{figure} 238 239 240 ##### Rotación simple a izquierda (o RR) 241 242 Las rotaciones simples a izquierda son análogas a las rotaciones simples a 243 derecho pero en sentido contrario, en la figura 4.1 se muestra un ejemplo de una 244 árbol desbalanceado y en la figura 4.2 se muestra el mismo árbol luego de 245 realizar una rotación simple a derecha en al nodo A. 246 247 \begin{figure}[H] 248 \centering 249 \hspace*{1mm} 250 \begin{subfigure}[t]{0.45\linewidth} 251 \centering 252 \includegraphics[width=\linewidth]{img/bin/arbol_avl_desbalanceado_rsi.png} 253 \caption{Arbol desbalanceado} 254 \end{subfigure} 255 \hspace*{1mm} 256 \begin{subfigure}[t]{0.45\linewidth} 257 \centering 258 \raisebox{5mm}{\includegraphics[width=\linewidth]{img/bin/arbol_avl_rsi.png}} 259 \caption{Luego de RSI} 260 \end{subfigure} 261 \hspace*{0.05\linewidth} 262 \caption{Rotación simple a izquierda} 263 \label{fig:ej-arboles} 264 \end{figure} 265 266 ##### Rotación doble derecha (derecha-izquierda, RL) 267 268 En las rotaciones dobles a derecha se deben realizar dos rotaciones simples, 269 en primer lugar a derecha y por ultimo a izquierda. En la figura 5.1 se muestra 270 un árbol desbalanceado, para balancearlo en primer lugar se realiza una rotación 271 simple a derecha sobre el nodo B, resultando como en la figura 5.2. 272 273 \begin{figure}[H] 274 \centering 275 \hspace*{5mm} 276 \begin{subfigure}[t]{0.38\linewidth} 277 \centering 278 \includegraphics[width=\linewidth]{img/bin/arbol_avl_desbalanceado_rdd.png} 279 \caption{Arbol desbalanceado} 280 \end{subfigure} 281 \hspace*{1mm} 282 \begin{subfigure}[t]{0.48\linewidth} 283 \centering 284 \raisebox{2mm}{\includegraphics[width=\linewidth]{img/bin/arbol_avl_desbalanceado_rdd_primer_rot.png}} 285 \caption{Luego de RSD sobre B} 286 \end{subfigure} 287 \hspace*{0.05\linewidth} 288 \caption{Rotación doble a derecha} 289 \label{fig:ej-arboles} 290 \end{figure} 291 292 Luego de la primer rotación se obtiene un nuevo árbol desbalanceado, pero que se 293 balancea fácilmente mediante una rotación simple. 294 <!-- , en este caso una rotación simple a izquierda sobre el nodo A. --> 295 296 ##### Rotación doble izquierda (izquierda-derecha, LR) 297 298 Estas rotaciones son similares a las dobles a derecha pero las rotaciones 299 ocurren en sentido opuesto, la primera a izquierda y la segundo a derecha. 300 301 \begin{figure}[H] 302 \centering 303 \hspace*{5mm} 304 \begin{subfigure}[t]{0.38\linewidth} 305 \centering 306 \includegraphics[width=\linewidth]{img/bin/arbol_avl_desbalanceado_rdi.png} 307 \caption{Arbol desbalanceado} 308 \end{subfigure} 309 \hspace*{1mm} 310 \begin{subfigure}[t]{0.48\linewidth} 311 \centering 312 \raisebox{2mm}{\includegraphics[width=\linewidth]{img/bin/arbol_avl_desbalanceado_rdi_primer_rot.png}} 313 \caption{Luego de RSI sobre B} 314 \end{subfigure} 315 \hspace*{0.05\linewidth} 316 \caption{Rotación doble a izquierda} 317 \label{fig:ej-arboles} 318 \end{figure} 319 320 ## Árbol B 321 322 Los arboles B surgen como una forma de hacer más eficiente la lectura y 323 escritura en disco de datos, en particular de decrementar el tiempo y la 324 cantidad de bloques leídos de un disco a la hora de buscar un dato. 325 326 Lo particular de los arboles B en comparación a los arboles binarios vistos 327 anteriormente es que tienen un numero mayor de datos almacenados y un numero 328 mayor de hijos, pero se sigue la convención de los arboles de búsqueda binaria 329 en que los datos a la izquierda son menores y a la derecha mayores, tanto en los 330 nodos como en las claves. Esto se ve en la estructura de los nodos, un ejemplo 331 se muestra en la figura \ref{fig:estructura-nodo-arbol-b}, en el cual se ve una 332 estructura de un árbol B de orden 3. 333 334 \begin{figure}[H] 335 \centering 336 \includegraphics[width=\linewidth]{img/bin/nodo_arbol_b.png} 337 \caption{Estructura de un árbol B} 338 \label{fig:estructura-nodo-arbol-b} 339 \end{figure} 340 341 El **orden** de un árbol B (se denota con la letra `m`) determina la cantidad 342 máxima de hijos que pueden tener los nodos (y por consiguiente la cantidad 343 máxima de claves, ya que es $m-1$). Por ejemplo, en el árbol de la figura 344 \ref{fig:estructura-nodo-arbol-b}, el orden del árbol es 3, por lo que cada nodo 345 puede tener un máximo de 3 hijos, y almacenar 2 claves. 346 347 Por definición, en los arboles B se deben cumplir las siguientes reglas: 348 349 1. Todos los nodos, salvo la raíz, deben tener al menos $m/2$ hijos o 350 $(m/2) - 1$ claves. 351 3. Todas las hojas están en el mismo nivel. 352 4. El proceso de creación es de abajo hacia arriba. 353 354 ### Operaciones 355 356 Los arboles B tienen las mismas operaciones que los arboles binarios y aparte la 357 operación de dividir y fusionar (las cuales son operaciones de balanceo). Al 358 igual que los arboles AVL, al momento de insertar y eliminar datos del árbol 359 ocurre un proceso de balanceo, pero en este caso siendo la operación más 360 sencilla, ya que se trata de un procedimiento de un solo paso. 361 362 #### Búsqueda 363 364 La búsqueda es similar al árbol binario ya que las claves están ordenadas en 365 cada nodo $k1 < k2 < ... < kn$, en caso de que el dato a buscar este entre el 366 rango de dos claves, por ejemplo el dato a buscar $k$, cumple $k2 < k < k3$, 367 entonces se debe buscaren en el hijo entre $k2$ y $k3$, luego se realiza el 368 mismo procedimiento hasta llegar a las hojas. 369 370 #### Inserción 371 372 Para agregar un elemento, de manera análoga a arboles binarios, se busca la 373 posición mediante comparación con las claves hasta llegar a la hoja, en caso de 374 que haya lugar en la hoja simplemente se agrega, si no hay lugar se tiene que 375 dividir la hoja y promover el elemento $((m - 1)/2) + 1$ a un nivel superior, de 376 manera que en la nueva hoja queden el número mínimo de elementos. En caso de que 377 no haya más lugar en el nodo superior donde se promueve el elemento se realiza 378 el mismo procedimiento. 379 380 #### Eliminación 381 382 Cuando se elimina un elemento, a diferencia de cuando se inserta, puede ocurrir 383 en cualquier nodo, sea el nodo raíz, un nodo interno o un nodo hoja. Si el nodo 384 del cual se quiere eliminar el elemento es una hoja, y al eliminar el elemento 385 el número de claves sigue siendo mayor a la mínima, entonces el proceso de 386 eliminación se detiene allí. Si el número es menor al número mínimo de elementos 387 por nodo entonces se pide "prestado" al hermano izquierdo o derecho (dependiendo 388 la implementación del algoritmo) en caso de que ninguno de los dos tenga o que 389 tengan el número mínimo de elementos, se pide al de un nivel superior, en caso 390 de que ocurra lo mismo con el del nivel superior, que no tiene elementos para 391 prestar, entones se pide al de un nivel superior, y así sucesivamente hasta la 392 raíz, si la raíz tiene un solo elemento entonces se baja un nivel del árbol. 393 394 ## Árbol B+ 395 396 Los arboles B+ son muy similares a los arboles B pero con la condición que los 397 datos deben estar en las hojas, para esto se hace que las raíces sean 398 referencias al dato verdadero que se encuentra en la hojas. Además se impone la 399 condición de que todas las hojas deben estar conectadas, de esta forma todas las 400 hojas formen una especie de lista enlazada, y como todos los datos se almacenan 401 en las hojas, esta lista enlazada dispone de todos los datos almacenados en el 402 árbol, esto permite recorrer secuencialmente todos los nodos, lo cual es una 403 mejora con respecto a los arboles B, ya que se deben recorrerse recursivamente, 404 nodo por nodo. 405 406 En la figura \ref{fig:estructura-nodo-arbol-b+} se muestra un ejemplo de una 407 estructura de un árbol B+, se puede ver la conexión entre las hojas y las copia 408 de los nodos intermedios ($k1$ y $k2$). 409 410 \begin{figure}[H] 411 \centering 412 \includegraphics[width=\linewidth]{img/bin/nodo_arbol_b+.png} 413 \caption{Estructura de un árbol B+} 414 \label{fig:estructura-nodo-arbol-b+} 415 \end{figure} 416 417 ### Operaciones 418 419 Las operaciones en general son similares a los arboles B, pero con algunas 420 particularidades. 421 422 #### Búsqueda 423 424 En el caso de la búsqueda en un árbol B+, es similar a la búsqueda del árbol B, 425 pero no se debe detener cuando se encuentre la clave en la pagina raíz o en un 426 pagina interior, si no que se debe seguir por la rama derecha apuntada por esa 427 clave, ya que la clave apuntada en primera instancia era una copia de la clave 428 real almacenada en la hoja. 429 430 #### Inserción 431 432 El proceso de inserción en un árbol B+ es muy similar al de un árbol B, pero se 433 diferencia en que cuando se inserta una nueva clave en un nodo lleno, esta se 434 divide en dos, con la primera teniendo el número mínimo de claves y la segundo 435 el número mínimo de claves sumada la nueva clave, el elemento que promociona a 436 un nuevo nivel es una copia de la clave central. 437 438 #### Eliminación 439 440 En el caso de eliminar un elemento una vez encontrado, se elimina directamente 441 de la hoja (todos los datos están en las hojas), si luego de eliminarlo la hoja 442 queda con menos del mínimo de elementos por hoja ($m/2$) entonces hay que 443 eliminar la hoja y redistribuir los elementos con las hojas hermanas, la clave 444 copia en el nodo padre se debe eliminar también, si el nodo padre también queda 445 con menos del mínimo de claves por hoja, entonces hay que realizar el mismo 446 procedimiento. 447 448 ## Árbol heap 449 450 Los arboles heap son arboles con la particularidad de que se busca que siempre 451 estén completos o casi completos y parcialmente ordenados, esto se hace 452 insertando los elementos de izquierda a derecha por niveles, es por esto que 453 también se le dicen casi-completos ya que los subárboles de las hojas se van 454 completando a medida que ingresan los elementos 455 456 Los arboles heap, tienen un orden diferente al de los arboles binarios, se 457 ordenan por nivel. En los arboles heap de máximo la raíz es siempre mayor a los 458 hijos, y entre hijos (o hermanos) no hay una relación particular como si pasa en 459 los arboles binarios, en los cuales el izquierdo es siempre menor al hijo 460 derecho, además, existen también los arboles heap de mínimo, en los cuales la 461 raíz es siempre menor a los hijos. 462 463 En la figura 9 se ven dos ejemplos de arboles heap, en la figura 9.1, se ve un 464 árbol heap de máximo, mientras que en la figura 9.2 se ve un árbol heap de 465 mínimo. 466 467 \begin{figure}[H] 468 \centering 469 \begin{subfigure}[t]{0.45\linewidth} 470 \includegraphics[width=\linewidth]{img/bin/arbol_heap_max.png} 471 \caption{Árbol heap de máximo} 472 \end{subfigure} 473 \hspace*{1mm} 474 \begin{subfigure}[t]{0.45\linewidth} 475 \includegraphics[width=\linewidth]{img/bin/arbol_heap_min.png} 476 \caption{Árbol heap de mínimo} 477 \end{subfigure} 478 \vspace{0.5em} 479 \caption{Tipos de árbol heap} 480 \end{figure} 481 482 Los arboles heap típicamente se almacenan en vectores, almacenando los valores 483 por nivel, contanto $k$ desde $0$, para un padre en posición $k$ sus hijos se 484 almacenan en la posición $(2*k)+1$ y $(2*k)+2$ del vector para el hijo 485 izquierdo y derecho respectivamente, análogamente, si el hijo esta en la 486 posición $h$ del vector, el padre estará en la posición $floor((h-1)/2)$. 487 Almacenando los arboles en vectores permite acceder a los datos de forma 488 directa. En la figura 10 se muestra como se almacena el árbol heap de máximo de 489 la figura 9.1, como particularidad se ve que el primer elemento es la raíz, lo 490 cual es el elemento más grande por ser heap de máximo, si fuera de mínimo este 491 sería el menor elemento. 492 493 \begin{figure}[H] 494 \centering 495 \includegraphics[width=0.5\linewidth]{img/bin/arbol_heap_vector.png} 496 \caption{Árbol heap almacenado en vector} 497 \end{figure} 498 499 Para **insertar** elementos en un árbol heap se agrega siempre en la primer hoja 500 vacía de izquierda a derecha en el ultimo nivel del árbol, una vez insertado el 501 elemento se compara e intercambia con el padre hasta cumplir con la definición 502 de árbol heap (que la raíz sea mayor o menor a los hijos, es decir que los hijos 503 sean arboles heap de por sí). 504 505 Para **eliminar** elementos de un árbol heap típicamente se elimina la raíz, 506 para esto en primer lugar se intercambia con la ultimo hoja (ultimo nivel, 507 ultima hoja contando de izquierda a derecha) y luego se compara la nueva raíz 508 con los hijos intercambiando en cada caso con el mayor (o menor) hasta que el 509 árbol vuelva a ser un heap, por ultimo se elimina el dato a eliminar, es decir 510 la ultima hoja, o en caso de estar almacenado en un vector se decrementa la 511 longitud de este. 512 513 Como los arboles heap se completan por niveles, la altura del árbol es $log(n)$, 514 siendo $n$ la cantidad de nodos en el árbol, esto es una mejora contra los 515 arboles AVL que tienen una altura $Fib(n)$. 516 517 ## Algoritmo heapify 518 519 Heapify es un algoritmo utilizado para ordenar un árbol heap si la raíz del 520 árbol viola la propiedad principal de un árbol heap (que sea mínimo o máximo a 521 todos los hijos, dependiendo el tipo de heap, y que a su vez cada subárbol sea 522 un árbol heap de por sí). 523 524 El algoritmo también se utiliza para convertir un árbol binario en un árbol 525 heap, para esto se comienza en las hojas y se verifica que todos los subárboles 526 cumplan que sean heaps, en caso de no serlo intercambia los valores hacia abajo 527 hasta que se cumpla la condición de heap, estos pasos se repiten sucesivamente 528 con todos los nodos hasta llegar a la raíz. En este caso el algoritmo tiene una 529 complejidad de $\mathcal{O}(n)$ 530 531 A continuación se muestra una posible implementación recursiva del algoritmo 532 heapify para un árbol heap de máximo almacenado en un vector, en este caso 533 denominado `arr`, el lenguaje utilizado es python 534 535 ```python 536 def heapify(arr, n, i): 537 # Se asume que la raiz es maxima 538 max = i 539 540 # posicion de hijo izquierdo y derecho 541 left = (2*i) + 1 542 right = (2*i) + 2 543 544 # se comprueba si hay hijo izquierdo y es 545 # mayor a la raiz 546 if left < n and arr[left] > arr[max]: 547 max = left 548 549 # se comprueba si hay hijo derecho y es 550 # mayor a la raiz o al hijo izquierdo 551 if right < n and arr[right] > arr[max]: 552 max = right 553 554 # si la raiz no es maxima se intercambia 555 # con el maximo hijo, y se llama 556 # recursivamente a heapify para reordenar 557 # los hijos restantes 558 if max != i: 559 arr[i], arr[max] = arr[max], arr[i] 560 heapify(arr, n, max) 561 ``` 562 563 ## Heapsort 564 565 El algoritmo de ordenamiento heapsort es un algoritmo que se basa en el 566 algoritmo heapify, ya que para ordenar un vector, arma un árbol heap de máximo 567 (o mínimo según la implementación) e intercambia el valor de la raíz con el 568 ultimo valor del vector, decrementando la capacidad del vector en un elemento, 569 luego vuelve a armar un árbol heap con los elementos restantes e intercambia 570 nuevamente el ultimo elemento ahora con el ante-ultimo del vector, y 571 decrementando la cantidad de elementos en el vector, de esta forma al final del 572 vector se van colocando los valores máximos ordenados, el algoritmo sigue hasta 573 llegar al primer elemento del vector. 574 575 ## Colas con prioridad 576 577 Las colas con prioridad son una estructura de datos de tipo cola (o queue) pero 578 tienen la particularidad que al momento de insertar un elemento se puede asignar 579 una prioridad, de esta forma no se inserta siempre en un mismo lugar si no que 580 se puede insertar con un orden en particular dependiendo de la prioridad que se 581 asigne a el elemento a insertar. 582 583 Existen varias maneras de implementar una cola con prioridad, por ejemplo un 584 vector, una lista enlazada o un árbol heap. El caso de la implementación con 585 árbol heap es de las más eficientes, ya que en un árbol heap de máximo la raíz 586 es la que tiene el valor máximo, y se puede imponer que este número sea la 587 prioridad, de esta forma eliminar un elemento, es decir, desencolar el elemento 588 con mayor prioridad es eliminar la raíz del árbol.