diff --git a/mr/ub7/mr7.pdf b/mr/ub7/mr7.pdf index 28cf21e..65e3e7f 100644 --- a/mr/ub7/mr7.pdf +++ b/mr/ub7/mr7.pdf Binary files differ diff --git a/mr/ub7/mr7.tex b/mr/ub7/mr7.tex index cae81b4..6b6ef99 100644 --- a/mr/ub7/mr7.tex +++ b/mr/ub7/mr7.tex @@ -13,6 +13,7 @@ \usepackage{amssymb, amsthm} %noch stärker erweiterte Mathe-Zeichen \usepackage{tikz} %TikZ ist kein Zeichenprogramm \usetikzlibrary{trees,automata,arrows,shapes} +\usepackage{qtree} \pagestyle{empty} @@ -93,8 +94,25 @@ \end{enumerate} \Aufgabe{Quadtree}{6} \begin{enumerate}[(a)] - \item TODO %TODO - \item TODO %TODO wtf? + \item + \Tree [.g + [.g + [.g b w b b ] + w + [.g b b b w ] + b + ] + [.g + [.g w b b w ] + g + [.g b g w b ] + [.g b b b w ] + ] + [.g g g g w ] + [.g w w w b ] + ] + \item Die meisten nötigen Änderungen am Baum verursacht eine Änderung in einem zusammenhängenden Quadrat, also beispielsweise links oben in der Ecke. Eine Änderung dort bewirkt vier neue Knoten und einen geänderten.\\ + Die wenigsten nötigen ergeben sich, wenn ein ohnehin einzelnes Gridfeld geändert wird. Dabei darf jedoch der Baum nicht kleiner werden. Dies ist beispielsweise der Fall bei dem Feld links unten. \item $256^2=\left(2^8\right)^2=4^8$\\ $\Rightarrow$ maxdepth: 9\\ $\Rightarrow$ maxnodes: $\sum\limits_{i=0}^9\frac{4^9-1}{4-1}=87381$