From 9ea4ae3242d73a8e453564e0b9140f627976d005 Mon Sep 17 00:00:00 2001 From: Pavel Pisa Date: Sun, 8 Nov 2009 18:45:44 +0100 Subject: [PATCH] Not so much successful attempt to update equations to MathML in GAVL documentation. Signed-off-by: Pavel Pisa --- doc/srcdoc/gavl.tmpl | 1224 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 1221 insertions(+), 3 deletions(-) diff --git a/doc/srcdoc/gavl.tmpl b/doc/srcdoc/gavl.tmpl index 8774fff..e219fe4 100644 --- a/doc/srcdoc/gavl.tmpl +++ b/doc/srcdoc/gavl.tmpl @@ -753,6 +753,8 @@ cust2_root_t cust2_tree; --> + + Used Algorithms Background Tree Balancing Operations @@ -767,47 +769,80 @@ cust2_root_t cust2_tree; $\textrm{X}$ + + X + + . The height of subtree starting at $\textrm{X}$ + + X + + is labeled as $x=height(\textrm{X})$ - + x = height + (X + ) + + . Height difference (balance factor) for node $\textrm{X}$ + + X + + is labeled as $\Delta x=height(left(\textrm{X}))-height(right(\textrm{X}))$ + Δx = + height(left + (X)) - height(right(X)) + + . @@ -843,20 +878,55 @@ cust2_root_t cust2_tree; \end{eqnarray*} + + + Δs = n - b ≥ 2 + Δn = a - p ≥ 0 + + The height of subtree $\textrm{S}$ + + S + + is defined by highest branch, which is branch grovinggrowing from node $\textrm{A}$ @@ -876,47 +946,110 @@ b & = & a+1-\Delta s \end{eqnarray*} + + + n = a + 1 + s = a + 2 + p = a - Δn + b = a + 1 - Δs + + The height of branches $\textrm{N}$ + + N + + and $\textrm{S}$ + + S + + is marked as $n1$ + n1 + and $s1$ + s1 + after balancing. \begin{eqnarray*} @@ -925,11 +1058,39 @@ b & = & a+1-\Delta s \end{eqnarray*} + + + Δs1 = p - b + Δn1 = a - s1 + + \begin{eqnarray*} @@ -940,11 +1101,91 @@ s1 & = & a+1-\min (\Delta n,\Delta s-1) \end{eqnarray*} + + + s1 = max(p,b) + 1 + s1 = max(a - Δn,a + 1 - Δs) + 1 + s1 = a + 1 + max(-Δn, 1 - Δs) + s1 = a + 1 - min(Δn, Δs - 1) + + \begin{eqnarray*} @@ -959,11 +1200,121 @@ s1 & = & a+1-\min (\Delta n,\Delta s-1) \end{eqnarray*} + + + Δs1 = a - Δn - a - 1 + Δs + Δs1 = Δs - Δn - 1 + Δn1 = a - a - 1 + min(Δn, Δs - 1) + Δn1 = min(Δn - 1, Δs - 2) + Δn1 = Δn - 1Δs ≥ Δn + 1 + Δs - 2 Δs ≤ Δn + 1 + + Because balancing in case 1 does not guarantee that new tree has lower height than original tree, it is necessary to compute tree height change (tree height lowering). \begin{eqnarray*} @@ -979,11 +1330,145 @@ s-n1 & = & \left\langle \begin{array}{cc} \end{eqnarray*} + + + s - n1 = s - (max(a,s1) + 1) + = a + 2 - (max(a,a + 1 + max(-Δn, 1 - Δs)) + 1) + = 1 - max(0, max(1 - Δn, 2 - Δs)) + = min(1, Δn, Δs - 1)Δn ≥ 0, Δs ≥ 2 + = min(1, Δn) + s - n1 = 1 Δn≠0 + 0 Δn = 1 + + Tree Balancing Case 2 @@ -1013,38 +1498,58 @@ s-n1 & = & \left\langle \begin{array}{cc} $\textrm{P}$ + + P + + $\textrm{B}$ + + B + + or $\textrm{P}$ + + P + + $\textrm{C}$ + + C + + . \begin{eqnarray*} @@ -1053,11 +1558,42 @@ s-n1 & = & \left\langle \begin{array}{cc} \end{eqnarray*} + + + Δs = n - d ≥ 2 + Δn = a - p ≤-1 + + \begin{eqnarray*} @@ -1068,11 +1604,58 @@ a & = & p+\Delta n \end{eqnarray*} + + + n = p + 1 + s = p + 2 + d = p + 1 - Δs + a = p + Δn + + \begin{eqnarray*} @@ -1081,74 +1664,153 @@ a & = & p+\Delta n \end{eqnarray*} + + + forb ≥ cc = b - Δpp = b + 1 + forc ≥ bb = c + Δpp = c + 1 + + When $b\geq c$ + + b ≥ c + + then the height differences $\Delta s1$ + + Δs1 + + , $\Delta n1$ + + Δn1 + + and $\Delta p1$ + + Δp1 + + for nodes $\textrm{S}$ + + S + + , $\textrm{N}$ + + N + + and $\textrm{P}$ + + S + + of the balanced tree can be computed from next equations. \begin{eqnarray*} @@ -1165,74 +1827,293 @@ s1 & = & \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\ \end{eqnarray*} + + + b ≥ c , Δp ≥ 0 + n1 = b + 1 + p1 = b + 2 + s1 = max(c,d) + 1 = max(b - Δp,b + 2 - Δs) + 1 + Δs1 = c - d = b - Δp - b - 2 + Δs + Δs1 = Δs - 2 - Δp + Δn1 = a - b = b + 1 + Δn - b + Δn1 = Δn + 1 + Δp1 = n1 - s1 = b + 1 - max(b - Δp,b + 2 - Δs) - 1 + Δp1 = min(Δp, Δs - 2)Δp ≥ 0, Δs ≥ 2 + + When $c\geq b$ + + c ≥ b + + then the height differences $\Delta s1$ + + Δs1 + + , $\Delta n1$ + + Δn1 + + and $\Delta p1$ + + Δp1 + + for nodes $\textrm{S}$ + + S + + , $\textrm{N}$ + + N + + and $\textrm{P}$ + + P + + of the balanced tree can be computed from next equations. \begin{eqnarray*} @@ -1249,77 +2130,414 @@ n1 & = & \max (a,b)+1=\max (c+1+\Delta n,c+\Delta p)+1\\ \end{eqnarray*} + + + c ≥ b , Δp ≤ 0 + s1 = c + 1 + p1 = c + 2 + n1 = max(a,b) + 1 = max(c + 1 + Δn,c + Δp) + 1 + Δs1 = c - d = c - c - 2 + Δs + Δs1 = Δs - 2 + Δn1 = a - b = c + 1 + Δn - c - Δp + Δn1 = Δn + 1 - Δp + Δp1 = n1 - s1 = max(c + 1 + Δn,c + Δp) + 1 - c - 1 + Δp1 = max(Δn, Δs - 1)Δn ≤-1, Δp ≤ 0 + + Height of the AVL TreeMinimal number of nodes $T$ + T + can be computed recursively. \[ T(h)=T(h-1)+T(h-2)+1,\, T(0)=0,\, T(1)=1\] + + T(h) = T(h - 1) + T(h - 2) + 1,T(0) = 0,T(1) = 1 + + 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986 \[ T(h)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{(h+2)}-1\] + + T(h) = 1 + 5 1 + 5 + 2 (h+2) - 1 + + \[ T(h)=\frac{1}{\sqrt{5}}\, 2^{(h+2)\, log_{2}\left(\frac{1+\sqrt{5}}{2}\right)}-1\] + + T(h) = 1 + 52(h+2)log21+5 + 2 + - 1 + + \[ h=\left(log_{2}(T+1)-log_{2}\left(\frac{1}{\sqrt{5}}\right)\right)log_{2}^{-1}\left(\frac{1+\sqrt{5}}{2}\right)-2\] + + h = log2(T + 1) - log2 1 + 5 log2-1 1 + 5 + 2 - 2 + + \[ log_{2}^{-1}\left(\frac{1+\sqrt{5}}{2}\right)=1.44042\] + + log2-1 1 + 5 + 2 = 1.44042 + + An AVL tree with n nodes has height between log2 (n + 1) and 1.44 * log2 (n + 2) - 0.328. An AVL tree with height h has between pow (2, (h + .328) / 1.44) - 1 and pow (2, h) - 1 nodes.A red-black tree with n nodes has height at least log2 (n + 1) but no more than 2 * log2 (n + 1). A red-black tree with height h has at least pow (2, h / 2) - 1 nodes but no more than pow (2, h) - 1. -- 2.39.2