Reference Guide: Trees

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.

Tree

Interface that defines operations one can perform on a Tree abstract data type

Signature

template <typename NODE> class Tree

Methods

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

HashTree

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

Signature

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>>

Additional Methods

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

RedBlackTree

Class that implements a Red Black Tree data structure on top of Tree abstract data type

Signature

template <typename T> class RedBlackTree : public Tree<RedBlackTreeNode<T,compare,hash>>

Additional Methods

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

TreeNode

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

Signature

template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>> class TreeNode

Methods

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

RedBlackTreeNode

Struct that defines a NODE in a Red Black Tree

Signature

template <typename T> struct RedBlackTreeNode

Fields

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

RedBlackTreeNodeColor

Enum that defines colors required by Red Black Tree algorithm

Signature

enum RedBlackTreeNodeColor {RED, BLACK}
Share