\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{graphicx}

\title{Derivations For updating balance factors in AVL trees after rotations}
\author{Blake Cecil}


\begin{document}

\maketitle

\section*{Left Rotations}

\begin{figure}[h]
\centering
\includegraphics[width=13cm]{avl.png}
\caption{A tree after left rotation}
\end{figure}
Allow $h_x$ to denote a sub-tree rooted at x. First we will calculate the new balance factor for B\\

By Definition we have:\\
\begin{align*}
newBal(B) &= h_a - h_c\\
oldBal(B) &= h_a - h_d
\end{align*}\\

However the height of d can also be given by $1 + max(h_c, h_e)$ so by substitution:\\

$$oldbal(B)=h_a - (1 + max(h_c, h_e)$$\\

Subtracting the old balance yields\\
\begin{align*}
newBal(B)-oldBal(B) &= h_a - h_c -(h_a - (1 + max(h_c, h_e))\\
newBal(B)-oldBal(B) &= h_a - h_c -h_a + (1 + max(h_c, h_e))\\
newBal(B)-oldBal(B) &= - h_c + (1 + max(h_c, h_e))\\
newBal(B) &= oldBal(B) + 1 + max(h_c, h_e) - h_c
\end{align*}\\

Applying the identity $max(a, b)-c = max(a-c, b- c)$ yields\\
\begin{align*}
newBal(B) &= oldBal(B) + 1 + max(h_c-h_c, h_e-h_c)\\
newBal(B) &= oldBal(B) + 1 + max(0, h_e-h_c)
\end{align*}\\

Returning to our original picture notice $h_e-h_c = -oldBal(D)$ so by substitution\\
$$newBal(B) = oldBal(B) + 1 + max(0, -oldBal(D))$$\\

Applying the identity $max(-a,-b) = -min(a, b)$ yields\\
$$newBal(B) = oldBal(B) + 1 - min(0, oldbal(D)$$\\

So $newBal(B) = oldBal(B) + 1 - min(0, oldbal(D)$ is the updated balance factor for Node B after a left rotate\\

We know want to determine the new balance for D\\

By Definition we have\\
\begin{align*}
newBal(D) &= h_b - h_e\\
oldBal(D) &= h_c - h_e
\end{align*}\\

However the height of b can also be given by $1 + max(h_a, h_c)$ so by substitution\\

$$newBal(D) = 1 + max(h_a, h_c) - h_e$$\\

Subtracting the old balance yields:\\
\begin{align*}
newBal(D) - oldBal(D) &= 1 + max(h_a, h_c) - h_e - (h_c - h_e)\\
newBal(D) - oldBal(D) &= 1 + max(h_a, h_c) - h_e - h_c + h_e\\
newBal(D) - oldBal(D) &= 1 + max(h_a, h_c) - h_c
\end{align*}\\

Applying the identity $max(a, b)-c = max(a-c, b- c)$ yields\\
$$newBal(D) - oldBal(D) = 1 + max(h_a - h_c, 0)$$\\

Returning to our original picture notice $h_a - h_c = newBal(B)$ so by substitution\\
\begin{align*}
newBal(D) - oldBal(D) &= 1 + max(newBal(B), 0)\\
newBal(D) &= oldBal(D) + 1 + max(newBal(B), 0)
\end{align*}

\section*{Right rotations}

By definition, we know that Blake is a doo-doo head. Thus it is trivial to see:

$$E(t) = \text{Curtis' ego} = e^{2t}$$\\

And thus long term behavior is categorized by:

\begin{align*}
\lim_{a \to \infty} \int_0^a E(t) dt &= \lim_{a \to \infty} \int_0^a e^{2t} dt\\
&= \infty
\end{align*}

And so as $t$ tends to $\infty$ his ego will as well. And this shit is fucking $\mathcal{O}(n\log{}n)$

\begin{minipage}[c]{0.35\linewidth}
\begin{align*}
\mathcal{O}(n!logloglogloglog(n^n)) &= 4x+y3^{2^2}\\
&= \text{blue}\\
&= f(uck)
\end{align*}
\end{minipage}
\hfill
\begin{minipage}[c]{0.35\linewidth}
Well fuck
\end{minipage}

\end{document}