Abstract Data Types: Trees

├─ What is a TREE
├─ What are the operations a TREE requires
└─ What are the data structures that implement TREE

What is a tree?

A tree is a non-sequential abstract data type where following rules have to be obeyed:

every entry is a node that has links to:
- a single parent node (unless it's root)
- a number of child nodes (if any)
there is a single root node all others descend from directly or indirectly. This node is the only entry that has a nil parent.
by following child nodes recursively, no node should be able to reach itself (it should be acyclic)
there must be a single path from one node to another (no reference is duplicated)

How values (or nodes) are added to tree:

What are the operations a tree requires?

One of the reasons why textbooks do not mention trees as abstract data type is that in usage they are almost irreducible to a common ground: each type of tree chosen reflects a different need with fundamentally different operations. Of all, only these two are universally common:

Operation	Arguments	Returns	Description
getSize		ULONG	Gets number of nodes in tree.
getRoot		NODE	Gets root node from tree.

What are the data structures that implement tree?

On this opaque definition, there are endless varieties built to address a particular need. Most commonly used are:

Standard Tree: a tree in which node can have no matter how many children
- Strengths:
  - good to store node hierarchies without any special rules
  - memory/speed efficiency
- Weaknesses:
  - ordering is very costly
  - search is very slow, unless nodes are stored in a Hash Table as well
Binary Search Tree: a tree in which node can only have two children at most, able to rebalance itself
- Strengths:
  - good when someone wants tree nodes to be self-sorted
  - good for node searches
- Weaknesses:
  - slow at any operation that may require rebalancing (inserts, deletes)
  - higher memory consumption

This time complexity table using Big O Notation shows advantages and disadvantages of each data structure chosen for each tree operation:

Operation	Standard Tree	Binary Search Tree
getSize	O(1)	O(1)
getRoot	O(1)	O(log(N))

Conclusion: Standard Tree backed by a Hash Table, with its speed/memory efficiency advantages, should be solution of choice unless one specifically desires structure to be self-ordered!