1 | <!doctype html> |
---|
2 | <html> |
---|
3 | <head> |
---|
4 | <title>CodeMirror 2: sTeX mode</title> |
---|
5 | <link rel="stylesheet" href="../../lib/codemirror.css"> |
---|
6 | <script src="../../lib/codemirror.js"></script> |
---|
7 | <script src="stex.js"></script> |
---|
8 | <link rel="stylesheet" href="stex.css"> |
---|
9 | <style>.CodeMirror {background: #f8f8f8;}</style> |
---|
10 | <link rel="stylesheet" href="../../css/docs.css"> |
---|
11 | </head> |
---|
12 | <body> |
---|
13 | <h1>CodeMirror 2: sTeX mode</h1> |
---|
14 | <form><textarea id="code" name="code"> |
---|
15 | \begin{module}[id=bbt-size] |
---|
16 | \importmodule[balanced-binary-trees]{balanced-binary-trees} |
---|
17 | \importmodule[\KWARCslides{dmath/en/cardinality}]{cardinality} |
---|
18 | |
---|
19 | \begin{frame} |
---|
20 | \frametitle{Size Lemma for Balanced Trees} |
---|
21 | \begin{itemize} |
---|
22 | \item |
---|
23 | \begin{assertion}[id=size-lemma,type=lemma] |
---|
24 | Let $G=\tup{V,E}$ be a \termref[cd=binary-trees]{balanced binary tree} |
---|
25 | of \termref[cd=graph-depth,name=vertex-depth]{depth}$n>i$, then the set |
---|
26 | $\defeq{\livar{V}i}{\setst{\inset{v}{V}}{\gdepth{v} = i}}$ of |
---|
27 | \termref[cd=graphs-intro,name=node]{nodes} at |
---|
28 | \termref[cd=graph-depth,name=vertex-depth]{depth} $i$ has |
---|
29 | \termref[cd=cardinality,name=cardinality]{cardinality} $\power2i$. |
---|
30 | \end{assertion} |
---|
31 | \item |
---|
32 | \begin{sproof}[id=size-lemma-pf,proofend=,for=size-lemma]{via induction over the depth $i$.} |
---|
33 | \begin{spfcases}{We have to consider two cases} |
---|
34 | \begin{spfcase}{$i=0$} |
---|
35 | \begin{spfstep}[display=flow] |
---|
36 | then $\livar{V}i=\set{\livar{v}r}$, where $\livar{v}r$ is the root, so |
---|
37 | $\eq{\card{\livar{V}0},\card{\set{\livar{v}r}},1,\power20}$. |
---|
38 | \end{spfstep} |
---|
39 | \end{spfcase} |
---|
40 | \begin{spfcase}{$i>0$} |
---|
41 | \begin{spfstep}[display=flow] |
---|
42 | then $\livar{V}{i-1}$ contains $\power2{i-1}$ vertexes |
---|
43 | \begin{justification}[method=byIH](IH)\end{justification} |
---|
44 | \end{spfstep} |
---|
45 | \begin{spfstep} |
---|
46 | By the \begin{justification}[method=byDef]definition of a binary |
---|
47 | tree\end{justification}, each $\inset{v}{\livar{V}{i-1}}$ is a leaf or has |
---|
48 | two children that are at depth $i$. |
---|
49 | \end{spfstep} |
---|
50 | \begin{spfstep} |
---|
51 | As $G$ is \termref[cd=balanced-binary-trees,name=balanced-binary-tree]{balanced} and $\gdepth{G}=n>i$, $\livar{V}{i-1}$ cannot contain |
---|
52 | leaves. |
---|
53 | \end{spfstep} |
---|
54 | \begin{spfstep}[type=conclusion] |
---|
55 | Thus $\eq{\card{\livar{V}i},{\atimes[cdot]{2,\card{\livar{V}{i-1}}}},{\atimes[cdot]{2,\power2{i-1}}},\power2i}$. |
---|
56 | \end{spfstep} |
---|
57 | \end{spfcase} |
---|
58 | \end{spfcases} |
---|
59 | \end{sproof} |
---|
60 | \item |
---|
61 | \begin{assertion}[id=fbbt,type=corollary] |
---|
62 | A fully balanced tree of depth $d$ has $\power2{d+1}-1$ nodes. |
---|
63 | \end{assertion} |
---|
64 | \item |
---|
65 | \begin{sproof}[for=fbbt,id=fbbt-pf]{} |
---|
66 | \begin{spfstep} |
---|
67 | Let $\defeq{G}{\tup{V,E}}$ be a fully balanced tree |
---|
68 | \end{spfstep} |
---|
69 | \begin{spfstep} |
---|
70 | Then $\card{V}=\Sumfromto{i}1d{\power2i}= \power2{d+1}-1$. |
---|
71 | \end{spfstep} |
---|
72 | \end{sproof} |
---|
73 | \end{itemize} |
---|
74 | \end{frame} |
---|
75 | \begin{note} |
---|
76 | \begin{omtext}[type=conclusion,for=binary-tree] |
---|
77 | This shows that balanced binary trees grow in breadth very quickly, a consequence of |
---|
78 | this is that they are very shallow (and this compute very fast), which is the essence of |
---|
79 | the next result. |
---|
80 | \end{omtext} |
---|
81 | \end{note} |
---|
82 | \end{module} |
---|
83 | |
---|
84 | %%% Local Variables: |
---|
85 | %%% mode: LaTeX |
---|
86 | %%% TeX-master: "all" |
---|
87 | %%% End: \end{document} |
---|
88 | </textarea></form> |
---|
89 | <script> |
---|
90 | var editor = CodeMirror.fromTextArea(document.getElementById("code"), {}); |
---|
91 | </script> |
---|
92 | |
---|
93 | <p><strong>MIME types defined:</strong> <code>text/stex</code>.</p> |
---|
94 | |
---|
95 | </body> |
---|
96 | </html> |
---|