What is a Tree in Data Structure?
A tree is a type of data structure representing hierarchical data. It has a non-linear structure consisting of nodes connected by edges. Among the other types of data structures that perform operations in a linear data structure, the complexity increases with an increase in data size. However, the tree data structure provides quicker access to the data which is non-linear. Availability of the various types of data structures and the algorithms associated with them, the task performance has become an easy and efficient way.
A few terminologies associated with trees in data structure are:
- Node: the node is an entity in a tree data structure that contains a key or a value and pointers to its child nodes.
- Child node: A child node is the descendant of any node.
- Leaf nodes: The nodes which don’t have any child nodes and are the bottom-most node in a tree. They are also called the external nodes.
- Root: It is the topmost point of a tree.
- Internal node: The node having at least one child node.
- Edge: An edge refers to the connection between any two nodes in a tree.
- Height of a node: Number of edges from the node to the deepest leaf.
- Depth of a node: Number of edges from the root to the node.
- Height of a tree: Height of the root node.
- Degree of a node: Total number of branches to that node.
- Forest: A collection of disjoint trees.
Types of tree
1. Binary tree
The binary tree is a type of tree data structure where every parent node has a maximum of two child nodes. As the name suggests, binary means two, therefore, each node can have 0, 1, or 2 nodes. A binary tree data structure is shown in Figure 1. Node 1 in the tree contains two pointers, one for each child node. Node 2 again has two pointers each for the two child nodes. Whereas node 3, 5, and 6 are leaf nodes and therefore, have null pointers on both left and right parts.
Figure 1: A representation of a binary tree (https://www.javatpoint.com/binary-tree).
Properties of a binary tree
- Maximum number of nodes at each level of I is 2 i.
- The height of the tree in Figure 1 is 3 which means that the maximum number of nodes will be (1+2+4+8) =15.
- At height h, the maximum number of nodes possible is (20 + 21 + 22+….2h) = 2h+1 -1.
- At height h, the minimum number of nodes possible is equal to h+1.
- A minimum number of nodes will represent a tree with maximum height and vice versa.
Even the binary trees can be divided into the following types of tree:
- Full Binary tree: It is a special type of binary tree. In this tree data structure, every parent node or an internal node has either two children or no child nodes.
- Perfect binary tree: In this type of tree data structure, every internal node has exactly two child nodes and all the leaf nodes are at the same level.
- Complete binary tree: It resembles that of the full binary tree with a few differences.
- Every level is completely filled.
- The leaf nodes lean towards the left of the tree.
- It is not a requirement for the last leaf node to have the right sibling, i.e. a complete binary tree doesn’t have to be a full binary tree.
- Degenerate or Pathological Tree: These trees have a single child either to the left or right of the parent node.
- Skewed binary tree: It is a pathological or degenerate tree where the tree is dominated by either the left nodes or the right nodes. Therefore, there are two types of skewed binary trees, i.e. left-skewed or the right-skewed binary tree.
- Balanced binary tree: The difference between the height of the left and right subtree for each node is either 0 or 1.
2. Binary Search Tree
These tree structures are non-linear and one node is connected to a number of nodes. The node can be connected to at most two child nodes. It is called a binary search tree because:
- Each node has a maximum of two child nodes.
- It can be used to search an element in 0(log(n)) time and hence known as a search tree.
Figure: An example of a Binary search tree (https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm)
Properties of a binary search tree are:
- Value in all the nodes of a left subtree should be lesser than the value in the root node.
- Value in all the nodes of a right subtree should be larger than the value in the root node.
3. AVL Tree
The AVL trees are the types or variants of a binary tree. It consists of properties from both the binary as well as a binary search tree. Invented by Adelson Velsky Lindas, these trees are self-balancing which means the height of the left subtree and the right subtree is balanced. This balance is measured in terms of a balancing factor.
- It is the difference between the left subtree and the right subtree.
- The value of a balancing factor must be 0, -1, or 1. Therefore, each node of an AVL tree should consist of a balancing factor value i.e. 0, -1, or 1.
- Balance Factor = (Height of Left Subtree – Height of Right Subtree)
- An AVL tree is said to be a balanced tree if the balance factor of each node is between -1 to 1.
Values of nodes other than -1, to 1 in an AVL tree will represent an unbalanced tree that needs to be balanced.
- If a node has a balance factor of 1, it means that the left subtree is one level higher than the right subtree.
- If a node has a balance factor of 0, it means that the height of the left subtree and the right subtree is equal.
- If a node has a balance factor of -1, it means that the right subtree is one level higher than the left subtree or the left subtree is one level lower than the right subtree.
B Tree is a more generalized form of a binary search tree. It is also known as the height-balanced m way tree, where m is the order of the tree. Each node of the tree can have more than one key and more than two child nodes. In the case of a binary tree, the leaf nodes might not be at the same level. However, in the case of a B Tree, all the leaf nodes should be at the same level.
Properties of a B-tree:
- Keys are stored in increasing order for each node x.
- A Boolean value “x.leaf” exists in each node, which is true if x is a leaf.
- The internal nodes should have at most “n-1” keys, where n is the order of the tree. It should also have a pointer for each child.
- All the nodes will have at most n children and at least n/2 children, except the root node.
- The leaf nodes of the tree have the same depth.
- The root node will have a minimum of 1 key and at least two children.
- If n ≥ 1, then for any n-key B-tree of height h and minimum degree t ≥ 2, h ≥ logt (n+1)/2.
- Binary Search tree can be applied for searching an element in a set of elements.
- Heap trees are used for heap sort.
- Modern routers use a type of tree called Tries for storing routing information.
- The B-Trees and the T-Trees are mostly used by popular databases to store their data.
- A syntax tree is used by compilers to validate the syntax of every written program.
Data structures provide an organized way of storing the data for easy management and effective handling. Various types of data structures exist for different types of data. Based on the type of data that needs to be stored, it is chosen by the user.
Trees are types of such data structures where the hierarchical type of data can be stored. The data is stored in the nodes which sometimes stores the reference for other nodes called the children nodes.
Based on the number of child nodes, trees can be classified into various types as mentioned in the article. Based on the arrangement of nodes in the tree types, each tree structure has associated properties. With the different types of operation that can be performed by the different classes of trees, this type of data structure has found applications in sorting algorithms and data storage.
An Executive PG Programme in Software Development – Specialisation in Full Stack Development, curated by upGrad & IIIT-Bangalore, can assist you in improving your profile and securing better employment opportunities as a programmer.