Merge branch 'master' of G:\gitroot\writing into algoxy

bhehir · Apr 21, 2011 · 85d383f · 85d383f
2 parents 9882a16 + 2b27f9c
commit 85d383f
Show file tree

Hide file tree

Showing 4 changed files with 25 additions and 6 deletions.
diff --git a/Makefile b/Makefile
@@ -3,9 +3,12 @@ SRC = common-en.tex
 
 all: $(BOOK).pdf
 
+index:
+	makeindex $(BOOK)
+
 $(BOOK).pdf: $(SRC)
 	latex $(BOOK).tex
-	makeindex -o $(BOOK).ind $(BOOK).idx #must have \makeindex in tex file
+	makeindex $(BOOK).idx
 	latex $(BOOK).tex
 	dvipdfmx $(BOOK)
 
@@ -15,5 +18,3 @@ clean:
 distclean: clean
 	rm -f *.pdf *.dvi *~
 
-
-
diff --git a/common-en.tex b/common-en.tex
@@ -39,6 +39,7 @@
 %\usepackage{algorithmic} %old version; we can use algorithmicx instead
 \usepackage{algorithm} 
 \usepackage[noend]{algpseudocode} %for pseudo code, include algorithmicsx automatically
+\usepackage{makeidx} % for index support
 
 
 \lstdefinelanguage{Smalltalk}{

diff --git a/datastruct/tree/binary-search-tree/bstree-en.tex b/datastruct/tree/binary-search-tree/bstree-en.tex
@@ -42,7 +42,7 @@ \chapter{Binary search tree, the `hello world' data structure}
 %                 Introduction
 % ================================================================
 \section{Introduction}
-\label{introduction}
+\label{introduction} \index{binary search tree}
 
 It's typically considered that Arrays or Lists are the `hello world' data structure.
 However, we'll see they are not so easy to implement actually. In some procedural 
@@ -53,7 +53,7 @@ \section{Introduction}
 Considering these factors, we start with Binary Search Tree (or BST) as the `hello world'
 data structure. Jon Bentley mentioned an interesting problem in `programming pearls'
 \cite{Bentley}. The problem is about to count the number of times each word occurs
-in a big text. And the solution is something like the below C++ code.
+in a big text. And the solution is something like the below C++ code.\index{word counter}
 
 \lstset{language=C++}
 \begin{lstlisting}
@@ -88,6 +88,7 @@ \section{Introduction}
 
 The concept of Binary tree is a recursive definition. Binary search tree is just a special 
 type of binary tree. The Binary tree is typically defined as the following.
+\index{binary tree}
 
 A binary tree is 
 \begin{itemize}
@@ -129,6 +130,7 @@ \section{Introduction}
 % Data layout
 % ================================================================
 \section{Data Layout}
+\index{binary search tree!data layout}
 
 Based on the recursive definition of binary search tree, we can draw the 
 data layout in procedural setting with pointer supported as in figure
@@ -205,6 +207,7 @@ \section{Data Layout}
 % Insert
 % ================================================================
 \section{Insertion}
+\index{binary search tree!insertion}
 
 To insert a key $k$ (may be along with a value in practice) to a binary search tree $T$, we can follow a quite straight forward way.
 
@@ -318,6 +321,7 @@ \section{Insertion}
 post for reference.
 
 \section{Traversing}
+\index{binary search tree!traverse}
 
 Traversing means visiting every element one by one in a binary 
 search tree. There are 3 ways to traverse a binary tree, pre-order tree walk, 
@@ -336,6 +340,8 @@ \section{Traversing}
 \item post-order traverse, visit $left$, then $right$, finally $current$.
 \end{itemize}
 
+\index{pre-order traverse} \index{in-order traverse} \index{post-order traverse}
+
 Note that each visiting operation is recursive. And we see the order
 of visiting $current$ determines the name of the traversing method.
 
@@ -492,6 +498,8 @@ \subsection*{Exercise}
 % Querying a binary search tree
 % ================================================================
 \section{Querying a binary search tree}
+\index{binary search tree!search}
+\index{binary search tree!looking up}
 
 There are three types of querying for binary search tree, searching
 a key in the tree, find the minimum or maximum element in the tree,
@@ -577,6 +585,7 @@ \subsection{Looking up}
 \end{lstlisting}
 
 \subsection{Minimum and maximum}
+\index{binary search tree!min/max}
 
 Minimum and maximum can be implemented from the property of binary search
 tree, less keys are always in left child, and greater keys are in right.
@@ -612,6 +621,7 @@ \subsection{Minimum and maximum}
 in pure procedural way without using recursion.
 
 \subsection{Successor and predecessor}
+\index{binary search tree!succ/pred}
 
 The last kind of querying, to find the successor or predecessor of an element
 is useful when a tree is treated as a generic container and traversed by 
@@ -723,6 +733,7 @@ \subsection*{Exercise}
 %                 Deletion
 % ================================================================
 \section{Deletion}
+\index{binary search tree!delete}
 Deletion is another `imperative only' topic for binary search tree.
 This is because deletion mutate the tree, while in purely functional
 settings, we don't modify the tree after building it in most 
@@ -937,6 +948,7 @@ \subsection*{Exercise}
 \end{itemize}
 
 \section{Randomly build binary search tree}
+\index{binary search tree!randomly build}
 It can be found that all operations given in this post bound to $O(h)$
 time for a tree of height $h$. The height affects the performance 
 a lot. For a very unbalanced tree, $h$ tends to be $O(N)$, which leads

diff --git a/main-en.tex b/main-en.tex
@@ -50,11 +50,14 @@
 % ================================================================
 %                 Content
 % ================================================================
-\input{others/preface/preface-en.tex}
+
 %\newpage
 \tableofcontents
 \newpage
 
+\part{Introduction}
+\input{others/preface/preface-en.tex}
+
 \part{Binary search tree}
 \input{datastruct/tree/binary-search-tree/bstree-en.tex}
 
@@ -76,4 +79,6 @@ \part{Binary heaps}
 \part{GNU Free Documentation License}
 \input{fdl-1.3.tex}
 
+\printindex
+
 \end{document}