Abstract Data Types: Trees
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)
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 very different need, requiring fundamentally different operations. Of all, only these two are universally common:
||Gets number of nodes in tree.
||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
- good to store node hierarchies without any special rules
- memory/speed efficiency
- 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
- good when someone wants tree nodes to be self-sorted
- good for node searches
- 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:
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!