\section{lib/rbtree/red\-\_\-black\-\_\-tree.h File Reference}
\label{red__black__tree_8h}\index{lib/rbtree/red\-\_\-black\-\_\-tree.\-h@{lib/rbtree/red\-\_\-black\-\_\-tree.\-h}}
{\ttfamily \#include \char`\"{}misc.\-h\char`\"{}}\\*
{\ttfamily \#include \char`\"{}stack.\-h\char`\"{}}\\*
Include dependency graph for red\-\_\-black\-\_\-tree.\-h\-:\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=262pt]{red__black__tree_8h__incl}
\end{center}
\end{figure}
This graph shows which files directly or indirectly include this file\-:\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=254pt]{red__black__tree_8h__dep__incl}
\end{center}
\end{figure}
\subsection*{Data Structures}
\begin{DoxyCompactItemize}
\item 
struct {\bf rb\-\_\-red\-\_\-blk\-\_\-node}
\item 
struct {\bf rb\-\_\-red\-\_\-blk\-\_\-tree}
\end{DoxyCompactItemize}
\subsection*{Typedefs}
\begin{DoxyCompactItemize}
\item 
typedef struct {\bf rb\-\_\-red\-\_\-blk\-\_\-node} {\bf rb\-\_\-red\-\_\-blk\-\_\-node}
\item 
typedef struct {\bf rb\-\_\-red\-\_\-blk\-\_\-tree} {\bf rb\-\_\-red\-\_\-blk\-\_\-tree}
\end{DoxyCompactItemize}
\subsection*{Functions}
\begin{DoxyCompactItemize}
\item 
{\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$ {\bf R\-B\-Tree\-Create} ({\bf int}($\ast$Comp\-Func)(const void $\ast$, const void $\ast$), void($\ast$Dest\-Func)(void $\ast$), void($\ast$Info\-Dest\-Func)(void $\ast$), void($\ast$Print\-Func)(const void $\ast$), void($\ast$Print\-Info)(void $\ast$))
\item 
{\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$ {\bf R\-B\-Tree\-Insert} ({\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$, void $\ast$key, void $\ast${\bf info})
\item 
void {\bf R\-B\-Tree\-Print} ({\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$)
\item 
void {\bf R\-B\-Delete} ({\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$, {\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$)
\item 
void {\bf R\-B\-Tree\-Destroy} ({\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$)
\item 
{\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$ {\bf Tree\-Predecessor} ({\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$, {\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$)
\item 
{\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$ {\bf Tree\-Successor} ({\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$, {\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$)
\item 
{\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$ {\bf R\-B\-Exact\-Query} ({\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$, void $\ast$)
\item 
{\bf stk\-\_\-stack} $\ast$ {\bf R\-B\-Enumerate} ({\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$tree, void $\ast$low, void $\ast$high)
\item 
void {\bf Null\-Function} (void $\ast$)
\end{DoxyCompactItemize}


\subsection{Typedef Documentation}
\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!rb\-\_\-red\-\_\-blk\-\_\-node@{rb\-\_\-red\-\_\-blk\-\_\-node}}
\index{rb\-\_\-red\-\_\-blk\-\_\-node@{rb\-\_\-red\-\_\-blk\-\_\-node}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{rb\-\_\-red\-\_\-blk\-\_\-node}]{\setlength{\rightskip}{0pt plus 5cm}typedef struct {\bf rb\-\_\-red\-\_\-blk\-\_\-node}  {\bf rb\-\_\-red\-\_\-blk\-\_\-node}}\label{red__black__tree_8h_adb14130f53533bcb1b70cd06be14d5aa}
\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!rb\-\_\-red\-\_\-blk\-\_\-tree@{rb\-\_\-red\-\_\-blk\-\_\-tree}}
\index{rb\-\_\-red\-\_\-blk\-\_\-tree@{rb\-\_\-red\-\_\-blk\-\_\-tree}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{rb\-\_\-red\-\_\-blk\-\_\-tree}]{\setlength{\rightskip}{0pt plus 5cm}typedef struct {\bf rb\-\_\-red\-\_\-blk\-\_\-tree}  {\bf rb\-\_\-red\-\_\-blk\-\_\-tree}}\label{red__black__tree_8h_a40b5445fe31b39c46fe6064b2428fc0e}


\subsection{Function Documentation}
\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!Null\-Function@{Null\-Function}}
\index{Null\-Function@{Null\-Function}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{Null\-Function}]{\setlength{\rightskip}{0pt plus 5cm}void Null\-Function (
\begin{DoxyParamCaption}
\item[{void $\ast$}]{}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_a97527e14151a1f6c0575a0c572d90cc6}


Definition at line 72 of file misc.\-c.

\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!R\-B\-Delete@{R\-B\-Delete}}
\index{R\-B\-Delete@{R\-B\-Delete}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{R\-B\-Delete}]{\setlength{\rightskip}{0pt plus 5cm}void R\-B\-Delete (
\begin{DoxyParamCaption}
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$}]{, }
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$}]{}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_ac0558ab75c52cabee6dbc9d413a8315d}


Definition at line 601 of file red\-\_\-black\-\_\-tree.\-c.



References Assert(), rb\-\_\-red\-\_\-blk\-\_\-tree\-::\-Destroy\-Info, rb\-\_\-red\-\_\-blk\-\_\-tree\-::\-Destroy\-Key, if(), rb\-\_\-red\-\_\-blk\-\_\-node\-::info, rb\-\_\-red\-\_\-blk\-\_\-node\-::key, rb\-\_\-red\-\_\-blk\-\_\-node\-::left, rb\-\_\-red\-\_\-blk\-\_\-tree\-::nil, rb\-\_\-red\-\_\-blk\-\_\-node\-::parent, R\-B\-Delete\-Fix\-Up(), rb\-\_\-red\-\_\-blk\-\_\-node\-::red, rb\-\_\-red\-\_\-blk\-\_\-node\-::right, rb\-\_\-red\-\_\-blk\-\_\-tree\-::root, and Tree\-Successor().



Referenced by main().

\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!R\-B\-Enumerate@{R\-B\-Enumerate}}
\index{R\-B\-Enumerate@{R\-B\-Enumerate}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{R\-B\-Enumerate}]{\setlength{\rightskip}{0pt plus 5cm}{\bf stk\-\_\-stack}$\ast$ R\-B\-Enumerate (
\begin{DoxyParamCaption}
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$}]{tree, }
\item[{void $\ast$}]{low, }
\item[{void $\ast$}]{high}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_a966ae2ca51032fffd98e8c497dd7e120}


Definition at line 664 of file red\-\_\-black\-\_\-tree.\-c.



References rb\-\_\-red\-\_\-blk\-\_\-tree\-::\-Compare, rb\-\_\-red\-\_\-blk\-\_\-node\-::key, rb\-\_\-red\-\_\-blk\-\_\-node\-::left, rb\-\_\-red\-\_\-blk\-\_\-tree\-::nil, N\-U\-L\-L, rb\-\_\-jbuf, rb\-\_\-red\-\_\-blk\-\_\-node\-::right, rb\-\_\-red\-\_\-blk\-\_\-tree\-::root, Stack\-Create(), Stack\-Push(), and Tree\-Predecessor().



Referenced by main().

\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!R\-B\-Exact\-Query@{R\-B\-Exact\-Query}}
\index{R\-B\-Exact\-Query@{R\-B\-Exact\-Query}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{R\-B\-Exact\-Query}]{\setlength{\rightskip}{0pt plus 5cm}{\bf rb\-\_\-red\-\_\-blk\-\_\-node}$\ast$ R\-B\-Exact\-Query (
\begin{DoxyParamCaption}
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$}]{, }
\item[{void $\ast$}]{}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_acc3a67c3e60fd309870b5c52badab123}


Definition at line 487 of file red\-\_\-black\-\_\-tree.\-c.



References rb\-\_\-red\-\_\-blk\-\_\-tree\-::\-Compare, rb\-\_\-red\-\_\-blk\-\_\-node\-::key, rb\-\_\-red\-\_\-blk\-\_\-node\-::left, rb\-\_\-red\-\_\-blk\-\_\-tree\-::nil, rb\-\_\-red\-\_\-blk\-\_\-node\-::right, and rb\-\_\-red\-\_\-blk\-\_\-tree\-::root.



Referenced by main().

\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!R\-B\-Tree\-Create@{R\-B\-Tree\-Create}}
\index{R\-B\-Tree\-Create@{R\-B\-Tree\-Create}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{R\-B\-Tree\-Create}]{\setlength{\rightskip}{0pt plus 5cm}{\bf rb\-\_\-red\-\_\-blk\-\_\-tree}$\ast$ R\-B\-Tree\-Create (
\begin{DoxyParamCaption}
\item[{{\bf int}($\ast$)(const void $\ast$, const void $\ast$)}]{Comp\-Func, }
\item[{void($\ast$)(void $\ast$)}]{Dest\-Func, }
\item[{void($\ast$)(void $\ast$)}]{Info\-Dest\-Func, }
\item[{void($\ast$)(const void $\ast$)}]{Print\-Func, }
\item[{void($\ast$)(void $\ast$)}]{Print\-Info}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_a0a75078a9d3fb2c28fd0f68d4351b09c}


Definition at line 33 of file red\-\_\-black\-\_\-tree.\-c.



References rb\-\_\-red\-\_\-blk\-\_\-tree\-::\-Compare, rb\-\_\-red\-\_\-blk\-\_\-tree\-::\-Destroy\-Info, rb\-\_\-red\-\_\-blk\-\_\-tree\-::\-Destroy\-Key, rb\-\_\-red\-\_\-blk\-\_\-node\-::key, rb\-\_\-red\-\_\-blk\-\_\-node\-::left, rb\-\_\-red\-\_\-blk\-\_\-tree\-::nil, N\-U\-L\-L, rb\-\_\-red\-\_\-blk\-\_\-node\-::parent, rb\-\_\-red\-\_\-blk\-\_\-tree\-::\-Print\-Info, rb\-\_\-red\-\_\-blk\-\_\-tree\-::\-Print\-Key, rb\-\_\-jbuf, rb\-\_\-red\-\_\-blk\-\_\-node\-::red, rb\-\_\-red\-\_\-blk\-\_\-node\-::right, rb\-\_\-red\-\_\-blk\-\_\-tree\-::root, and Safe\-Malloc().



Referenced by main().

\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!R\-B\-Tree\-Destroy@{R\-B\-Tree\-Destroy}}
\index{R\-B\-Tree\-Destroy@{R\-B\-Tree\-Destroy}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{R\-B\-Tree\-Destroy}]{\setlength{\rightskip}{0pt plus 5cm}void R\-B\-Tree\-Destroy (
\begin{DoxyParamCaption}
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$}]{}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_aef3a4f43eedd8a1602c9ea40e48d02c6}


Definition at line 446 of file red\-\_\-black\-\_\-tree.\-c.



References rb\-\_\-red\-\_\-blk\-\_\-node\-::left, rb\-\_\-red\-\_\-blk\-\_\-tree\-::nil, rb\-\_\-red\-\_\-blk\-\_\-tree\-::root, and Tree\-Dest\-Helper().



Referenced by main().

\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!R\-B\-Tree\-Insert@{R\-B\-Tree\-Insert}}
\index{R\-B\-Tree\-Insert@{R\-B\-Tree\-Insert}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{R\-B\-Tree\-Insert}]{\setlength{\rightskip}{0pt plus 5cm}{\bf rb\-\_\-red\-\_\-blk\-\_\-node}$\ast$ R\-B\-Tree\-Insert (
\begin{DoxyParamCaption}
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$}]{, }
\item[{void $\ast$}]{key, }
\item[{void $\ast$}]{info}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_a76e49f0050fbe87d6317596b3bedac0a}


Definition at line 242 of file red\-\_\-black\-\_\-tree.\-c.



References Assert(), rb\-\_\-red\-\_\-blk\-\_\-node\-::info, rb\-\_\-red\-\_\-blk\-\_\-node\-::key, rb\-\_\-red\-\_\-blk\-\_\-node\-::left, Left\-Rotate(), rb\-\_\-red\-\_\-blk\-\_\-tree\-::nil, N\-U\-L\-L, rb\-\_\-red\-\_\-blk\-\_\-node\-::parent, rb\-\_\-jbuf, rb\-\_\-red\-\_\-blk\-\_\-node\-::red, rb\-\_\-red\-\_\-blk\-\_\-node\-::right, Right\-Rotate(), rb\-\_\-red\-\_\-blk\-\_\-tree\-::root, Safe\-Malloc(), and Tree\-Insert\-Help().



Referenced by main().

\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!R\-B\-Tree\-Print@{R\-B\-Tree\-Print}}
\index{R\-B\-Tree\-Print@{R\-B\-Tree\-Print}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{R\-B\-Tree\-Print}]{\setlength{\rightskip}{0pt plus 5cm}void R\-B\-Tree\-Print (
\begin{DoxyParamCaption}
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$}]{}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_aba6f16cac1e5431614299144f3644d3e}


Definition at line 468 of file red\-\_\-black\-\_\-tree.\-c.



References Inorder\-Tree\-Print(), rb\-\_\-red\-\_\-blk\-\_\-node\-::left, and rb\-\_\-red\-\_\-blk\-\_\-tree\-::root.



Referenced by main().

\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!Tree\-Predecessor@{Tree\-Predecessor}}
\index{Tree\-Predecessor@{Tree\-Predecessor}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{Tree\-Predecessor}]{\setlength{\rightskip}{0pt plus 5cm}{\bf rb\-\_\-red\-\_\-blk\-\_\-node}$\ast$ Tree\-Predecessor (
\begin{DoxyParamCaption}
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$}]{, }
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$}]{}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_ac6e8723eb2bf61c1a5aa51aa029ce9f5}


Definition at line 349 of file red\-\_\-black\-\_\-tree.\-c.



References rb\-\_\-red\-\_\-blk\-\_\-node\-::left, rb\-\_\-red\-\_\-blk\-\_\-tree\-::nil, rb\-\_\-red\-\_\-blk\-\_\-node\-::parent, rb\-\_\-red\-\_\-blk\-\_\-node\-::right, and rb\-\_\-red\-\_\-blk\-\_\-tree\-::root.



Referenced by main(), and R\-B\-Enumerate().

\index{red\-\_\-black\-\_\-tree.\-h@{red\-\_\-black\-\_\-tree.\-h}!Tree\-Successor@{Tree\-Successor}}
\index{Tree\-Successor@{Tree\-Successor}!red_black_tree.h@{red\-\_\-black\-\_\-tree.\-h}}
\subsubsection[{Tree\-Successor}]{\setlength{\rightskip}{0pt plus 5cm}{\bf rb\-\_\-red\-\_\-blk\-\_\-node}$\ast$ Tree\-Successor (
\begin{DoxyParamCaption}
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-tree} $\ast$}]{, }
\item[{{\bf rb\-\_\-red\-\_\-blk\-\_\-node} $\ast$}]{}
\end{DoxyParamCaption}
)}\label{red__black__tree_8h_ae02133690bdb971d63ee3b6428f1a005}


Definition at line 314 of file red\-\_\-black\-\_\-tree.\-c.



References rb\-\_\-red\-\_\-blk\-\_\-node\-::left, rb\-\_\-red\-\_\-blk\-\_\-tree\-::nil, rb\-\_\-red\-\_\-blk\-\_\-node\-::parent, rb\-\_\-red\-\_\-blk\-\_\-node\-::right, and rb\-\_\-red\-\_\-blk\-\_\-tree\-::root.



Referenced by main(), and R\-B\-Delete().

