This section is a reference guide to classes/interfaces built by API on top of Tree abstract data type:
To see how can above classes/interfaces be iterated, please review iterators section. To see a real life example how can above classes be used, please have a look at unit tests.
Interface that defines operations one can perform on a Tree abstract data type
template <typename NODE>
class Tree
| Method | Signature | Description |
| ~Tree | virtual ~Tree () | Clears node children from heap memory |
| getRoot | virtual NODE* getRoot () = 0 | Gets root node from tree |
| getSize | virtual const std::size_t& getSize () const = 0 | Gets number of nodes from tree |
Class that implements a Standard Tree data structure on top of Tree abstract data type, backed by a Hash Table implementing Set to insure node value uniqueness
template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class HashTree : public Tree<TreeNode<T,compare,hash>>
| Method | Signature | Description |
| Tree | Tree (const T& data) | Creates root tree node by data inside |
| getRoot | TreeNode<T,compare,hash>* getRoot () | Gets root node of tree |
| getSize | const std::size_t& getSize () const | Gets number of nodes in tree |
| getHeight | std::size_t getHeight () | Gets number of edges from root node to most distant descendant |
| createNode | virtual TreeNode<T,compare,hash>* createNode (const T& data, TreeNode<T,compare,hash>* const& parent) | Creates a tree node, child of another |
| removeNode | virtual void removeNode (TreeNode<T,compare,hash>* const& node) | Removes and deallocates node from tree, moving children to its parent |
| removeBranch | virtual void removeBranch (TreeNode<T,compare,hash>* const& node) | Removes and deallocates node from tree along with all descendants |
| search | TreeNode<T,compare,hash>* search (const T& data) | Searches node in tree by value inside |
| contains | bool contains (const T& data) const | Checks if tree contains a node by value inside |
Class that implements a Red Black Tree data structure on top of Tree abstract data type
template <typename T>
class RedBlackTree : public Tree<RedBlackTreeNode<T,compare,hash>>
| Method | Signature | Description |
| RedBlackTree | RedBlackTree (int (*comparator)(const T&,const T&)) | Creates a RBT by comparator |
| ~RedBlackTree | ~RedBlackTree () | Deallocates all elements in RBT from heap |
| getNodeValue | T* getNodeValue (const T& value) const | Gets value in RBT matching that of input |
| insertNode | void insertNode (const T& value) | Adds node to RBT by value |
| hasNode | bool hasNode (const T& value) const | Checks if RBT contains node by value |
| hasMatches | bool hasMatches (const T& value, int (*custom_comparator)(const T&,const T&)) | Checks if RBT contains node by value and comparator |
| deleteNode | void deleteNode (const T& value) | Removes node from RBT by value |
| deleteMatches | void deleteMatches (const T& value, int (*custom_comparator)(const T&,const T&)) | Removes node from RBT by value and comparator |
| getNextNode | RedBlackTreeNode<T,compare,hash>*& getNextNode (RedBlackTreeNode<T,compare,hash>* node) | Gets next node in RBT after input node for iteration |
Class that implements a NODE in a Standard Tree data structure backed by a Hash Table implementing Set to insure value uniqueness along with operations it can perform
template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class TreeNode
| Method | Signature | Description |
| TreeNode | TreeNode (const T& data) | Creates a node by value inside |
| ~TreeNode | ~TreeNode () | Clears node children from heap memory |
| setParent | void setParent (TreeNode<T,compare,hash>* const& parent) | Sets parent node |
| getParent | TreeNode<T,compare,hash>* const& getParent () | Gets parent node |
| setData | void setData (const T& data) | Sets value inside node |
| getData | const T& getData () const | Gets value inside node |
| getChildren | Set<TreeNode<T,compare,hash>*>* const& getChildren () | Gets all node children |
| addChild | void addChild (TreeNode<T,compare,hash>* const& node) | Adds child node |
| hashChild | bool hashChild (TreeNode<T,compare,hash>* const& node) | Checks if node has child node |
| removeChild | void removeChild (TreeNode<T,compare,hash>* const& node) | Removes child node |
| removeChildren | void removeChildren () | Removes all child nodes |
| isDescendantOf | bool isDescendantOf (TreeNode<T,compare,hash>* const& node) | Checks if node is descendant of another |
| isAncestorOf | bool isAncestorOf (TreeNode<T,compare,hash>* const& node) | Checks if node is ancestor of another |
| getAncestors | List<TreeNode<T,compare,hash>*>* getAncestors () | Gets all node ancestors. Pointer returned must be deallocated by user! |
| getDescendants | List<TreeNode<T,compare,hash>*>* getDescendants () | Gets all node descendants. Pointer returned must be deallocated by user! |
| getSize | std::size_t getSize () const | Gets number of children in node |
| getHeight | std::size_t getHeight () const | Gets number of edges from the current node to most distant descendant |
| getDepth | std::size_t getDepth () const | Gets number of edges from the current node to most distant ancestor |
Struct that defines a NODE in a Red Black Tree
template <typename T>
struct RedBlackTreeNode
| Name | Type | Description |
| data | T | Node data |
| left | RedBlackTreeNode<T,compare,hash>* | Left node |
| right | RedBlackTreeNode<T,compare,hash>* | Right node |
| parent | RedBlackTreeNode<T,compare,hash>* | Parent node |
| color | RedBlackTreeNodeColor | Node color |
Enum that defines colors required by Red Black Tree algorithm
enum RedBlackTreeNodeColor {RED, BLACK}