What is a Tree?
Data structures, amongst other things, are used to store and organize data. Different types of data are more efficiently organized using particular data structures.
Trees are non-linear data structures which are quite often used to represent hierarchical data such as the employee organizational structure in a company.
Structure of a Tree:
A collection of entities called nodes (represented as circles in our diagrams) are linked together with an edge to simulate a hierarchical structure. Each node contains data that can be of any type as long as all the nodes contain the same type of data.
Components of a Tree:
Root: A node with no incoming link to another node, i.e. no parent.
Child: A node with an incoming link from an upper node, i.e. a parent node. A child can only have one parent.
Parent: A node with an outgoing link to a lower node, i.e. a child node. A parent can have multiple children.
Siblings: Children nodes with the same parent.
Leaf: A node with no outgoing link to a lower node, i.e. no child node.
Depth: The depth of a node, ‘x’, is the number of edges (links) in the path from the root node to the node ‘x’. In the example on the right, the depth of node ‘x’ is 2.
Height: The height of a node, ‘x’, is the number of edges (links) in the longest path from the node ‘x’ to a leaf node. In the example on the left, the height of node ‘x’ is 0 because it is zero edges away from the root node, while the height of the root node is 2. The height of a tree is equivalent to the height of the node with the maximum height.
Subtree: A subtree is a smaller tree within a larger tree. The root node of a subtree can be any node of the larger tree. In the example on the left, tree A is a subtree of tree B.
A Sample Tree:
Different Types of Trees:
Many different types of trees exist which are optimized for particular use-cases. Each tree type offers its own particular structure. Some commonly used trees include:
- Binary Trees
- Binary Search Trees
- AVL Trees
- Red-Black Trees
- 2-3 Trees
- 2-3-4 Trees
