Abstract Data Types: Trees

What is a tree?

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

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:

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:

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!


Share