commit e8247e3ce93feaf9f0544b6df61999b467b18123
parent 2b5b44f49cf2cc66e2658641c03adacc91d6372f
Author: Martin Kloeckner <mjkloeckner@gmail.com>
Date: Wed, 23 Jul 2025 00:43:54 -0300
updated `notas/arbol`
Diffstat:
5 files changed, 42 insertions(+), 65 deletions(-)
diff --git a/notas/arbol/arboles.md b/notas/arbol/arboles.md
@@ -85,11 +85,13 @@ cuando el dato esta en una hoja).
[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 más a la izquierda del subárbol derecho del nodo eliminado.
+un orden. El caso en que el nodo a eliminar tiene uno o ningún hijo es trivial,
+cuando el nodo tiene 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 (con recorrido inorden) esto resulta en el nodo más a
+la izquierda del subárbol derecho del nodo eliminado, otras implementaciones
+utilizan el predecesor inorden, lo que resulta en el nodo mas a la derecha del
+subárbol izquierdo.
### Maneras de recorrer un árbol binario
@@ -149,8 +151,8 @@ alguna hoja, no lo estarían.
Se dice que un árbol esta completo, si todas sus hojas están llenas excepto el
ultimo nivel, que debe estar casi-completo de izquierda a derecha, es decir,
puede haber hojas vacías pero deben estar lo más a la derecha posible y solo en
-el ultimo nivel. En la figura 1 ambos arboles están completos. A un árbol que no
-es completo también se le dice **desequilibrado**.
+el ultimo nivel. En la figura 1 ambos arboles están completos. A un árbol
+incompleto también se le dice **desequilibrado**.
#### Árbol degenerado o patológico
@@ -478,15 +480,15 @@ mínimo.
\end{figure}
Los arboles heap típicamente se almacenan en vectores, almacenando los valores
-por nivel, es decir, para un padre en posición $k$ sus hijos se almacenaran en
-la posición $(2*k)+1$ y $(2*k)+2$ del vector para el hijo izquierdo y derecho
-respectivamente, análogamente, si el hijo esta en la posición $h$ del vector, el
-padre estará en la posición $floor((h-1)/2)$. Almacenando los arboles en
-vectores permite acceder a los datos de forma directa. En la figura 10 se
-muestra como se almacena el árbol heap de máximo de la figura 9.1, como
-particularidad se ve que el primer elemento es la raíz, lo cual es el elemento
-más grande por ser heap de máximo, si fuera de mínimo este sería el menor
-elemento.
+por nivel, contanto $k$ desde $0$, para un padre en posición $k$ sus hijos se
+almacenan en la posición $(2*k)+1$ y $(2*k)+2$ del vector para el hijo
+izquierdo y derecho respectivamente, análogamente, si el hijo esta en la
+posición $h$ del vector, el padre estará en la posición $floor((h-1)/2)$.
+Almacenando los arboles en vectores permite acceder a los datos de forma
+directa. En la figura 10 se muestra como se almacena el árbol heap de máximo de
+la figura 9.1, como particularidad se ve que el primer elemento es la raíz, lo
+cual es el elemento más grande por ser heap de máximo, si fuera de mínimo este
+sería el menor elemento.
\begin{figure}[H]
\centering
@@ -533,31 +535,29 @@ denominado `arr`, el lenguaje utilizado es python
```python
def heapify(arr, n, i):
# Se asume que la raiz es maxima
- largest = i
+ max = i
- # posicion de hijo izquierdo
+ # posicion de hijo izquierdo y derecho
left = (2*i) + 1
-
- # posicion de hijo derecho
right = (2*i) + 2
# se comprueba si hay hijo izquierdo y es
# mayor a la raiz
- if left < n and arr[left] > arr[largest]:
- largest = left
-
- # se comprueba si hay hijo derecho y es mayor
- # a la raiz o al hijo izquierdo
- if right < n and arr[right] > arr[largest]:
- largest = right
-
- # si la raiz no es maxima se intercambia con
- # el maximo hijo, y se llama recursivamente
- # a heapify para continuar con el algoritmo
- # con los hijos restantes
- if largest != i:
- arr[i], arr[largest] = arr[largest], arr[i]
- heapify(arr, n, largest)
+ if left < n and arr[left] > arr[max]:
+ max = left
+
+ # se comprueba si hay hijo derecho y es
+ # mayor a la raiz o al hijo izquierdo
+ if right < n and arr[right] > arr[max]:
+ max = right
+
+ # si la raiz no es maxima se intercambia
+ # con el maximo hijo, y se llama
+ # recursivamente a heapify para reordenar
+ # los hijos restantes
+ if max != i:
+ arr[i], arr[max] = arr[max], arr[i]
+ heapify(arr, n, max)
```
## Heapsort
diff --git a/notas/arbol/arboles.pdf b/notas/arbol/arboles.pdf
Binary files differ.
diff --git a/notas/arbol/img/Makefile b/notas/arbol/img/Makefile
@@ -1,7 +1,7 @@
SRC_DIR = src
BIN_DIR = bin
SOURCES = $(shell find $(SRC_DIR) -name "*.gv")
-TARGETS = $(patsubst $(SRC_DIR)/%.gv,%.png,$(SOURCES))
+TARGETS = $(patsubst $(SRC_DIR)/%.gv,$(BIN_DIR)/%.png,$(SOURCES))
all: $(BIN_DIR) $(TARGETS)
.PHONY: all clean
@@ -9,11 +9,11 @@ all: $(BIN_DIR) $(TARGETS)
$(BIN_DIR):
mkdir -p $(BIN_DIR)
-%.png: $(SRC_DIR)/%.gv
+$(BIN_DIR)/%.png: $(SRC_DIR)/%.gv
@if [ ! -d "$(BIN_DIR)" ]; then \
mkdir -p $(BIN_DIR); \
fi
- dot -Tpng $< -o $(BIN_DIR)/$@
+ dot -T png $< -o $@
clean:
- rm -r $(BIN_DIR)
+ rm -rf $(BIN_DIR)
diff --git a/notas/arbol/img/src/arbol_heap_vector.gv b/notas/arbol/img/src/arbol_heap_vector.gv
@@ -2,5 +2,5 @@ graph {
node[shape=record, penwidth=2, fontsize=22, fontname="sans"];
edge [penwidth=2.0];
- array [label="<f0> 50 | <f1> 30 | <f2> 20 | <f3> 15 | <f4> 10 | <f5> 8 | <f6> 16"];
+ array [label="<f0> 50 | <f1> 30 | <f2> 20 | <f3> 15 | <f4> 10 | <f5> 8 | <f6> 16"];
}
diff --git a/notas/arbol/style.tex b/notas/arbol/style.tex
@@ -99,7 +99,7 @@ BoldFont = *-Bold,
% \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}
+{0pt}{1.50ex 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}
@@ -120,7 +120,6 @@ BoldFont = *-Bold,
% \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
@@ -293,25 +292,6 @@ BoldFont = *-Bold,
\usepackage{xcolor}
-\definecolor{bggray}{rgb}{0.95,0.95,0.95}
-\definecolor{keywordcolor}{rgb}{0.2,0.2,0.7}
-\definecolor{commentcolor}{rgb}{0.0,0.5,0.0}
-\definecolor{stringcolor}{rgb}{0.6,0.1,0.1}
-
-\lstset{
- backgroundcolor=\color{bggray},
- basicstyle=\ttfamily\small,
- breaklines=true,
- breakatwhitespace=true,
- columns=fullflexible,
- % frame=single,
- showstringspaces=false,
- keywordstyle=\color{keywordcolor}\bfseries,
- commentstyle=\color{commentcolor}\itshape,
- stringstyle=\color{stringcolor},
- numbers=none,
-}
-
% tango style
\definecolor{bgcolor}{HTML}{F6F6F6}
\definecolor{keywordcolor}{HTML}{204A87}
@@ -321,9 +301,7 @@ BoldFont = *-Bold,
\definecolor{operatorcolor}{HTML}{CE5C00}
\definecolor{identifiercolor}{HTML}{000000} % For general text
-% === Listings configuration ===
\lstset{
- language=Python, % Change this for other languages
backgroundcolor=\color{bgcolor},
basicstyle=\ttfamily\small,
keywordstyle=\color{keywordcolor}\bfseries,
@@ -337,8 +315,7 @@ BoldFont = *-Bold,
columns=fullflexible,
showstringspaces=true,
frame=single,
- framerule=0pt,
+ framerule=1pt,
xleftmargin=0pt,
moredelim=**[is][\color{operatorcolor}\bfseries]{@}{@}, % allow inline operator styling using @...@
}
-
