\hypertarget{classBinarySearchTree}{
\section{Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$ Class Template Reference}
\label{classBinarySearchTree}\index{BinarySearchTree@{BinarySearchTree}}
}
{\tt \#include $<$Binary\-Search\-Tree.hh$>$}

Inheritance diagram for Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[height=2cm]{classBinarySearchTree}
\end{center}
\end{figure}


\subsection{Detailed Description}
\subsubsection*{template$<$typename Key\-Type, typename Value\-Type$>$ class Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$}

The Binary\-Search\-Tree class.



Definition at line 32 of file Binary\-Search\-Tree.hh.\subsection*{Public Types}
\begin{CompactItemize}
\item 
typedef \hyperlink{classDictionaryADT}{Dictionary\-ADT}$<$ Key\-Type, Value\-Type $>$::Entry \hyperlink{classBinarySearchTree_s0}{Entry}
\begin{CompactList}\small\item\em A local typedef of the \hyperlink{classDictionaryADT_s0}{Dictionary\-ADT::Entry} mainly kept here for for documentation purposes.\item\end{CompactList}\item 
typedef \hyperlink{classDictionaryADT}{Dictionary\-ADT}$<$ Key\-Type, Value\-Type $>$::Entry\-List \hyperlink{classBinarySearchTree_s1}{Entry\-List}
\begin{CompactList}\small\item\em A local typedef of the \hyperlink{classDictionaryADT_s1}{Dictionary\-ADT::Entry\-List} mainly kept here for for documentation purposes.\item\end{CompactList}\item 
typedef \hyperlink{structBSTNode}{BSTNode}$<$ \hyperlink{classBinarySearchTree_s0}{Entry} $>$ \hyperlink{classBinarySearchTree_s2}{Node}
\begin{CompactList}\small\item\em Typedef for the type of ndoe used by this BST.\item\end{CompactList}\end{CompactItemize}
\subsection*{Public Methods}
\begin{CompactItemize}
\item 
\hyperlink{classBinarySearchTree_a0}{Binary\-Search\-Tree} (void)
\begin{CompactList}\small\item\em (1) Default constructor.\item\end{CompactList}\item 
\hyperlink{classBinarySearchTree_a1}{Binary\-Search\-Tree} (const Binary\-Search\-Tree \&other)
\begin{CompactList}\small\item\em (2) Copy constructor.\item\end{CompactList}\item 
Binary\-Search\-Tree \& \hyperlink{classBinarySearchTree_a2}{operator=} (const Binary\-Search\-Tree \&other)
\begin{CompactList}\small\item\em (3) Assign Op.\item\end{CompactList}\item 
virtual \hyperlink{classBinarySearchTree_a3}{$\sim$Binary\-Search\-Tree} (void)
\begin{CompactList}\small\item\em (4) Destructor.\item\end{CompactList}\item 
virtual int \hyperlink{classBinarySearchTree_a4}{get\-Size} (void) const
\begin{CompactList}\small\item\em Returns the number of elements in the BST.\item\end{CompactList}\item 
virtual bool \hyperlink{classBinarySearchTree_a5}{find} (const Key\-Type \&key, Value\-Type \&value) const
\begin{CompactList}\small\item\em Given a key, 'returns' (via a reference parameter) the value associated with it in this BST.\item\end{CompactList}\item 
virtual int \hyperlink{classBinarySearchTree_a6}{get\-Entry\-List} (\hyperlink{classBinarySearchTree_s1}{Entry\-List} \&entries) const
\begin{CompactList}\small\item\em \char`\"{}Returns\char`\"{} a list of all the Key/Value pairs in the tree.\item\end{CompactList}\item 
virtual std::ostream \& \hyperlink{classBinarySearchTree_a7}{print} (std::ostream \&out=std::cerr) const
\begin{CompactList}\small\item\em Pretty-Print out a view of this Dictionary for debugging purposes.\item\end{CompactList}\item 
virtual bool \hyperlink{classBinarySearchTree_a8}{insert} (const Key\-Type \&new\-Key, const Value\-Type \&new\-Value)
\begin{CompactList}\small\item\em Inserts a new key/value pair into the BST.\item\end{CompactList}\item 
virtual bool \hyperlink{classBinarySearchTree_a9}{change\-Value} (const Key\-Type \&old\-Key, const Value\-Type \&new\-Value)
\begin{CompactList}\small\item\em Changes the value associated with an existing key in the BST (old\-Key) to a new value.\item\end{CompactList}\item 
virtual bool \hyperlink{classBinarySearchTree_a10}{insert} (const \hyperlink{classBinarySearchTree_s0}{Entry} \&entry)
\begin{CompactList}\small\item\em Same as the the other {\tt insert} function, but takes an {\tt Entry} rather than seperate key and value arguments.\item\end{CompactList}\item 
virtual bool \hyperlink{classBinarySearchTree_a11}{change\-Value} (const \hyperlink{classBinarySearchTree_s0}{Entry} \&entry)
\begin{CompactList}\small\item\em Same as the the other {\tt Change\-Value} function, but takes an {\tt Entry} rather than seperate key and value argument.\item\end{CompactList}\end{CompactItemize}
\subsection*{Protected Methods}
\begin{CompactItemize}
\item 
virtual \hyperlink{classBinarySearchTree_s2}{Node} $\ast$ \hyperlink{classBinarySearchTree_b0}{find\-Node} (const Key\-Type \&key) const
\begin{CompactList}\small\item\em Finds the node associated with a given key.\item\end{CompactList}\item 
virtual int \hyperlink{classBinarySearchTree_b1}{recursive\-Get\-Entry\-List} (\hyperlink{classBinarySearchTree_s1}{Entry\-List} \&entries, \hyperlink{classBinarySearchTree_s2}{Node} $\ast$p\-Curr\-Node) const
\begin{CompactList}\small\item\em Recursively copies the key/value pairs in the tree rooted at p\-Curr\-Node into the Entry\-List.\item\end{CompactList}\item 
virtual \hyperlink{classBinarySearchTree_s2}{Node} $\ast$ \hyperlink{classBinarySearchTree_b2}{clone\-Tree} (const \hyperlink{classBinarySearchTree_s2}{Node} $\ast$const p\-Root)
\begin{CompactList}\small\item\em Recursively copy the tree rooted at p\-Root, returning a pointer to the newly copied subtree.\item\end{CompactList}\item 
virtual void \hyperlink{classBinarySearchTree_b3}{destroy\-Tree} (\hyperlink{classBinarySearchTree_s2}{Node} $\ast$const p\-Root)
\begin{CompactList}\small\item\em Deallocates memory for the tree rooted at p\-Root.\item\end{CompactList}\end{CompactItemize}
\subsection*{Protected Attributes}
\begin{CompactItemize}
\item 
\hyperlink{classBinarySearchTree_s2}{Node} $\ast$ \hyperlink{classBinarySearchTree_n0}{m\_\-p\-Root}
\begin{CompactList}\small\item\em The root of the BST.\item\end{CompactList}\item 
int \hyperlink{classBinarySearchTree_n1}{m\_\-num\-Elts}
\begin{CompactList}\small\item\em The number of elements in the BST.\item\end{CompactList}\end{CompactItemize}


\subsection{Member Typedef Documentation}
\hypertarget{classBinarySearchTree_s0}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!Entry@{Entry}}
\index{Entry@{Entry}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[Entry]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ template Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Entry}}
\label{classBinarySearchTree_s0}


A local typedef of the \hyperlink{classDictionaryADT_s0}{Dictionary\-ADT::Entry} mainly kept here for for documentation purposes.

Used to represent Key/Value pairs. 

Reimplemented from \hyperlink{classDictionaryADT_s0}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 49 of file Binary\-Search\-Tree.hh.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::change\-Value(), and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::insert().\hypertarget{classBinarySearchTree_s1}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!EntryList@{EntryList}}
\index{EntryList@{EntryList}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[EntryList]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ template Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Entry\-List}}
\label{classBinarySearchTree_s1}


A local typedef of the \hyperlink{classDictionaryADT_s1}{Dictionary\-ADT::Entry\-List} mainly kept here for for documentation purposes.

Used by {\tt \hyperlink{classBinarySearchTree_a6}{get\-Entry\-List}()}. 

Reimplemented from \hyperlink{classDictionaryADT_s1}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 53 of file Binary\-Search\-Tree.hh.\hypertarget{classBinarySearchTree_s2}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!Node@{Node}}
\index{Node@{Node}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[Node]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ template Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Node}}
\label{classBinarySearchTree_s2}


Typedef for the type of ndoe used by this BST.

Useful layer of  abstraction that allows a bit more flexibility in changing underly class for each node. (For instance, if you wanted to template the node on an additional parameter, you only have to change this typedef). 

Definition at line 59 of file Binary\-Search\-Tree.hh.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::insert().

\subsection{Constructor \& Destructor Documentation}
\hypertarget{classBinarySearchTree_a0}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!BinarySearchTree@{BinarySearchTree}}
\index{BinarySearchTree@{BinarySearchTree}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[BinarySearchTree]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Binary\-Search\-Tree (void)}}
\label{classBinarySearchTree_a0}


(1) Default constructor.

Constructs an empty tree. 

Definition at line 26 of file Binary\-Search\-Tree.cc.\hypertarget{classBinarySearchTree_a1}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!BinarySearchTree@{BinarySearchTree}}
\index{BinarySearchTree@{BinarySearchTree}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[BinarySearchTree]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Binary\-Search\-Tree (const Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$ \& {\em other})}}
\label{classBinarySearchTree_a1}


(2) Copy constructor.

Constructs a new tree that is a copy of the given tree.\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
other}]The tree to copy. \end{description}
\end{Desc}


Definition at line 36 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::clone\-Tree(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-num\-Elts, and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-p\-Root.\hypertarget{classBinarySearchTree_a3}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!~BinarySearchTree@{$\sim$BinarySearchTree}}
\index{~BinarySearchTree@{$\sim$BinarySearchTree}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[$\sim$BinarySearchTree]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::$\sim$Binary\-Search\-Tree (void)\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{classBinarySearchTree_a3}


(4) Destructor.

Note that the destructor is declared virtual in this inheritance tree. Why do you think this is necessary? 

Definition at line 63 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::destroy\-Tree(), and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-p\-Root.

\subsection{Member Function Documentation}
\hypertarget{classBinarySearchTree_a11}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!changeValue@{changeValue}}
\index{changeValue@{changeValue}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[changeValue]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ bool Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::change\-Value (const \hyperlink{classBinarySearchTree_s0}{Entry} \& {\em entry})\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{classBinarySearchTree_a11}


Same as the the other {\tt Change\-Value} function, but takes an {\tt Entry} rather than seperate key and value argument.

\begin{Desc}
\item[Returns :]\par
{\tt true} if the data was changed,  {\tt false} otherwise.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
entry}]The entry representing the key/value information  to be changed in the BST. \end{description}
\end{Desc}


Implements \hyperlink{classDictionaryADT_a7}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 214 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::find\-Node(), and BSTNode$<$ Entry $>$::m\_\-data.\hypertarget{classBinarySearchTree_a9}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!changeValue@{changeValue}}
\index{changeValue@{changeValue}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[changeValue]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ bool Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::change\-Value (const Key\-Type \& {\em old\-Key}, const Value\-Type \& {\em new\-Value})\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{classBinarySearchTree_a9}


Changes the value associated with an existing key in the BST (old\-Key) to a new value.

Assumes 'old\-Key' exists in  the BST.

\begin{Desc}
\item[Returns :]\par
{\tt true} if the data was changed,  {\tt false} otherwise.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
old\-Key}]The key whose value will be changed. \item[{\em 
new\-Value}]The new value to be associated with {\tt old\-Key}. \end{description}
\end{Desc}


Implements \hyperlink{classDictionaryADT_a5}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 145 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Entry.

Referenced by main().\hypertarget{classBinarySearchTree_b2}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!cloneTree@{cloneTree}}
\index{cloneTree@{cloneTree}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[cloneTree]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::\hyperlink{classBinarySearchTree_s2}{Node} $\ast$ Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::clone\-Tree (const \hyperlink{classBinarySearchTree_s2}{Node} $\ast$const {\em p\-Root})\hspace{0.3cm}{\tt  \mbox{[}protected, virtual\mbox{]}}}}
\label{classBinarySearchTree_b2}


Recursively copy the tree rooted at p\-Root, returning a pointer to the newly copied subtree.

Does $\ast$not$\ast$  deallocate any memory.

\begin{Desc}
\item[Returns :]\par
A pointer to the newly allocated clone of  the subtree.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
p\-Root}]The root of the subtree to clone \end{description}
\end{Desc}


Definition at line 315 of file Binary\-Search\-Tree.cc.

References BSTNode$<$ Entry $>$::clone(), BSTNode$<$ Entry $>$::m\_\-p\-Left, BSTNode$<$ Data\-Type $>$::m\_\-p\-Parent, and BSTNode$<$ Entry $>$::m\_\-p\-Right.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Binary\-Search\-Tree(), and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::operator=().\hypertarget{classBinarySearchTree_b3}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!destroyTree@{destroyTree}}
\index{destroyTree@{destroyTree}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[destroyTree]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ void Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::destroy\-Tree (\hyperlink{classBinarySearchTree_s2}{Node} $\ast$const {\em p\-Root})\hspace{0.3cm}{\tt  \mbox{[}protected, virtual\mbox{]}}}}
\label{classBinarySearchTree_b3}


Deallocates memory for the tree rooted at p\-Root.

\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
p\-Root}]The root of the tree to desctroy. \end{description}
\end{Desc}


Definition at line 348 of file Binary\-Search\-Tree.cc.

References BSTNode$<$ Entry $>$::m\_\-p\-Left, and BSTNode$<$ Entry $>$::m\_\-p\-Right.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::operator=(), and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::$\sim$Binary\-Search\-Tree().\hypertarget{classBinarySearchTree_a5}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!find@{find}}
\index{find@{find}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[find]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ bool Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::find (const Key\-Type \& {\em key}, Value\-Type \& {\em value}) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{classBinarySearchTree_a5}


Given a key, 'returns' (via a reference parameter) the value associated with it in this BST.

\begin{Desc}
\item[Returns :]\par
{\tt true} if the key is in the BST,  {\tt false} otherwise. If the key is not in the  BST, the value of {\tt value} is undefined.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
key}]The key to search for. \item[{\em 
value}]output parameter to hold a copy of the value for the given key. \end{description}
\end{Desc}


Implements \hyperlink{classDictionaryADT_a2}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 80 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::find\-Node(), and BSTNode$<$ Entry $>$::m\_\-data.

Referenced by main().\hypertarget{classBinarySearchTree_b0}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!findNode@{findNode}}
\index{findNode@{findNode}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[findNode]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::\hyperlink{classBinarySearchTree_s2}{Node} $\ast$ Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::find\-Node (const Key\-Type \& {\em key}) const\hspace{0.3cm}{\tt  \mbox{[}protected, virtual\mbox{]}}}}
\label{classBinarySearchTree_b0}


Finds the node associated with a given key.

If the key is  not in the tree, returns {\tt NULL} if the tree is empty;  otherwise, returns the parent of where $<$cdoe$>$key} should be.

\begin{Desc}
\item[Returns :]\par
{\tt NULL} if the tree is empty. The node  represeting the key if it exist, or the \char`\"{}parent\char`\"{} of  where the node with the {\tt key} should  have been.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
key}]The key to search for. \end{description}
\end{Desc}


Definition at line 237 of file Binary\-Search\-Tree.cc.

References BSTNode$<$ Entry $>$::m\_\-data, BSTNode$<$ Entry $>$::m\_\-p\-Left, BSTNode$<$ Entry $>$::m\_\-p\-Right, and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-p\-Root.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::change\-Value(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::find(), and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::insert().\hypertarget{classBinarySearchTree_a6}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!getEntryList@{getEntryList}}
\index{getEntryList@{getEntryList}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[getEntryList]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ int Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::get\-Entry\-List (\hyperlink{classBinarySearchTree_s1}{Entry\-List} \& {\em entries}) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{classBinarySearchTree_a6}


\char`\"{}Returns\char`\"{} a list of all the Key/Value pairs in the tree.

The  values will be in $\ast$sorted order$\ast$, since this is a BST and the list is generated using an inorder traversal.

\begin{Desc}
\item[Returns :]\par
an int specifying the number of elements in the arrays.  -1 if there was an error.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
entries}]output parameter that holds the list of key/value pairs in the BST. The original contents of  the list is erased. \end{description}
\end{Desc}


Implements \hyperlink{classDictionaryADT_a3}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 123 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::get\-Size(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-p\-Root, and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::recursive\-Get\-Entry\-List().

Referenced by main().\hypertarget{classBinarySearchTree_a4}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!getSize@{getSize}}
\index{getSize@{getSize}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[getSize]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ int Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::get\-Size (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{classBinarySearchTree_a4}


Returns the number of elements in the BST.

\begin{Desc}
\item[Returns :]\par
the number of elements in the BST. \end{Desc}


Implements \hyperlink{classDictionaryADT_a1}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 72 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-num\-Elts.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::get\-Entry\-List(), and main().\hypertarget{classBinarySearchTree_a10}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!insert@{insert}}
\index{insert@{insert}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[insert]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ bool Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::insert (const \hyperlink{classBinarySearchTree_s0}{Entry} \& {\em entry})\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{classBinarySearchTree_a10}


Same as the the other {\tt insert} function, but takes an {\tt Entry} rather than seperate key and value arguments.

\begin{Desc}
\item[Returns :]\par
{\tt true} if this key did not previously exist  in the tree, {\tt false} otherwise.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
entry}]The new key/value pair to be inserted into the  BST. \end{description}
\end{Desc}


Implements \hyperlink{classDictionaryADT_a6}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 166 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::find\-Node(), BSTNode$<$ Entry $>$::m\_\-data, Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-num\-Elts, BSTNode$<$ Entry $>$::m\_\-p\-Left, BSTNode$<$ Entry $>$::m\_\-p\-Right, Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-p\-Root, and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Node.\hypertarget{classBinarySearchTree_a8}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!insert@{insert}}
\index{insert@{insert}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[insert]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ bool Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::insert (const Key\-Type \& {\em new\-Key}, const Value\-Type \& {\em new\-Value})\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{classBinarySearchTree_a8}


Inserts a new key/value pair into the BST.

If the key previously  existed in the BST, will overwrite the old value with  the new value.

\begin{Desc}
\item[Returns :]\par
{\tt true} if this key did not previously exist  in the tree, {\tt false} otherwise.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
new\-Key}]The new key with which {\tt new\-Value} will be associated. \item[{\em 
new\-Value}]the value to be associated with {\tt new\-Key}. \end{description}
\end{Desc}


Implements \hyperlink{classDictionaryADT_a4}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 155 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Entry.

Referenced by main().\hypertarget{classBinarySearchTree_a2}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!operator=@{operator=}}
\index{operator=@{operator=}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[operator=]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$ \& Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::operator= (const Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$ \& {\em other})}}
\label{classBinarySearchTree_a2}


(3) Assign Op.

Copies the contents of another BST to this BST.

\begin{Desc}
\item[Returns :]\par
returns a reference to $\ast$this$\ast$ BST. So stuff like (a=b).insert(3,4) inserts int BST a. This is the standard C/C++ semantics for assignment.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
other}]The tree to copy. \end{description}
\end{Desc}


Definition at line 48 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::clone\-Tree(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::destroy\-Tree(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-num\-Elts, and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-p\-Root.\hypertarget{classBinarySearchTree_a7}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!print@{print}}
\index{print@{print}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[print]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ ostream \& Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::print (std::ostream \& {\em out} = std::cerr) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{classBinarySearchTree_a7}


Pretty-Print out a view of this Dictionary for debugging purposes.

This code requires operator$<$$<$ for both Key\-Type and Value\-Type, so  you can remove this if you're not debugging. You can \char`\"{}turn off\char`\"{} printing by compiling in \char`\"{}release mode\char`\"{} (ie, by defining \char`\"{}NDEBUG\char`\"{})

\begin{Desc}
\item[Returns :]\par
The ostream used by the print function. This is  mainly a convienience thing.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
out}]The output stream to pretty-print the Dictionary to. This funciton defaults to cerr. \end{description}
\end{Desc}


Implements \hyperlink{classDictionaryADT_a8}{Dictionary\-ADT$<$ Key\-Type, Value\-Type $>$}.

Definition at line 102 of file Binary\-Search\-Tree.cc.

References Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-p\-Root, and BSTNode$<$ Entry $>$::print().

Referenced by main().\hypertarget{classBinarySearchTree_b1}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!recursiveGetEntryList@{recursiveGetEntryList}}
\index{recursiveGetEntryList@{recursiveGetEntryList}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[recursiveGetEntryList]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ int Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::recursive\-Get\-Entry\-List (\hyperlink{classBinarySearchTree_s1}{Entry\-List} \& {\em entries}, \hyperlink{classBinarySearchTree_s2}{Node} $\ast$ {\em p\-Curr\-Node}) const\hspace{0.3cm}{\tt  \mbox{[}protected, virtual\mbox{]}}}}
\label{classBinarySearchTree_b1}


Recursively copies the key/value pairs in the tree rooted at p\-Curr\-Node into the Entry\-List.

The copying is done via an in-order  traversal of the subtrees rooted at p\-Curr\-Node (thus, the data in  the arrays will be ordered by key value). Does nothing if  p\-Curr\-Node == {\tt NULL}.

\begin{Desc}
\item[Returns :]\par
The number of valid items in the list.\end{Desc}
\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
entries}]The Entry\-List to populate with the key/value pairs\item[{\em 
p\-Curr\-Node}]The current node in the inorder traversal \end{description}
\end{Desc}


Definition at line 276 of file Binary\-Search\-Tree.cc.

References BSTNode$<$ Entry $>$::is\-Leaf(), BSTNode$<$ Entry $>$::m\_\-data, BSTNode$<$ Entry $>$::m\_\-p\-Left, and BSTNode$<$ Entry $>$::m\_\-p\-Right.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::get\-Entry\-List().

\subsection{Member Data Documentation}
\hypertarget{classBinarySearchTree_n1}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!m_numElts@{m\_\-numElts}}
\index{m_numElts@{m\_\-numElts}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[m\_\-numElts]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ int Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-num\-Elts\hspace{0.3cm}{\tt  \mbox{[}protected\mbox{]}}}}
\label{classBinarySearchTree_n1}


The number of elements in the BST.



Definition at line 291 of file Binary\-Search\-Tree.hh.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Binary\-Search\-Tree(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::get\-Size(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::insert(), and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::operator=().\hypertarget{classBinarySearchTree_n0}{
\index{BinarySearchTree@{Binary\-Search\-Tree}!m_pRoot@{m\_\-pRoot}}
\index{m_pRoot@{m\_\-pRoot}!BinarySearchTree@{Binary\-Search\-Tree}}
\subsubsection[m\_\-pRoot]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Key\-Type, typename Value\-Type$>$ \hyperlink{classBinarySearchTree_s2}{Node}$\ast$ Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::m\_\-p\-Root\hspace{0.3cm}{\tt  \mbox{[}protected\mbox{]}}}}
\label{classBinarySearchTree_n0}


The root of the BST.

What is a \char`\"{}mutable\char`\"{} data member? It's a  data member that can be modified $>$$>$even if the instance of this  class is declared const$<$$<$! This has one very important effect: This data member can be modifed by any class method, even if the method is declared 'const'! The reason the root pointer is declared mutable will become important when we look at Splay\-Tree::Find() and Splay\-Tree::Splay() 

Definition at line 288 of file Binary\-Search\-Tree.hh.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::Binary\-Search\-Tree(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::find\-Node(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::get\-Entry\-List(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::insert(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::operator=(), Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::print(), and Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::$\sim$Binary\-Search\-Tree().

The documentation for this class was generated from the following files:\begin{CompactItemize}
\item 
\hyperlink{BinarySearchTree_8hh}{Binary\-Search\-Tree.hh}\item 
\hyperlink{BinarySearchTree_8cc}{Binary\-Search\-Tree.cc}\item 
\hyperlink{BSTInst_8cc}{BSTInst.cc}\end{CompactItemize}
