commit c5e0c38d27ac8f24c1754034cce95164b4d8be79 parent 391b9d09f0f3662d0afda1cc713bc14da5f47d03 Author: Martin Kloeckner <mjkloeckner@gmail.com> Date: Thu, 17 Jul 2025 01:31:03 -0300 twocolumn view + completed missing data *heap section still incomplete Diffstat:
35 files changed, 909 insertions(+), 349 deletions(-) diff --git a/notas/arbol/arboles.md b/notas/arbol/arboles.md @@ -16,70 +16,60 @@ obligatoriamente debe cumplir que cada nodo tenga un solo padre. Dentro de la estructura se asigna diferentes nombres a los nodos con diferentes características, como la **raíz**, el cual es el nodo que no tiene "ancestros" y la **hoja** que es un nodo que no tiene hijos. Otras definiciones -incluyen el **grado** que es el numero de hijos que tiene un subárbol o nodo, y -la **altura** de un nodo que es la longitud del camino mas largo desde el nodo a -la raíz (por convención la raíz tiene altura 1). - -En la figura 1 se muestra varios ejemplos de arboles. Tomando como ejemplo el -árbol binario de la figura 1.3, la raíz es el nodo A, las hojas los nodos D, E, -F y G, el grado de la raíz 2 y la altura 3. - -{ width=28% } -\hspace{3em} -{ width=28% } -\hspace{3em} -{ width=28% } - -\vspace{-1em} -\begin{figure}[!h] -\begin{subfigure}[t]{0.3\textwidth} -\caption{Árbol binario} -\end{subfigure} -\hspace{2em} -\begin{subfigure}[t]{0.3\textwidth} -\caption{Árbol de búsqueda binario} -\end{subfigure} -\hspace{2em} -\begin{subfigure}[t]{0.3\textwidth} -\caption{Otro ejemplo de árbol binario} -\end{subfigure} -\vspace{-0.30em} -\caption{Ejemplos de arboles binarios} +incluyen el **grado** que es el numero de hijos máximo que puede tener un +subárbol o nodo, y la **altura** de un nodo que es la longitud del camino mas +largo desde el nodo a la raíz (por convención la raíz tiene altura 1). + +En la figura 1 se muestran 2 ejemplos de arboles binarios. Tomando como ejemplo +el árbol binario de la figura 1.1, la raíz es el nodo A, las hojas los nodos D, +E, F y G, el grado de la raíz 2 y la altura 3. + +\begin{figure}[H] + \centering + \hspace*{1mm} + \begin{subfigure}[t]{0.45\linewidth} + \centering + \includegraphics[width=\linewidth]{./img/binario_letras.png} + \caption{Árbol de búsqueda binaria} + \label{fig:ej-abb} + \end{subfigure} + \hspace*{1mm} + \begin{subfigure}[t]{0.40\linewidth} + \centering + \includegraphics[width=\linewidth]{./img/binario_incompleto.png} + \caption{Árbol binario} + \label{fig:-} + \label{fig:ej-arbol-binario} + \end{subfigure} + \hspace*{0.05\linewidth} + \caption{Ejemplos de arboles binarios} + \label{fig:ej-arboles} \end{figure} -\vspace{-0.50em} - -Un ejemplo de la implementación típica de un nodo de un árbol binario se puede -ver en la figura 2, en la cual cada nodo tiene un dato asociado que almacena y a -su vez una referencia al nodo izquierdo y derecho que le preceden. - -<!-- { width=40% } --> - -{ width=30% } -\hspace{1em} -{ width=65% } - -\vspace{-1em} -\begin{figure}[!h] -\begin{subfigure}[t]{0.3\textwidth} -\caption{Árbol binario} -\end{subfigure} -\hspace{3em} -\begin{subfigure}[t]{0.6\textwidth} -\caption{Árbol B, k* representa una clave o dato almacenado} -\end{subfigure} -\vspace{-0.30em} -\caption{Estructura de nodos de arboles} -\end{figure} -\vspace{-0.50em} +En la figura 2 se ve un ejemplo de la estructura típica de un árbol binario +junto con el contenido de los nodos, cada nodo tiene un dato asociado que +almacena y a su vez una referencia al nodo izquierdo y derecho que le preceden. + +\begin{figure}[H] + \centering + \begin{subfigure}[t]{0.55\linewidth} + \centering + \includegraphics[width=\linewidth]{./img/nodo_arbol_busqueda_binario.png} + \label{fig:ej-abb} + \end{subfigure} + \vspace{-1em} + \caption{Estructura de nodo de un árbol binario} + \label{fig:ej-arboles} +\end{figure} -## Arboles de búsqueda binario +## Arboles de búsqueda binaria -Un árbol de búsqueda binario o ABB por sus siglas, es un árbol binario, es decir +Un árbol de búsqueda binaria o ABB por sus siglas, es un árbol binario, es decir que tiene un máximo de dos hijos por cada nodo, pero que además está ordenado, esto es, el nodo izquierdo contiene un dato menor en comparación con el nodo -actual, y el nodo derecho un dato mayor en comparación. Un ejemplo de un árbol -de búsqueda binario se puede ver en la figura 1.2 +actual, y el nodo derecho un dato mayor. Un ejemplo de un árbol de búsqueda +binaria se puede ver en la figura 1.2, el árbol de la figura 1.1 también es un +árbol de búsqueda binaria si consideramos el orden alfabético. Tener un árbol binario ordenado permite reducir el numero de pasos requeridos para encontrar un dato almacenado en el árbol. Los ABB deben cumplir que el dato @@ -93,6 +83,24 @@ cuando el dato esta en una hoja). [^1]: Abdul Bari. (2018, Marzo 16). 10.1 AVL Tree - Insertion and Rotations. [https://www.youtube.com/watch?v=jDM6_TnYIqE&t=239s](https://www.youtube.com/watch?v=jDM6_TnYIqE&t=239s). +Cuando se inserta o elimina un elemento en el árbol se lo hace siguiendo un +orden. El caso en que el nodo a eliminar tiene uno o dos hijos es trivial, lo +particular es cuando el nodo tiene dos hijos, en ese caso se debe reemplazar el +nodo eliminado por el sucesor inorden, esto es el nodo que se debería visitar si +se acabara de visitar el nodo eliminado (con recorrido inorden) esto resulta en +el nodo mas a la izquierda del subárbol derecho del nodo eliminado. + +<!-- +La particularidad cuando se elimina un nodo es que también se lo hace en orden, +es decir, en el caso base en que el nodo a eliminar no tiene hijos, se elimina +directamente, si tiene un solo hijo se lo elimina y el hijo se coloca en la +ubicación del nodo eliminado, pero en el caso de que tenga dos hijos, se debe +reemplazar el nodo eliminado por el sucesor inorden, esto es el nodo que se +debería visitar si se acabara de visitar el nodo eliminado en la manera de +recorrer el árbol inorden, esto es el nodo mas a la izquierda del subárbol del +nodo eliminado. +--> + ### Maneras de recorrer un árbol binario Existen varias formas de recorrer un árbol binario siendo las mas típicas @@ -106,45 +114,79 @@ primero se accede a la raíz, luego al nodo izquierdo y luego al derecho, si alguno de los nodos es un subárbol entonces se realiza el mismo procedimiento. Para el recorrido inorden, primero se accede al nodo izquierdo, luego a la raíz, y por ultimo al nodo derecho, este recorrido típicamente se usa en arboles de -búsqueda binarios (ABB). Por ultimo en el recorrido postorden, primero se accede +búsqueda binaria (ABB). Por ultimo en el recorrido postorden, primero se accede a ambos nodos, izquierdo y derecho, y luego a la raíz. Para la manera en anchura (Breath-First Search), se recorre el nodo en orden por -niveles de arriba hacia abajo y de izquierda a derecha, es decir, primero la -raíz, luego todos los nodos, luego los nodos de los nodos, y así sucesivamente. - -Por ejemplo, en el árbol de la figura 1.3, el recorrido utilizando los 4 métodos -mencionados resultan: - -* Preorden: A B D E C F G -* Inorden: D B E A C F G -* Postorden: D E B F G C A -* Nivel por nivel: A B C D E F G +niveles de arriba hacia abajo y de izquierda a derecha, primero la +raíz, luego todos los nodos, luego los nodos de los nodos, etc. + +Por ejemplo, en el árbol de la figura 1.1, el recorrido utilizando los 4 métodos +mencionados resultan como se ve en la tabla 1. + +<!-- +\begin{table}[H] +\centering +\renewcommand{\arraystretch}{1.05} +\begin{minipage}{\columnwidth} +\centering +\begin{tabular}{ll} +\textbf{Recorrido\hspace{5em}} & \textbf{Nodos} \\ +\hline \vspace{-0.75em} \\ +Preorden & A B D E C F G \\ +Inorden & D B E A C F G \\ +Postorden & D E B F G C A \\ +Nivel por nivel & A B C D E F G \\ +\end{tabular} +\caption{Recorridos de un árbol binario} +\end{minipage} +\end{table} +--> + +\begin{table}[H] +\renewcommand{\arraystretch}{1.2} % Espaciado entre filas +\noindent\begin{minipage}{\columnwidth} +\centering +\begin{tabular}{|p{3cm}|l|} +\hline +\textbf{Recorrido} & \textbf{Nodos} \\ +\hline +Preorden & $A-B-D-E-C-F-G$ \\ +\hline +Inorden & $D-B-E-A-C-F-G$ \\ +\hline +Postorden & $D-E-B-F-G-C-A$ \\ +\hline +Nivel por nivel & $A-B-C-D-E-F-G$ \\ +\hline +\end{tabular} +\caption{Recorridos de un árbol binario} +\end{minipage} +\end{table} ### Características de los arboles #### Árbol lleno -Se dice que un árbol esta lleno, si todas las hojas tienen el mismo nivel y +Se dice que un árbol esta lleno si todas las hojas tienen el mismo nivel y todos los nodos anteriores tienen el numero máximo de hijos (en un árbol binario -2), por ejemplo el árbol de la figura 1.3 está lleno, los arboles de las figuras -1.1 y 1.2 no están llenos ya que las hojas no tienen el mismo nivel (hay hojas -de nivel 2 y 3 en ambos casos). +2) el árbol de la figura 1.1 está lleno, pero el de la figura 1.2 no lo está ya +que las hojas no tienen el mismo nivel (hay hojas de nivel 2 y otras de 3). #### Árbol completo Se dice que un árbol esta completo, si todas sus hojas están llenas sin contar -contar el ultimo subárbol, es decir, puede haber alguno hoja vacía y además -todas las hojas están lo mas a la izquierda posible, es decir, las posibles -hojas vacías están a la derecha de la raíz del nodo, y se van completando de -izquierda a derecha. En los arboles de las figuras solo 1.3 cumple, para que 1.1 -y 1.2 cumplan deberían estar completos de izquierda a derecha y no ocurre. -A un árbol que no esta completa también se le dice desequilibrado. +el ultimo subárbol, es decir, puede haber alguno hoja vacía y además todas las +hojas están lo mas a la izquierda posible, es decir, las posibles hojas vacías +están a la derecha de la raíz del nodo, y se van completando de izquierda a +derecha. En la figura 1 ambos arboles están completos. A un árbol que no esta +completo también se le dice desequilibrado. #### Árbol balanceado -Un árbol se dice balanceado si para cada nodo la diferencia de alturas entra el -subárbol izquierdo y derecho es pequeña, típicamente menor a $\left|1\right|$ +Un árbol se dice balanceado si para cada nodo la diferencia de alturas entre el +subárbol izquierdo y derecho es pequeña, típicamente menor o igual a $1$ en +valor absoluto. #### Árbol degenerado o patológico @@ -164,55 +206,289 @@ $$\boxed{F_{equilibrio} = h_{derecho} - h_{izquierdo}}$$ ### Árbol AVL (Adelson-Velski y Landis) -Un árbol AVL, es una caso particular de un árbol de búsqueda binario en el que +Un árbol AVL, es una caso particular de un árbol de búsqueda binaria en el que cada vez que se inserta o elimina un nuevo elemento se lo hace de manera que el árbol resulte balanceado, esta es una mejora a los ABB ya que si se insertan los -datos ordenados el árbol se degenera. Para que el árbol resulte balanceado al -insertar o eliminar un elemento cada vez que se realiza dicha operación se -comprueba si el árbol resulta equilibrado, en caso de que no se lo balancea. +datos ordenados en el árbol ABB se degenera. Para que el árbol AVL resulte +balanceado al insertar o eliminar un elemento se comprueba si el árbol resulta +balanceado mediante el calculo del factor de equilibrio para cada nodo, en caso +de que el factor de equilibrio no pertenezca a $[-1, 0, 1]$, se lo +balancea. + +Si bien los arboles AVL son mucho mas eficientes que los arboles ABB, tienen la +particularidad de que por cada nivel pueden tener una mínima cantidad de nodos +(en el peor de los casos) que no es la máxima, y en particular se verifica que +para un árbol AVL de altura $h$ (o $h$ niveles) la cantidad mínima de nodos es +$F(n)$, siendo $F$ la serie de Fibonacci de $n$ términos, es por esto que +también a los arboles AVL se los conoce como **arboles de Fibonacci**. #### Algoritmos de rotación Las rotaciones se realizan para balancear arboles AVL. El punto clave es entender que las rotaciones se aplican solo a 3 nodos y modifican los nodos -hijos. +hijos. Se determina que un nodo debe ser balanceado calculando el factor de +equilibrio de cada nodo, el primer nodo de abajo hacia arriba que esta +desbalanceado debe ser balanceado. + +##### Rotación simple a derecha (o LL[^2]) + +[^2]: LL (por left-left en ingles) es porque el que causa el desbalanceo del + nodo esta en el hijo izquierdo del hijo izquierdo. + +En las rotaciones simples a derecha sobre un nodo, se rota ese nodo a su hijo +izquierdo y en su lugar se toma el hijo derecho del nodo previo; en el lugar del +nodo previo "asciende" su hijo derecho. En la figura 3.1 se muestra un árbol +desbalanceado, cuyo primer nodo desbalanceado de abajo hacia arriba es A, ya que +tiene un factor de equilibrio $-2$ lo cual en valor absoluto es mayor estricto +que $1$, en la figura 3.2 se muestra el resultado luego de realizar una rotación +simple a derecha sobre el nodo A. + +\begin{figure}[H] + \centering + \hspace*{1mm} + \begin{subfigure}[t]{0.45\linewidth} + \centering + \includegraphics[width=\linewidth]{./img/arbol_avl_desbalanceado_rsd.png} + \caption{Arbol desbalanceado} + \end{subfigure} + \hspace*{1mm} + \begin{subfigure}[t]{0.45\linewidth} + \centering + \raisebox{5mm}{\includegraphics[width=\linewidth]{./img/arbol_avl_rsd.png}} + \caption{Luego de RSD} + \end{subfigure} + \hspace*{0.05\linewidth} + \caption{Rotación simple a derecha} + \label{fig:ej-arboles} +\end{figure} -##### Rotación simple a derecha -##### Rotación simple a izquierda +##### Rotación simple a izquierda (o RR) + +Las rotaciones simples a izquierda son análogas a las rotaciones simples a +derecho pero en sentido contrario, en la figura 4.1 se muestra un ejemplo de una +árbol AVL desbalanceado, en la figura 4.2 se muestra el mismo árbol luego de +hacer una rotación simple a derecha con respecto al nodo B, para finalizar el +balanceo faltaría hacer una rotación simple a izquierda con respecto al nodo A. + +\begin{figure}[H] + \centering + \hspace*{1mm} + \begin{subfigure}[t]{0.45\linewidth} + \centering + \includegraphics[width=\linewidth]{./img/arbol_avl_desbalanceado_rsi.png} + \caption{Arbol desbalanceado} + \end{subfigure} + \hspace*{1mm} + \begin{subfigure}[t]{0.45\linewidth} + \centering + \raisebox{5mm}{\includegraphics[width=\linewidth]{./img/arbol_avl_rsi.png}} + \caption{Luego de RSI} + \end{subfigure} + \hspace*{0.05\linewidth} + \caption{Rotación simple a izquierda} + \label{fig:ej-arboles} +\end{figure} -##### Rotación doble a derecha +##### Rotación doble derecha (derecha-izquierda, RL) + +En las rotaciones dobles a derecha se deben realizar dos rotaciones simples, +en primer lugar a derecha y por ultimo a izquierda. En la figura 5.1 se muestra +un árbol desbalanceado, para balancearlo en primer lugar se realiza una rotación +simple a derecha sobre el nodo B, resultando como en la figura 5.2. + +\begin{figure}[H] + \centering + \hspace*{5mm} + \begin{subfigure}[t]{0.38\linewidth} + \centering + \includegraphics[width=\linewidth]{./img/arbol_avl_desbalanceado_rdd.png} + \caption{Arbol desbalanceado} + \end{subfigure} + \hspace*{1mm} + \begin{subfigure}[t]{0.48\linewidth} + \centering + \raisebox{2mm}{\includegraphics[width=\linewidth]{./img/arbol_avl_desbalanceado_rdd_primer_rot.png}} + \caption{Luego de RSD sobre B} + \end{subfigure} + \hspace*{0.05\linewidth} + \caption{Rotación doble a derecha} + \label{fig:ej-arboles} +\end{figure} -##### Rotación doble a izquierda +Luego de la primer rotación se obtiene un nuevo árbol desbalanceado, pero que se +puede balancear fácilmente mediante una rotación simple, en este caso una +rotación simple a izquierda sobre el nodo A. + +##### Rotación doble izquierda (izquierda-derecha, LR) + +Las rotaciones dobles a izquierda son similares a las dobles a derecha pero las +rotaciones ocurren en sentido opuesto, la primera a izquierda y la segundo a +derecha. + +\begin{figure}[H] + \centering + \hspace*{5mm} + \begin{subfigure}[t]{0.38\linewidth} + \centering + \includegraphics[width=\linewidth]{./img/arbol_avl_desbalanceado_rdi.png} + \caption{Arbol desbalanceado} + \end{subfigure} + \hspace*{1mm} + \begin{subfigure}[t]{0.48\linewidth} + \centering + \raisebox{2mm}{\includegraphics[width=\linewidth]{./img/arbol_avl_desbalanceado_rdi_primer_rot.png}} + \caption{Luego de RSI sobre B} + \end{subfigure} + \hspace*{0.05\linewidth} + \caption{Rotación doble a izquierda} + \label{fig:ej-arboles} +\end{figure} ## Árbol B Los arboles B surgen como una forma de hacer mas eficiente la lectura y escritura en disco de datos, en particular de decrementar el tiempo y la -cantidad de bloques leídos de un disco a la hora de buscar un dato> +cantidad de bloques leídos de un disco a la hora de buscar un dato. Lo particular de los arboles B en comparación a los arboles binarios vistos anteriormente es que tienen un numero mayor de datos almacenados y un numero -mayor de hijos, pero se sigue la convención de los arboles de búsqueda binarios +mayor de hijos, pero se sigue la convención de los arboles de búsqueda binaria en que los datos a la izquierda son menores y a la derecha mayores, tanto en los -nodos como en las claves. +nodos como en las claves. Esto se ve en la estructura de los nodos, un ejemplo +se muestra en la figura \ref{fig:estructura-nodo-arbol-b}, en el cual se ve una +estructura de un árbol B de orden 3. + +\begin{figure}[H] + \centering + \includegraphics[width=\linewidth]{./img/nodo_arbol_b.png} + \caption{Estructura de un árbol B} + \label{fig:estructura-nodo-arbol-b} +\end{figure} + +<!-- +El **grado** de un árbol B determina la cantidad máxima de hijos que puede tener +cada nodo de árbol. +--> + +El *orden* de un árbol B (se denota con la letra *m*) determina la cantidad +máxima de hijos que pueden tener los nodos (y por consiguiente la cantidad +máxima de claves, ya que es $m-1$). Por ejemplo, en el árbol de la figura +\ref{fig:estructura-nodo-arbol-b}, el orden del árbol es 3, por lo que cada nodo +puede tener un máximo de 3 hijos, y almacenar 2 claves. + +Por definición, en los arboles B se deben cumplir las siguientes reglas: + +1. Todos los nodos, salvo la raíz, deben tener al menos $((m/2)-1)$ + claves, o $m/2$ hijos (salvo hojas). +3. Todas las hojas están en el mismo nivel. +4. El proceso de creación es de abajo hacia arriba. + +### Operaciones Los arboles B tienen las mismas operaciones que los arboles binarios y aparte la -operación de dividir y fusionar. +operación de dividir y fusionar. Al igual que los arboles AVL, al momento de +insertar y eliminar datos del árbol ocurre un proceso de balanceo, pero en este +caso siendo la operación mas sencilla, ya que se trata de un procedimiento de un +solo paso. + +#### Búsqueda + +La búsqueda es similar al árbol binario ya que las claves están ordenadas en +cada nodo $k1 < k2 < ... < kn$, en caso de que el dato a buscar este entre el +rango de dos claves, por ejemplo el dato a buscar $k$, cumple $k2 < k < k3$, +entonces se debe buscaren en el hijo entre $k2$ y $k3$, luego se realiza el +mismo procedimiento hasta llegar a las hojas. + +#### Inserción + +Para agregar un elemento, de manera análoga a arboles binarios, se busca la +posición mediante comparación con las claves hasta llegar a la hoja, en caso de +que haya lugar en la hoja simplemente se agrega, si no hay lugar se tiene que +dividir la hoja y promover el elemento $((m - 1)/2) + 1$ a un nivel superior, de +manera que en la nueva hoja queden el numero mínimo de elementos. En caso de que +no haya mas lugar en el nodo superior donde se promueve el elemento se realiza +el mismo procedimiento. + +#### Eliminación + +Cuando se elimina un elemento, a diferencia de cuando se inserta, puede ocurrir +en cualquier nodo, sea el nodo raíz, un nodo interno o un nodo hoja. Si el nodo +del cual se quiere eliminar el elemento es una hoja, y al eliminar el elemento +el numero de claves sigue siendo mayor a la mínima, entonces el proceso de +eliminación se detiene allí. Si el numero es menor al numero mínimo de elementos +por nodo entonces se pide "prestado" al hermano izquierdo o derecho (dependiendo +la implementación del algoritmo) en caso de que ninguno de los dos tenga o que +tengan el numero mínimo de elementos, se pide al de un nivel superior, en caso +de que ocurra lo mismo con el del nivel superior, que no tiene elementos para +prestar, entones se pide al de un nivel superior, y así sucesivamente hasta la +raíz, si la raíz tiene un solo elemento entonces se baja un nivel del árbol. + +<!-- +#### División + +#### Fusión +--> ## Árbol B+ Los arboles B+ son muy similares a los arboles B pero con la condición que los -datos deben estar en las hojas, y por esto para mantener la estructura de árbol, -se copian los datos de las raíces a las hojas. Además se impone la condición de -que todas las hojas deben estar conectadas, de forma de que todas las hojas -formen una especie de lista enlazada. +datos deben estar en las hojas, para esto se hace que las raíces sean +referencias al dato verdadero que se encuentra en la hojas. Además se impone la +condición de que todas las hojas deben estar conectadas, de esta forma todas las +hojas formen una especie de lista enlazada, y como todos los datos se almacenan +en las hojas, esta lista enlazada dispone de todos los datos almacenados en el +árbol, esto permite recorrer secuencialmente todos los nodos del árbol, lo cual +es una mejora con respecto a los arboles B, ya que se deben recorrer +recursivamente, nodo por nodo. + +En la figura \ref{fig:estructura-nodo-arbol-b+} se muestra un ejemplo de una +estructura de un árbol B+, se puede ver la conexión entre las hojas y las copia +de los nodos intermedios ($k1$ y $k2$). + +\begin{figure}[H] + \centering + \includegraphics[width=\linewidth]{./img/nodo_arbol_b+.png} + \caption{Estructura de un árbol B+} + \label{fig:estructura-nodo-arbol-b+} +\end{figure} + +### Operaciones + +Las operaciones en general son similares a los arboles B, pero con algunas +particularidades. + +#### Búsqueda + +En el caso de la búsqueda en un árbol B+, es similar a la búsqueda del árbol B, +pero no se debe detener cuando se encuentre la clave en la pagina raíz o en un +pagina interior, si no que se debe seguir por la rama derecha apuntada por esa +clave. + +#### Inserción + +El proceso de inserción en un árbol B+ es muy similar al de un árbol B, pero se +diferencia en que cuando se inserta una nueva clave en un nodo lleno, esta se +divide en dos, con la primera teniendo el numero mínimo de claves y la segundo +el numero mínimo de claves sumada las nueva clave, el elemento que promociona a +un nuevo nivel es una copia de la clave central. + +#### Eliminación + +En el caso de eliminar un elemento una vez encontrado, se elimina directamente +de la hoja (todos los datos están en las hojas), si luego de eliminarlo la hoja +queda con menos del mínimo de elementos por hoja ($m/2$) entonces hay que +eliminar la hoja y redistribuir los elementos con las hojas hermanas, la clave +copia en el nodo padre se debe eliminar también, si el nodo padre también queda +con menos del mínimo de claves por hoja, entonces hay que realizar el mismo +procedimiento. ## Colas con prioridad -Las colas con prioridad es una estructura de datos de tipo cola pero tienen la -particularidad que al momento de insertar un elemento se puede asignar una -prioridad, de manera que se inserte con un orden de prioridad. +Las colas con prioridad son una estructura de datos de tipo cola (o queue) pero +tienen la particularidad que al momento de insertar un elemento se puede asignar +una prioridad, de esta forma no se inserta siempre en un mismo lugar si no que +se puede inserta con un orden en particular. Existen varias maneras de implementar una cola con prioridad, por ejemplo un vector, una lista enlazada o un árbol heap. diff --git a/notas/arbol/arboles.pdf b/notas/arbol/arboles.pdf Binary files differ. diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rdd.gv b/notas/arbol/img/arbol_avl_desbalanceado_rdd.gv @@ -0,0 +1,15 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.40, fontname="sans"]; + + A [pos=" 0.00, 1.00!"]; + A_label [pos=" 0.35, 1.00!", shape=plaintext, label="-2"]; + + B [pos=" 0.50, 0.50!"]; + B_label [pos=" 0.85, 0.50!", shape=plaintext, label="-1"]; + + C [pos=" 0.00, 0.00!"]; + C_label [pos=" 0.35, 0.00!", shape=plaintext, label="0"]; + + A -- B -- C; +} diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rdd.png b/notas/arbol/img/arbol_avl_desbalanceado_rdd.png Binary files differ. diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rdd_primer_rot.gv b/notas/arbol/img/arbol_avl_desbalanceado_rdd_primer_rot.gv @@ -0,0 +1,15 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.40, fontname="sans"]; + + A [pos="-0.50, 0.50!"]; + A_label [pos="-0.15, 0.50!", shape=plaintext, label="-2"]; + + C [pos=" 0.00, 0.00!"]; + C_label [pos=" 0.35, 0.00!", shape=plaintext, label="-1"]; + + B [pos=" 0.50,-0.50!"]; + B_label [pos=" 0.85,-0.50!", shape=plaintext, label="0"]; + + A -- C -- B; +} diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rdd_primer_rot.png b/notas/arbol/img/arbol_avl_desbalanceado_rdd_primer_rot.png Binary files differ. diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rdi.gv b/notas/arbol/img/arbol_avl_desbalanceado_rdi.gv @@ -0,0 +1,16 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.40, fontname="sans"]; + + A [pos=" 0.50, 1.00!"]; + A_label [pos=" 0.85, 1.00!", shape=plaintext, label="-2"]; + + B [pos=" 0.00, 0.50!"]; + B_label [pos=" 0.35, 0.50!", shape=plaintext, label="-1"]; + + C [pos=" 0.50, 0.00!"]; + C_label [pos=" 0.85, 0.00!", shape=plaintext, label="0"]; + + + A -- B -- C; +} diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rdi.png b/notas/arbol/img/arbol_avl_desbalanceado_rdi.png Binary files differ. diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rdi_primer_rot.gv b/notas/arbol/img/arbol_avl_desbalanceado_rdi_primer_rot.gv @@ -0,0 +1,16 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.40, fontname="sans"]; + + A [pos=" 0.50, 0.50!"]; + A_label [pos=" 0.85, 0.50!", shape=plaintext, label="-2"]; + + B [pos="-0.50,-0.50!"]; + B_label [pos="-0.15,-0.50!", shape=plaintext, label="0"]; + + C [pos=" 0.00, 0.00!"]; + C_label [pos=" 0.35, 0.00!", shape=plaintext, label="-1"]; + + A -- C; + C -- B; +} diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rdi_primer_rot.png b/notas/arbol/img/arbol_avl_desbalanceado_rdi_primer_rot.png Binary files differ. diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rsd.gv b/notas/arbol/img/arbol_avl_desbalanceado_rsd.gv @@ -0,0 +1,15 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.40, fontname="sans"]; + + A [pos=" 0.50, 0.50!"]; + A_label [pos=" 0.85, 0.50!", shape=plaintext, label="-2"]; + + B [pos=" 0.00, 0.00!"]; + B_label [pos=" 0.35, 0.00!", shape=plaintext, label="-1"]; + + C [pos="-0.50,-0.50!"]; + C_label [pos="-0.15,-0.50!", shape=plaintext, label="0"]; + + A -- B -- C; +} diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rsd.png b/notas/arbol/img/arbol_avl_desbalanceado_rsd.png Binary files differ. diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rsi.gv b/notas/arbol/img/arbol_avl_desbalanceado_rsi.gv @@ -0,0 +1,15 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.40, fontname="sans"]; + + A [pos="-0.50, 0.50!"]; + A_label [pos="-0.15, 0.50!", shape=plaintext, label="-2"]; + + B [pos=" 0.00, 0.00!"]; + B_label [pos=" 0.35, 0.00!", shape=plaintext, label="-1"]; + + C [pos=" 0.50,-0.50!"]; + C_label [pos=" 0.85,-0.50!", shape=plaintext, label="0"]; + + A -- B -- C; +} diff --git a/notas/arbol/img/arbol_avl_desbalanceado_rsi.png b/notas/arbol/img/arbol_avl_desbalanceado_rsi.png Binary files differ. diff --git a/notas/arbol/img/arbol_avl_rdd.gv b/notas/arbol/img/arbol_avl_rdd.gv @@ -0,0 +1,15 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.40, fontname="sans"]; + + A [pos=" 0.50, 1.00!"]; + A_label [pos=" 0.85, 1.00!", shape=plaintext, label="-2"]; + + B [pos=" 0.00, 0.50!"]; + B_label [pos=" 0.35, 0.50!", shape=plaintext, label="-1"]; + + C [pos=" 0.50, 0.00!"]; + C_label [pos=" 0.85, 0.00!", shape=plaintext, label="0"]; + + A -- B -- C; +} diff --git a/notas/arbol/img/arbol_avl_rdd.png b/notas/arbol/img/arbol_avl_rdd.png Binary files differ. diff --git a/notas/arbol/img/arbol_avl_rsd.gv b/notas/arbol/img/arbol_avl_rsd.gv @@ -0,0 +1,15 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.40, fontname="sans"]; + + B [pos=" 0.00, 0.50!"]; + B_label [pos=" 0.35, 0.50!", shape=plaintext, label="0"]; + + C [pos="-0.50, 0.00!"]; + C_label [pos="-0.15, 0.00!", shape=plaintext, label="0"]; + + A [pos=" 0.50, 0.00!"]; + A_label [pos=" 0.85, 0.00!", shape=plaintext, label="0"]; + + B -- {A, C}; +} diff --git a/notas/arbol/img/arbol_avl_rsd.png b/notas/arbol/img/arbol_avl_rsd.png Binary files differ. diff --git a/notas/arbol/img/arbol_avl_rsi.gv b/notas/arbol/img/arbol_avl_rsi.gv @@ -0,0 +1,15 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.40, fontname="sans"]; + + B [pos=" 0.00, 0.50!"]; + B_label [pos=" 0.35, 0.50!", shape=plaintext, label="0"]; + + A [pos="-0.50, 0.00!"]; + A_label [pos="-0.15, 0.00!", shape=plaintext, label="0"]; + + C [pos=" 0.50, 0.00!"]; + C_label [pos=" 0.85, 0.00!", shape=plaintext, label="0"]; + + B -- {A, C}; +} diff --git a/notas/arbol/img/arbol_avl_rsi.png b/notas/arbol/img/arbol_avl_rsi.png Binary files differ. diff --git a/notas/arbol/img/arbol_binario.png b/notas/arbol/img/arbol_binario.png Binary files differ. diff --git a/notas/arbol/img/arbol_binario.svg b/notas/arbol/img/arbol_binario.svg @@ -1,242 +0,0 @@ -<?xml version="1.0" encoding="UTF-8" standalone="no"?> -<!-- Created with Inkscape (http://www.inkscape.org/) --> - -<svg - xmlns:dc="http://purl.org/dc/elements/1.1/" - xmlns:cc="http://creativecommons.org/ns#" - xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" - xmlns:svg="http://www.w3.org/2000/svg" - xmlns="http://www.w3.org/2000/svg" - version="0.0" - width="300" - height="250" - viewBox="0 0 289.333 253" - id="svg2623" - xml:space="preserve"><defs - id="defs2799" /><g - transform="matrix(1.012,0,0,1.012,180.087,42.504)" - id="g2987" - style="overflow:visible"><path - d="m -85.000008,-2 a 20,20 0 1 1 -40.000002,0 20,20 0 1 1 40.000002,0 z" - transform="translate(70,-15)" - id="path2981" - style="fill:none;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><text - x="-42.312504" - y="-8.09375" - id="text2983" - xml:space="preserve" - style="font-size:24px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-width:2;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate;font-family:DejaVu Sans;-inkscape-font-specification:DejaVu Sans"><tspan - x="-42.312504" - y="-8.09375" - id="tspan2985">2</tspan></text> - -</g><g - transform="matrix(1.012,0,0,1.012,104.187,98.164)" - id="g2992" - style="overflow:visible"><path - d="m -85.000008,-2 a 20,20 0 1 1 -40.000002,0 20,20 0 1 1 40.000002,0 z" - transform="translate(70,-15)" - id="path2994" - style="fill:none;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><text - x="-42.312504" - y="-8.09375" - id="text2996" - xml:space="preserve" - style="font-size:24px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-width:2;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate;font-family:DejaVu Sans;-inkscape-font-specification:DejaVu Sans"><tspan - x="-42.312504" - y="-8.09375" - id="tspan2998">7</tspan></text> - -</g><g - transform="matrix(1.012,0,0,1.012,255.986,98.164)" - id="g3000" - style="overflow:visible"><path - d="m -85.000008,-2 a 20,20 0 1 1 -40.000002,0 20,20 0 1 1 40.000002,0 z" - transform="translate(70,-15)" - id="path3002" - style="fill:none;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><text - x="-42.312504" - y="-8.09375" - id="text3004" - xml:space="preserve" - style="font-size:24px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-width:2;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate;font-family:DejaVu Sans;-inkscape-font-specification:DejaVu Sans"><tspan - x="-42.312504" - y="-8.09375" - id="tspan3006">5</tspan></text> - -</g><g - transform="matrix(1.012,0,0,1.012,53.5865,174.064)" - id="g3008" - style="overflow:visible"><path - d="m -85.000008,-2 a 20,20 0 1 1 -40.000002,0 20,20 0 1 1 40.000002,0 z" - transform="translate(70,-15)" - id="path3010" - style="fill:none;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><text - x="-42.312504" - y="-8.09375" - id="text3012" - xml:space="preserve" - style="font-size:24px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-width:2;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate;font-family:DejaVu Sans;-inkscape-font-specification:DejaVu Sans"><tspan - x="-42.312504" - y="-8.09375" - id="tspan3014">2</tspan></text> - -</g><g - transform="matrix(1.012,0,0,1.012,154.786,174.064)" - id="g3016" - style="overflow:visible"><path - d="m -85.000008,-2 a 20,20 0 1 1 -40.000002,0 20,20 0 1 1 40.000002,0 z" - transform="translate(70,-15)" - id="path3018" - style="fill:none;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><text - x="-42.312504" - y="-8.09375" - id="text3020" - xml:space="preserve" - style="font-size:24px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-width:2;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate;font-family:DejaVu Sans;-inkscape-font-specification:DejaVu Sans"><tspan - x="-42.312504" - y="-8.09375" - id="tspan3022">6</tspan></text> - -</g><g - transform="matrix(1.012,0,0,1.012,306.586,174.064)" - id="g3024" - style="overflow:visible"><path - d="m -85.000008,-2 a 20,20 0 1 1 -40.000002,0 20,20 0 1 1 40.000002,0 z" - transform="translate(70,-15)" - id="path3026" - style="fill:none;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><text - x="-42.312504" - y="-8.09375" - id="text3028" - xml:space="preserve" - style="font-size:24px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-width:2;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate;font-family:DejaVu Sans;-inkscape-font-specification:DejaVu Sans"><tspan - x="-42.312504" - y="-8.09375" - id="tspan3030">9</tspan></text> - -</g><g - transform="matrix(1.012,0,0,1.012,114.307,244.904)" - id="g3032" - style="overflow:visible"><path - d="m -85.000008,-2 a 20,20 0 1 1 -40.000002,0 20,20 0 1 1 40.000002,0 z" - transform="translate(70,-15)" - id="path3034" - style="fill:none;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><text - x="-42.312504" - y="-8.09375" - id="text3036" - xml:space="preserve" - style="font-size:24px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-width:2;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate;font-family:DejaVu Sans;-inkscape-font-specification:DejaVu Sans"><tspan - x="-42.312504" - y="-8.09375" - id="tspan3038">5</tspan></text> - -</g><g - transform="matrix(1.012,0,0,1.012,186.995,244.744)" - id="g3040" - style="overflow:visible"><path - d="m -85.000008,-2 a 20,20 0 1 1 -40.000002,0 20,20 0 1 1 40.000002,0 z" - transform="translate(78.1738,-14.8418)" - id="path3042" - style="fill:none;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><text - x="-42.312504" - y="-8.09375" - id="text3044" - xml:space="preserve" - style="font-size:24px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-width:2;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate;font-family:DejaVu Sans;-inkscape-font-specification:DejaVu Sans"><tspan - x="-42.312504" - y="-8.09375" - id="tspan3046">11</tspan></text> - -</g><g - transform="matrix(1.012,0,0,1.012,255.986,244.904)" - id="g3048" - style="overflow:visible"><path - d="m -85.000008,-2 a 20,20 0 1 1 -40.000002,0 20,20 0 1 1 40.000002,0 z" - transform="translate(70,-15)" - id="path3050" - style="fill:none;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><text - x="-42.312504" - y="-8.09375" - id="text3052" - xml:space="preserve" - style="font-size:24px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-width:2;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate;font-family:DejaVu Sans;-inkscape-font-specification:DejaVu Sans"><tspan - x="-42.312504" - y="-8.09375" - id="tspan3054">4</tspan></text> - -</g><g - transform="matrix(-0.597738,-0.801692,0.801692,-0.597738,131.928,233.807)" - id="g3096"><path - d="m 159.85851,60.695994 -3.04799,14.192 6.096,0 -3.04801,-14.192 z" - id="path3092" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1.99999988;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><path - d="m 159.8465,70.84 0,43.93551" - id="path3094" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /></g><g - transform="matrix(0.597738,-0.801692,-0.801692,-0.597738,156.41,233.807)" - id="g3106" - style="overflow:visible"><path - d="m 159.85851,60.695994 -3.04799,14.192 6.096,0 -3.04801,-14.192 z" - id="path3108" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1.99999988;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><path - d="m 159.8465,70.84 0,43.93551" - id="path3110" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /></g><g - transform="matrix(-0.836546,-0.547897,0.547897,-0.836546,130.664,278.069)" - id="g3112" - style="overflow:visible"><path - d="m 159.85851,60.695994 -3.04799,14.192 6.096,0 -3.04801,-14.192 z" - id="path3114" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1.99999988;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><path - d="m 159.8465,70.84 0,39.91866" - id="path3116" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /></g><g - transform="matrix(0.836546,-0.547897,-0.547897,-0.836546,7.25664,278.147)" - id="g3118" - style="overflow:visible"><path - d="m 159.85851,60.695994 -3.04799,14.192 6.096,0 -3.04801,-14.192 z" - id="path3120" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1.99999988;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><path - d="m 159.8465,70.84 0,39.91866" - id="path3122" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /></g><g - transform="matrix(0.836546,-0.547897,-0.547897,-0.836546,159.563,277.894)" - id="g3124" - style="overflow:visible"><path - d="m 159.85851,60.695994 -3.04799,14.192 6.096,0 -3.04801,-14.192 z" - id="path3126" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1.99999988;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><path - d="m 159.8465,70.84 0,39.91866" - id="path3128" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /></g><g - transform="matrix(-0.836546,-0.547897,0.547897,-0.836546,333.182,349.493)" - id="g3130" - style="overflow:visible"><path - d="m 159.85851,60.695994 -3.04799,14.192 6.096,0 -3.04801,-14.192 z" - id="path3132" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1.99999988;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><path - d="m 159.8465,70.84 0,36.27828" - id="path3134" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /></g><g - transform="matrix(0.875939,-0.482422,-0.482422,-0.875939,39.6299,340.2)" - id="g3142" - style="overflow:visible"><path - d="m 159.85851,60.695994 -3.04799,14.192 6.096,0 -3.04801,-14.192 z" - id="path3144" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1.99999988;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><path - d="m 159.8465,70.84 0,31.1306" - id="path3146" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /></g><g - transform="matrix(-0.875939,-0.482422,0.482422,-0.875939,199.907,341.565)" - id="g3148" - style="overflow:visible"><path - d="m 159.85851,60.695994 -3.04799,14.192 6.096,0 -3.04801,-14.192 z" - id="path3150" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1.99999988;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /><path - d="m 159.8465,70.84 0,31.1306" - id="path3152" - style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" /></g><metadata - id="metadata3117"><rdf:RDF><cc:Work - rdf:about=""><dc:title></dc:title></cc:Work></rdf:RDF></metadata></svg> -\ No newline at end of file diff --git a/notas/arbol/img/arbol_de_busqueda_binario.png b/notas/arbol/img/arbol_de_busqueda_binario.png Binary files differ. diff --git a/notas/arbol/img/arbol_de_busqueda_binario_letras.png b/notas/arbol/img/arbol_de_busqueda_binario_letras.png Binary files differ. diff --git a/notas/arbol/img/binario_incompleto.gv b/notas/arbol/img/binario_incompleto.gv @@ -0,0 +1,19 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.5, penwidth=2, + fontsize=22, fontname="sans"]; + edge [penwidth=2.0]; + + A [pos=" 0.0, 0.7!", label="2"]; + B [pos="-0.8, 0.0!", label="7"]; + C [pos=" 0.8, 0.0!", label="2"]; + + D [pos="-1.2,-0.8!", label="2"]; + E [pos="-0.4,-0.8!", label="6"]; + + // G [pos=" 1.2,-0.8!"]; + // F [pos=" 0.4,-0.8!"]; + + A -- B -- {D, E}; + A -- C; +} diff --git a/notas/arbol/img/binario_incompleto.png b/notas/arbol/img/binario_incompleto.png Binary files differ. diff --git a/notas/arbol/img/binario_letras.gv b/notas/arbol/img/binario_letras.gv @@ -0,0 +1,19 @@ +graph G { + layout=neato; + node[shape=circle, fixedsize=true, width=0.5, penwidth=2, + fontsize=22, fontname="sans"]; + edge [penwidth=2.0]; + + A [pos=" 0.0, 0.7!"]; + B [pos="-0.8, 0.0!"]; + C [pos=" 0.8, 0.0!"]; + + D [pos="-1.2,-0.8!"]; + E [pos="-0.4,-0.8!"]; + + F [pos=" 0.4,-0.8!"]; + G [pos=" 1.2,-0.8!"]; + + A -- B -- {D, E}; + A -- C -- {F, G}; +} diff --git a/notas/arbol/img/binario_letras.png b/notas/arbol/img/binario_letras.png Binary files differ. diff --git a/notas/arbol/img/nodo_arbol_b+.gv b/notas/arbol/img/nodo_arbol_b+.gv @@ -0,0 +1,64 @@ +// compile with dot + +graph Tree { + rankdir=TB; + node [shape=record, fontname="sans"]; + splines=polyline; + + R [label=< + <table border="0" cellborder="1" cellspacing="0" cellpadding="6"> + <tr> + <td port="left">*</td> + <td>k1</td> + <td port="middle">*</td> + <td>k2</td> + <td port="right">*</td> + </tr> + </table> + >, shape=none]; + + A [label=< + <table border="0" cellborder="1" cellspacing="0" cellpadding="6"> + <tr> + <td port="left">*</td> + <td>k1</td> + <td port="middle">*</td> + <td>k3</td> + <td port="right">*</td> + </tr> + </table> + >, shape=none]; + + B [label=< + <table border="0" cellborder="1" cellspacing="0" cellpadding="6"> + <tr> + <td port="left">*</td> + <td>k2</td> + <td port="middle">*</td> + <td>k4</td> + <td port="right">*</td> + </tr> + </table> + >, shape=none]; + + C [label=< + <table border="0" cellborder="1" cellspacing="0" cellpadding="6"> + <tr> + <td port="left">*</td> + <td>k5</td> + <td port="middle">*</td> + <td>k6</td> + <td port="right">*</td> + </tr> + </table> + >, shape=none]; + + R:left -- A:middle; + R:middle -- B:middle; + R:right -- C:middle; + + A:right -- B:left [dir=forward, arrowhead=normal, arrowsize=0.8]; + B:right -- C:left [dir=forward, arrowhead=normal, arrowsize=0.8]; + + { rank=same; A; B; C; } +} diff --git a/notas/arbol/img/nodo_arbol_b+.png b/notas/arbol/img/nodo_arbol_b+.png Binary files differ. diff --git a/notas/arbol/img/nodo_arbol_b.gv b/notas/arbol/img/nodo_arbol_b.gv @@ -1,12 +1,14 @@ +// compile with dot + graph Tree { rankdir=TB; - node [shape=record]; + node [shape=record, fontname="sans"]; splines=polyline; R [label= "{{<left>*|k1|<middle>*|k2|<right>*}}"]; - A [label= "{{<left>*|k1|<middle>*|k2|<right>*}}"]; - B [label= "{{<left>*|k1|<middle>*|k2|<right>*}}"]; - C [label= "{{<left>*|k1|<middle>*|k2|<right>*}}"]; + A [label= "{{<left>*|k3|<middle>*|k4|<right>*}}"]; + B [label= "{{<left>*|k5|<middle>*|k6|<right>*}}"]; + C [label= "{{<left>*|k7|<middle>*|k8|<right>*}}"]; R:left -- A; R:middle -- B; diff --git a/notas/arbol/img/nodo_arbol_b.png b/notas/arbol/img/nodo_arbol_b.png Binary files differ. diff --git a/notas/arbol/img/nodo_arbol_busqueda_binario.gv b/notas/arbol/img/nodo_arbol_busqueda_binario.gv @@ -1,7 +1,9 @@ +// compile with dot + graph Tree { rankdir=TB; splines=polyline; - node [shape=record]; + node [shape=record, fontname="sans"]; R [label= "{{<left>*|dato|<right>*}}"]; A [label= "{{<left>*|dato|<right>*}}"]; diff --git a/notas/arbol/img/nodo_arbol_busqueda_binario.png b/notas/arbol/img/nodo_arbol_busqueda_binario.png Binary files differ. diff --git a/notas/arbol/style.tex b/notas/arbol/style.tex @@ -0,0 +1,284 @@ +% \documentclass[12pt]{article} + +% page setup +% \usepackage[a4paper, +% top=2.5cm, +% bottom=2.5cm, +% left=2.00cm, +% right=2.00cm, +% bmargin=2.50cm]{geometry} +\usepackage[a4paper, + top=2.75cm, + bottom=2.50cm, + left=2.25cm, + right=2.25cm, + bmargin=2.50cm]{geometry} + +\usepackage[spanish]{babel} + +\usepackage{float} +\usepackage{titlesec} +\usepackage{fontspec} +\setmainfont{Helvetica} + +% right pointing hand +\usepackage{utfsym} + +% make pictures caption font bold and small +% \usepackage[font={footnotesize}]{caption} +\usepackage{subcaption} + +% inline code (backticks in md) +\linespread{1.10} +\definecolor{bgcolor}{HTML}{e0e0e0} +\let\oldtexttt\texttt + +\renewcommand{\texttt}[1]{ + \colorbox{bgcolor}{\oldtexttt{#1}} +} + +% change boldfont bold to extrabold +% \setmainfont[ +% BoldFont={Inter-ExtraBold} +% ]{Inter} + +% change regular font to light font +% \setmainfont{Inter light} + +\newfontfamily\titlefont{Inter}[ +UprightFont = *-Regular, +BoldFont = *-ExtraBold, +Scale = 0.90 +] + +\newfontfamily\sectionsfont{Inter}[ +UprightFont = *-Regular, +BoldFont = *-Bold, +] + +\setmathfont[Scale=1.00]{Fira Math} + +\usepackage{xcolor} +\definecolor{ugrey}{HTML}{333333} + +\titleformat{\section} +{\color{black}\titlefont\Large\bfseries} +{\color{black}} +{0em} +{} + +\titleformat{\subsection} +{\color{black}\sectionsfont\large\bfseries} +{\color{black}} +{0em} +{} + +\titleformat{\subsubsection} +{\color{black}\sectionsfont\bfseries} +{\color{black}} +{0em} +{} + +\titleformat{\paragraph} +{\color{black}\sectionsfont\bfseries} +{\color{black}\theparagraph} +{0em} +{} + +\titleformat{\subparagraph} +{\color{black}\normalfont\bfseries} +{\color{black}\theparagraph} +{0em} +{} + +% spacing: how to read {12pt plus 4pt minus 2pt} +% 12pt is what we would like the spacing to be +% plus 4pt means that TeX can stretch it by at most 4pt +% minus 2pt means that TeX can shrink it by at most 2pt +% +% \titlespacing{command}{left spacing}{before spacing}{after spacing}[right] + +\titlespacing*{\section} +{0pt}{2.00ex plus 0.25ex minus 0.10ex}{1.25ex plus 0.00ex} + +\titlespacing*{\subsection} +{0pt}{1.25ex plus 0.10ex minus 0.10ex}{0.75ex plus 0.00ex} + +\titlespacing*{\subsubsection} +{0pt}{1.25ex plus 0.10ex minus 0.10ex}{0.50ex plus 0.00ex} + +\titlespacing*{\paragraph} +{0pt}{1.25ex plus 0.10ex minus 0.10ex}{0.50ex plus 0.00ex} + +\titlespacing*{\subparagraph} +{0pt}{1.25ex plus 0.10ex minus 0.10ex}{0.50ex plus 0.00ex} + +% spacing between formulas and text +% \usepackage[nodisplayskipstretch]{setspace} +% \setstretch{1.20} + +% \setlength{\textfloatsep}{2pt plus 1.0pt minus 2.0pt} +% \setlength{\intextsep}{2pt plus 1.0pt minus 2.0pt} + + +\setlength{\abovecaptionskip}{1.00em} % above caption +\setlength{\belowcaptionskip}{-0.85em} % below caption + +\setlength{\textfloatsep}{0pt} +\setlength{\dblfloatsep}{0pt} % twocolumn float sep +\setlength{\intextsep}{8pt} + +\setlength{\abovedisplayskip}{0pt} +\setlength{\belowdisplayskip}{0pt} + +\setlength{\abovedisplayshortskip}{0pt} +\setlength{\belowdisplayshortskip}{0pt} + +\setlength{\belowdisplayshortskip}{\belowdisplayskip} + +\setlength{\baselineskip}{0pt} + +\setlength{\parskip}{0.5em} +\linespread{1.00} % 1.25 = 1.5 líneas aprox + +% \usepackage{setspace} +% \setstretch{1.25} + +% \captionsetup{font=small, labelfont=bf} +\captionsetup{font=small, labelfont=md} +\captionsetup[sub]{font=footnotesize,labelfont=md} + +\renewcommand\thesubfigure{\arabic{subfigure}} + +\renewcommand{\figurename}{Figura} +\renewcommand{\tablename}{Tabla} + +% \renewcommand{\contentsname}{Índice} +\renewcommand\contentsname{\vspace*{-45pt}} + +% TOC dots separation +% \renewcommand{\cftdotsep}{10} + +% \setlength{\cftsecindent}{0pt}% Remove indent for \section +% \setlength{\cftsubsecindent}{5pt}% Remove indent for \subsection +% \setlength{\cftsubsubsecindent}{0pt}% Remove indent for \subsubsec + +\setcounter{tocdepth}{4} + +\usepackage{titling} +\renewcommand{\maketitle}{ + \begin{flushleft} + {\bfseries\Huge\thetitle} + % \vspace{1mm} + \end{flushleft} + % \thispagestyle{empty} +} + +% remove the page number from all the pages that the TOC occupies +% \addtocontents{toc}{\protect\thispagestyle{empty}} + +% add page break after TOC set it to page number 1 +\let\oldtableofcontents\tableofcontents % remember the definition +\renewcommand\tableofcontents{ + \oldtableofcontents % use the standard toc + \thispagestyle{empty} + \pagebreak + \setcounter{page}{1} +} + +% Set text color for all document +% \color{ugrey} + +\usepackage[titles]{tocloft} +\renewcommand{\cftdotsep}{1.5} +\renewcommand{\cftsetpnumwidth}{1.5} +\renewcommand{\cftsetrmarg}{1.5} + +% \usepackage{float} +% \makeatletter +% \def\fps@figure{H} +% \makeatother + +% nicer chemical figures +\usepackage{chemfig} + +% change style of quote, see also https://tex.stackexchange.com/a/436253/114857 +\usepackage[most]{tcolorbox} + +\definecolor{linequote}{RGB}{224,215,188} +\definecolor{bordercolor}{RGB}{221,221,221} +% \definecolor{backquote}{RGB}{249,245,233} +\definecolor{backquote}{RGB}{245,245,245} + +% change left border: https://tex.stackexchange.com/a/475716/114857 +% change left margin: https://tex.stackexchange.com/a/457936/114857 +\newtcolorbox{myquote}[1][]{% + enhanced, + breakable, + size=minimal, + left=0pt, + top=12pt, + bottom=12pt, + right=12pt, + boxrule=1pt, + sharp corners=all, + colback=backquote, + colframe=black, + #1} + +% redefine quote environment to use the myquote environment, see +% https://tex.stackexchange.com/a/337587/114857 +\renewenvironment{quote}{\begin{myquote}}{\end{myquote}} + +% better fractions +\usepackage{nicefrac,xfrac} + +% surround footnotes number with square brackets and always use numbers (even +% inside quoted text) +% https://www.overleaf.com/learn/latex/Footnotes +\renewcommand*{\thefootnote}{\ [\arabic{footnote}]\ } +\renewcommand*{\thempfootnote}{\ [\arabic{mpfootnote}]\ } + +% space between text and footer +\setlength\footskip{36pt} +\setlength{\skip\footins}{2pt} + +% align first letter of all the lines in the footnotes +\usepackage[bottomfloats, belowfloats, hang, multiple, ragged]{footmisc} +\setlength{\footnotemargin}{1em} + +\newcommand{\unit}[2]{\nicefrac{#1}{#2}} + +\usepackage{enumitem} +\usepackage{amsfonts} + +\setlist[itemize,1]{label=$\bullet$} +\setlist[itemize,2]{label=$\textopenbullet$} + +\usepackage{tabularx} +\usepackage{multirow} % Required for multirows +\usepackage{colortbl} + +% Reduce space around displayed equations safely +\makeatletter +\setlength{\jot}{8pt} % valor por defecto es 3pt aproximadamente +\makeatother + +\usepackage{multicol} +\setlength{\columnsep}{12pt} + +% Delay start of two-column layout +\AtBeginDocument{ + \renewcommand{\figurename}{Figura} + \renewcommand{\tablename}{Tabla} +} + +% Begin multicols after title +% \usepackage{etoolbox} +% \pretocmd{\maketitle}{\clearpage\begin{multicols*}{2}}{}{} +% \AtEndDocument{ +% \end{multicols*} +% } + +\binoppenalty=10000 +\relpenalty=10000
