Data Structures: Standard Trees

What is a standard tree?

A standard tree is a Tree implementation without any restrictions, except those all trees by definition must obey to. In common practice, they are just used to store hierarchical un-ordered data.

What are the operations it requires?

Apart of implementing operations required by Tree abstract data type, following operations are added by standard tree:

Operation Arguments Returns Description
getHeight   ULONG Gets number of edges from root node to most distant descendant
createRootNode DATA NODE Sets tree root node.
createNode DATA, PARENT_NODE NODE Creates node, child of another, and adds it to tree.
removeNode NODE   Removes node from tree and moves its children to parent node.
removeBranch NODE   Removes node from tree along with its children.

And a NODE whose operations are:

Operation Arguments Returns Description
setData DATA void Sets value inside node
getData   DATA Gets value from node.
setParent NODE void Sets node's parent.
getParent   NODE Gets node's parent.
getChildren   EDGES Gets node's children.
addChild NODE void Adds child node.
hasChild NODE boolean Checks if node has child node.
removeChild NODE void Removes child node.
removeChildren   void Removes all child nodes.
isDescendantOf NODE void Checks if node is descendant of another.
isAncestorOf NODE void Checks if node is ancestor of another.
getRoot   NODE Navigates through node's ancestors until root node is found and returns latter.
getAncestors   LIST[NODE] Navigates recursively through node's parents in order to get all ancestors.
getDescendants   LIST[NODE] Navigates recursively through node's children in order to get all descendants.
getSize   ULONG Gets number of node descendants.
getHeight   ULONG Gets number of edges from the current node to most distant ancestor.
getDepth   ULONG Gets number of edges from the current node to most distant descendant

Regarding implementation chosen for "LIST[NODE]" above, following data structures should be used:

Regarding implementation chosen to store NODE's children, which reflects into "EDGES" above, following data structures can be used:

If Hash Table implementing Set solution is chosen, two more operations can be generalized for standard tree, both executed in constant O(1) time:

Operation Arguments Returns Description
contains DATA boolean Checks if tree contains a node whose value equals that of input.
search DATA VERTEX Searches tree for a node whose value equals that of input.

What are the methods to traverse a standard tree?

Depending on when a NODE is visited during traversal, following methods are in most common usage:


Share