\section{Red\_\-black\_\-tree.h File Reference}
\label{Red__black__tree_8h}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}}


This graph shows which files directly or indirectly include this file:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=96pt]{Red__black__tree_8h__dep__incl}
\end{center}
\end{figure}
\subsection*{Data Structures}
\begin{CompactItemize}
\item 
struct {\bf red\_\-black\_\-node}
\item 
struct {\bf red\_\-black\_\-tree}
\end{CompactItemize}
\subsection*{Typedefs}
\begin{CompactItemize}
\item 
typedef enum {\bf red\_\-black\_\-color} {\bf Red\_\-black\_\-color}
\item 
typedef {\bf red\_\-black\_\-node} {\bf Red\_\-black\_\-node}
\item 
typedef int( {\bf Comp} )(void $\ast$, void $\ast$)
\item 
typedef void( {\bf Op} )(void $\ast$)
\item 
typedef {\bf red\_\-black\_\-tree} {\bf Red\_\-black\_\-tree}
\end{CompactItemize}
\subsection*{Enumerations}
\begin{CompactItemize}
\item 
enum {\bf red\_\-black\_\-color} \{ {\bf Red}, 
{\bf Black}
 \}
\end{CompactItemize}
\subsection*{Functions}
\begin{CompactItemize}
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbnode\_\-construct} (void $\ast$object, {\bf Red\_\-black\_\-color} color)
\item 
void {\bf rbnode\_\-destruct} ({\bf Red\_\-black\_\-node} $\ast$node)
\item 
int {\bf rbnode\_\-depth} ({\bf Red\_\-black\_\-node} $\ast$node)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbnode\_\-minimum} ({\bf Red\_\-black\_\-node} $\ast$node)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbnode\_\-maximum} ({\bf Red\_\-black\_\-node} $\ast$node)
\item 
void {\bf rbnode\_\-replace} ({\bf Red\_\-black\_\-node} $\ast$node, void $\ast$object)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbnode\_\-successor} ({\bf Red\_\-black\_\-node} $\ast$node)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbnode\_\-predecessor} ({\bf Red\_\-black\_\-node} $\ast$node)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbnode\_\-duplicate} ({\bf Red\_\-black\_\-node} $\ast$node)
\item 
void {\bf rbnode\_\-traverse} ({\bf Red\_\-black\_\-node} $\ast$node, {\bf Op} $\ast$op)
\item 
void {\bf rbtree\_\-init} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Comp} $\ast$comp)
\item 
{\bf Red\_\-black\_\-tree} $\ast$ {\bf rbtree\_\-construct} ({\bf Comp} $\ast$comp)
\item 
void {\bf rbtree\_\-clean} ({\bf Red\_\-black\_\-tree} $\ast$tree)
\item 
void {\bf rbtree\_\-destruct} ({\bf Red\_\-black\_\-tree} $\ast$tree)
\item 
int {\bf rbtree\_\-size} ({\bf Red\_\-black\_\-tree} $\ast$tree)
\item 
int {\bf rbtree\_\-depth} ({\bf Red\_\-black\_\-tree} $\ast$tree)
\item 
int {\bf rbtree\_\-contains} ({\bf Red\_\-black\_\-tree} $\ast$tree, void $\ast$object)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbtree\_\-insert} ({\bf Red\_\-black\_\-tree} $\ast$tree, void $\ast$object)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf insert\_\-successor\_\-at} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Red\_\-black\_\-node} $\ast$at\_\-node, void $\ast$object)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf insert\_\-predecessor\_\-at} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Red\_\-black\_\-node} $\ast$at\_\-node, void $\ast$object)
\item 
void {\bf rbtree\_\-remove} ({\bf Red\_\-black\_\-tree} $\ast$tree, void $\ast$object)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbtree\_\-minimum} ({\bf Red\_\-black\_\-tree} $\ast$tree)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbtree\_\-maximum} ({\bf Red\_\-black\_\-tree} $\ast$tree)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbtree\_\-successor} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Red\_\-black\_\-node} $\ast$node)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbtree\_\-predecessor} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Red\_\-black\_\-node} $\ast$node)
\item 
{\bf Red\_\-black\_\-node} $\ast$ {\bf rbtree\_\-find} ({\bf Red\_\-black\_\-tree} $\ast$tree, void $\ast$object)
\item 
void {\bf rbtree\_\-remove\_\-at} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Red\_\-black\_\-node} $\ast$node)
\item 
void {\bf rbtree\_\-rotate\_\-left} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Red\_\-black\_\-node} $\ast$node)
\item 
void {\bf rbtree\_\-rotate\_\-right} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Red\_\-black\_\-node} $\ast$node)
\item 
void {\bf rbtree\_\-insert\_\-fixup} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Red\_\-black\_\-node} $\ast$node)
\item 
void {\bf rbtree\_\-remove\_\-fixup} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Red\_\-black\_\-node} $\ast$node)
\item 
void {\bf rbtree\_\-traverse} ({\bf Red\_\-black\_\-tree} $\ast$tree, {\bf Op} $\ast$op)
\end{CompactItemize}


\subsection{Typedef Documentation}
\index{Comp@{Comp}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Comp@{Comp}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Comp@{Comp}}
\index{Comp@{Comp}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef int( Comp)(void $\ast$, void $\ast$)}\label{Red__black__tree_8h_a2}


\index{Op@{Op}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Op@{Op}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Op@{Op}}
\index{Op@{Op}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef void( Op)(void $\ast$)}\label{Red__black__tree_8h_a3}


\index{Red_black_color@{Red\_\-black\_\-color}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Red_black_color@{Red\_\-black\_\-color}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Red_black_color@{Red\_\-black\_\-color}}
\index{Red_black_color@{Red\_\-black\_\-color}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef enum {\bf red\_\-black\_\-color}  Red\_\-black\_\-color}\label{Red__black__tree_8h_a0}


Color enumeration for nodes of red-black tree \index{Red_black_node@{Red\_\-black\_\-node}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Red_black_node@{Red\_\-black\_\-node}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Red_black_node@{Red\_\-black\_\-node}}
\index{Red_black_node@{Red\_\-black\_\-node}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef struct {\bf red\_\-black\_\-node}  Red\_\-black\_\-node}\label{Red__black__tree_8h_a1}


Representation of a node in a red-black tree \index{Red_black_tree@{Red\_\-black\_\-tree}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Red_black_tree@{Red\_\-black\_\-tree}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Red_black_tree@{Red\_\-black\_\-tree}}
\index{Red_black_tree@{Red\_\-black\_\-tree}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef struct {\bf red\_\-black\_\-tree}  Red\_\-black\_\-tree}\label{Red__black__tree_8h_a4}


Representation of a red-black tree 

\subsection{Enumeration Type Documentation}
\index{red_black_color@{red\_\-black\_\-color}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!red_black_color@{red\_\-black\_\-color}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!red_black_color@{red\_\-black\_\-color}}
\index{red_black_color@{red\_\-black\_\-color}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}enum red\_\-black\_\-color}\label{Red__black__tree_8h_a39}


Color enumeration for nodes of red-black tree \begin{Desc}
\item[Enumeration values: ]\par
\begin{description}
\index{Red@{Red}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Red@{Red}}\item[{\em 
{\em Red}\label{Red__black__tree_8h_a39a5}
}]\index{Black@{Black}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!Black@{Black}}\item[{\em 
{\em Black}\label{Red__black__tree_8h_a39a6}
}]\end{description}
\end{Desc}



\subsection{Function Documentation}
\index{insert_predecessor_at@{insert\_\-predecessor\_\-at}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!insert_predecessor_at@{insert\_\-predecessor\_\-at}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!insert_predecessor_at@{insert\_\-predecessor\_\-at}}
\index{insert_predecessor_at@{insert\_\-predecessor\_\-at}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ insert\_\-predecessor\_\-at ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Red\_\-black\_\-node} $\ast$ {\em at\_\-node}, void $\ast$ {\em object})}\label{Red__black__tree_8h_a26}


Insert a new object to the tree as the a predecessor of a given node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em at\_\-node}]The node to be preceded \item[{\em object}]The new object \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The new node \end{Desc}
\index{insert_successor_at@{insert\_\-successor\_\-at}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!insert_successor_at@{insert\_\-successor\_\-at}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!insert_successor_at@{insert\_\-successor\_\-at}}
\index{insert_successor_at@{insert\_\-successor\_\-at}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ insert\_\-successor\_\-at ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Red\_\-black\_\-node} $\ast$ {\em at\_\-node}, void $\ast$ {\em object})}\label{Red__black__tree_8h_a25}


Insert a new object to the tree as the a successor of a given node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em at\_\-node}]The node to be succeeded \item[{\em object}]The new object \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The new node \end{Desc}
\index{rbnode_construct@{rbnode\_\-construct}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_construct@{rbnode\_\-construct}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_construct@{rbnode\_\-construct}}
\index{rbnode_construct@{rbnode\_\-construct}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbnode\_\-construct (void $\ast$ {\em object}, {\bf Red\_\-black\_\-color} {\em color})}\label{Red__black__tree_8h_a7}


Construct of a red-black tree node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em object}]The object stored in the node \item[{\em color}]The color of the node \end{description}
\end{Desc}
\index{rbnode_depth@{rbnode\_\-depth}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_depth@{rbnode\_\-depth}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_depth@{rbnode\_\-depth}}
\index{rbnode_depth@{rbnode\_\-depth}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}int rbnode\_\-depth ({\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a9}


Calculate the depth of the sub-tree spanned by the given node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em node}]The sub-tree root \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The sub-tree depth \end{Desc}
\index{rbnode_destruct@{rbnode\_\-destruct}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_destruct@{rbnode\_\-destruct}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_destruct@{rbnode\_\-destruct}}
\index{rbnode_destruct@{rbnode\_\-destruct}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbnode\_\-destruct ({\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a8}


Recursive destructor for the entire sub-tree \index{rbnode_duplicate@{rbnode\_\-duplicate}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_duplicate@{rbnode\_\-duplicate}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_duplicate@{rbnode\_\-duplicate}}
\index{rbnode_duplicate@{rbnode\_\-duplicate}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbnode\_\-duplicate ({\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a15}


Duplicate the entire sub-tree rooted at the given node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em node}]The sub-tree root \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]A pointer to the duplicated sub-tree root \end{Desc}
\index{rbnode_maximum@{rbnode\_\-maximum}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_maximum@{rbnode\_\-maximum}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_maximum@{rbnode\_\-maximum}}
\index{rbnode_maximum@{rbnode\_\-maximum}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbnode\_\-maximum ({\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a11}


Get the rightmost node in the sub-tree spanned by the given node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em node}]The sub-tree root \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The sub-tree maximum \end{Desc}
\index{rbnode_minimum@{rbnode\_\-minimum}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_minimum@{rbnode\_\-minimum}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_minimum@{rbnode\_\-minimum}}
\index{rbnode_minimum@{rbnode\_\-minimum}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbnode\_\-minimum ({\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a10}


Get the leftmost node in the sub-tree spanned by the given node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em node}]The sub-tree root \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The sub-tree minimum \end{Desc}
\index{rbnode_predecessor@{rbnode\_\-predecessor}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_predecessor@{rbnode\_\-predecessor}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_predecessor@{rbnode\_\-predecessor}}
\index{rbnode_predecessor@{rbnode\_\-predecessor}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbnode\_\-predecessor ({\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a14}


Get the previous node in the tree (according to the tree order) \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em node}]The current node \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The predecessor node, or NULL if node is the tree minimum \end{Desc}
\index{rbnode_replace@{rbnode\_\-replace}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_replace@{rbnode\_\-replace}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_replace@{rbnode\_\-replace}}
\index{rbnode_replace@{rbnode\_\-replace}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbnode\_\-replace ({\bf Red\_\-black\_\-node} $\ast$ {\em node}, void $\ast$ {\em object})}\label{Red__black__tree_8h_a12}


Replace the object \index{rbnode_successor@{rbnode\_\-successor}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_successor@{rbnode\_\-successor}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_successor@{rbnode\_\-successor}}
\index{rbnode_successor@{rbnode\_\-successor}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbnode\_\-successor ({\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a13}


Get the next node in the tree (according to the tree order) \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em node}]The current node \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The successor node, or NULL if node is the tree maximum \end{Desc}
\index{rbnode_traverse@{rbnode\_\-traverse}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_traverse@{rbnode\_\-traverse}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbnode_traverse@{rbnode\_\-traverse}}
\index{rbnode_traverse@{rbnode\_\-traverse}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbnode\_\-traverse ({\bf Red\_\-black\_\-node} $\ast$ {\em node}, {\bf Op} $\ast$ {\em op})}\label{Red__black__tree_8h_a16}


Traverse a red-black sub-tree \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em node}]The sub-tree root \item[{\em op}]The operation to perform on each object in the sub-tree \end{description}
\end{Desc}
\index{rbtree_clean@{rbtree\_\-clean}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_clean@{rbtree\_\-clean}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_clean@{rbtree\_\-clean}}
\index{rbtree_clean@{rbtree\_\-clean}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-clean ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree})}\label{Red__black__tree_8h_a19}


Clean a red-black tree [takes O(n) operations] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \end{description}
\end{Desc}
\index{rbtree_construct@{rbtree\_\-construct}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_construct@{rbtree\_\-construct}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_construct@{rbtree\_\-construct}}
\index{rbtree_construct@{rbtree\_\-construct}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-tree}$\ast$ rbtree\_\-construct ({\bf Comp} $\ast$ {\em comp})}\label{Red__black__tree_8h_a18}


Construct a red-black tree with a comparison object \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em comp}]A pointer to the comparison object to be used by the tree \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The newly constructed tree \end{Desc}
\index{rbtree_contains@{rbtree\_\-contains}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_contains@{rbtree\_\-contains}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_contains@{rbtree\_\-contains}}
\index{rbtree_contains@{rbtree\_\-contains}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}int rbtree\_\-contains ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, void $\ast$ {\em object})}\label{Red__black__tree_8h_a23}


Check whether the tree contains an object [takes O(log n) operations] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em object}]The query object \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:](true) if an equal object is found in the tree, otherwise (false) \end{Desc}
\index{rbtree_depth@{rbtree\_\-depth}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_depth@{rbtree\_\-depth}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_depth@{rbtree\_\-depth}}
\index{rbtree_depth@{rbtree\_\-depth}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}int rbtree\_\-depth ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree})}\label{Red__black__tree_8h_a22}


Get the depth of the tree [takes O(n) operations] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The length of the longest path from the root to a leaf node \end{Desc}
\index{rbtree_destruct@{rbtree\_\-destruct}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_destruct@{rbtree\_\-destruct}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_destruct@{rbtree\_\-destruct}}
\index{rbtree_destruct@{rbtree\_\-destruct}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-destruct ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree})}\label{Red__black__tree_8h_a20}


Destruct a red-black tree \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \end{description}
\end{Desc}
\index{rbtree_find@{rbtree\_\-find}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_find@{rbtree\_\-find}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_find@{rbtree\_\-find}}
\index{rbtree_find@{rbtree\_\-find}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbtree\_\-find ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, void $\ast$ {\em object})}\label{Red__black__tree_8h_a32}


Find a node that contains the given object \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em object}]The desired object \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]A node that contains the given object, or NULL if no such object is found in the tree \end{Desc}
\index{rbtree_init@{rbtree\_\-init}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_init@{rbtree\_\-init}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_init@{rbtree\_\-init}}
\index{rbtree_init@{rbtree\_\-init}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-init ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Comp} $\ast$ {\em comp})}\label{Red__black__tree_8h_a17}


Initialize a red-black tree with a comparision function \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em comp}]The comparision function \end{description}
\end{Desc}
\index{rbtree_insert@{rbtree\_\-insert}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_insert@{rbtree\_\-insert}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_insert@{rbtree\_\-insert}}
\index{rbtree_insert@{rbtree\_\-insert}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbtree\_\-insert ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, void $\ast$ {\em object})}\label{Red__black__tree_8h_a24}


Insert an object to the tree [takes O(log n) operations] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em object}]The object to be inserted \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]the inserted object node \end{Desc}
\index{rbtree_insert_fixup@{rbtree\_\-insert\_\-fixup}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_insert_fixup@{rbtree\_\-insert\_\-fixup}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_insert_fixup@{rbtree\_\-insert\_\-fixup}}
\index{rbtree_insert_fixup@{rbtree\_\-insert\_\-fixup}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-insert\_\-fixup ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a36}


Fix-up the red-black tree properties after an insertion operation \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em node}]The node that has just been inserted to the tree \end{description}
\end{Desc}
\begin{Desc}
\item[Precondition:]The color of node must be red \end{Desc}
\index{rbtree_maximum@{rbtree\_\-maximum}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_maximum@{rbtree\_\-maximum}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_maximum@{rbtree\_\-maximum}}
\index{rbtree_maximum@{rbtree\_\-maximum}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbtree\_\-maximum ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree})}\label{Red__black__tree_8h_a29}


Get a handle to the tree maximum [takes O(log n) operations] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]the maximal object in the tree, or a NULL if the tree is empty \end{Desc}
\index{rbtree_minimum@{rbtree\_\-minimum}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_minimum@{rbtree\_\-minimum}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_minimum@{rbtree\_\-minimum}}
\index{rbtree_minimum@{rbtree\_\-minimum}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbtree\_\-minimum ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree})}\label{Red__black__tree_8h_a28}


Get a handle to the tree minimum [takes O(log n) operations] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]the minimal object in the tree, or a NULL if the tree is empty \end{Desc}
\index{rbtree_predecessor@{rbtree\_\-predecessor}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_predecessor@{rbtree\_\-predecessor}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_predecessor@{rbtree\_\-predecessor}}
\index{rbtree_predecessor@{rbtree\_\-predecessor}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbtree\_\-predecessor ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a31}


Get the previous node in the tree (according to the tree order) [takes O(log n) operations at worst-case, but only O(1) amortized] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em node}]The current object \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The predecessor node, or a NULL, if we are at the tree minimum \end{Desc}
\index{rbtree_remove@{rbtree\_\-remove}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_remove@{rbtree\_\-remove}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_remove@{rbtree\_\-remove}}
\index{rbtree_remove@{rbtree\_\-remove}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-remove ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, void $\ast$ {\em object})}\label{Red__black__tree_8h_a27}


Remove an object from the tree [takes O(log n) operations] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em object}]The object to be removed \end{description}
\end{Desc}
\begin{Desc}
\item[Precondition:]The object should be contained in the tree \end{Desc}
\index{rbtree_remove_at@{rbtree\_\-remove\_\-at}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_remove_at@{rbtree\_\-remove\_\-at}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_remove_at@{rbtree\_\-remove\_\-at}}
\index{rbtree_remove_at@{rbtree\_\-remove\_\-at}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-remove\_\-at ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a33}


Remove the object stored in the given tree node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em node}]The node storing the object to be removed from the tree \end{description}
\end{Desc}
\index{rbtree_remove_fixup@{rbtree\_\-remove\_\-fixup}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_remove_fixup@{rbtree\_\-remove\_\-fixup}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_remove_fixup@{rbtree\_\-remove\_\-fixup}}
\index{rbtree_remove_fixup@{rbtree\_\-remove\_\-fixup}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-remove\_\-fixup ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a37}


Fix-up the red-black tree properties after a removal operation \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em node}]The child of the node that has just been removed from the tree \end{description}
\end{Desc}
\index{rbtree_rotate_left@{rbtree\_\-rotate\_\-left}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_rotate_left@{rbtree\_\-rotate\_\-left}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_rotate_left@{rbtree\_\-rotate\_\-left}}
\index{rbtree_rotate_left@{rbtree\_\-rotate\_\-left}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-rotate\_\-left ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a34}


Left-rotate the sub-tree spanned by the given node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em node}]The sub-tree root \end{description}
\end{Desc}
\index{rbtree_rotate_right@{rbtree\_\-rotate\_\-right}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_rotate_right@{rbtree\_\-rotate\_\-right}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_rotate_right@{rbtree\_\-rotate\_\-right}}
\index{rbtree_rotate_right@{rbtree\_\-rotate\_\-right}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-rotate\_\-right ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a35}


Right-rotate the sub-tree spanned by the given node \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em node}]The sub-tree root \end{description}
\end{Desc}
\index{rbtree_size@{rbtree\_\-size}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_size@{rbtree\_\-size}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_size@{rbtree\_\-size}}
\index{rbtree_size@{rbtree\_\-size}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}int rbtree\_\-size ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree})}\label{Red__black__tree_8h_a21}


Get the size of the tree [takes O(1) operations] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The number of objects stored in the tree \end{Desc}
\index{rbtree_successor@{rbtree\_\-successor}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_successor@{rbtree\_\-successor}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_successor@{rbtree\_\-successor}}
\index{rbtree_successor@{rbtree\_\-successor}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}{\bf Red\_\-black\_\-node}$\ast$ rbtree\_\-successor ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Red\_\-black\_\-node} $\ast$ {\em node})}\label{Red__black__tree_8h_a30}


Get the next node in the tree (according to the tree order) [takes O(log n) operations at worst-case, but only O(1) amortized] \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em node}]The current object \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The successor node, or a NULL, if we are at the tree maximum \end{Desc}
\index{rbtree_traverse@{rbtree\_\-traverse}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_traverse@{rbtree\_\-traverse}}\index{Red_black_tree.h@{Red\_\-black\_\-tree.h}!rbtree_traverse@{rbtree\_\-traverse}}
\index{rbtree_traverse@{rbtree\_\-traverse}!Red_black_tree.h@{Red\_\-black\_\-tree.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void rbtree\_\-traverse ({\bf Red\_\-black\_\-tree} $\ast$ {\em tree}, {\bf Op} $\ast$ {\em op})}\label{Red__black__tree_8h_a38}


Traverse a red-black tree \begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em tree}]The tree \item[{\em op}]The operation to perform on every object of the tree (according to the tree order) \end{description}
\end{Desc}
