Introduction to Tree in Data Structure
A tree is a popular data structure with a hierarchical structure resembling a tree in the real world. It consists of a group of nodes connected by edges, each of which can have one or more children, with the exception of the root node, which has no parents. In order to organize and portray data in a hierarchical fashion, trees are usually used.
Tree is an example of non-linear data structure.
A tree is a data structure similar to a linked list but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes.
Two primary parts of a tree data structure are nodes and edges. The real data is contained in nodes, which may additionally have references or pointers to their child nodes. The connections between the nodes, known as edges, show their connectedness to one another. Except for the root node, every node has a parent node to which it is joined via an edge.
Basic Terminologies for a Tree
1. Node: The basic building block of a tree is the node. It represents a component or piece of data and could also include references or further details. Except for the root node, each node can have one or more children. E.g. Node A,B,C,D,E,F,G,H,I,J,K in the above diagram.
2. Root: In a tree, the root is the highest node. It has no parent nodes and acts as the root node for navigating the tree. E.g. Node A in the above diagram.
3. Parent: The node directly above a node in the hierarchy is considered the parent of that node. A node can only have one parent at most. E.g. A is parent to B, C, D. F is parent to J.
4. Child: A child is a node that lies immediately beneath its parent. There may be 0 or more child nodes in a node. J and K are child nodes of F and G respectively. B, C, D are children of A.
5. Siblings: Siblings are nodes with the same parent as themselves. They are nodes that share a parent node immediately, in other words. E and F are siblings with a common parent B.
6. Leaf node: A node that has no child nodes is referred to as a leaf node or a terminal node. The real data or values are contained there, representing the tree structure's branching points. E, J, K, H, I are leaf nodes.
7. Internal node: A node that has one or more child nodes is said to be an internal node. Any node that isn't a leaf node qualifies. For example A, B, C, D, E, F, I are internal nodes.
8. Edge: The connection or link between two nodes in a tree is represented by an edge. The relationship between the nodes is represented, demonstrating that one node is the parent of another.
9. Path: A path is a series of nodes connected by edges that starts at one node in the tree and ends at a different node. It displays the path or traversal between two nodes.
10. Ancestor: If there is a path from p to q, then p is the ancestor of q. A, C and G are the ancestor of K.
11. Descendent: If there is a path from p to q, then q is the descendent of p K is the descendent of G.
12. Depth: length of the path from root to the node. Depth of root is 0. The depth of given tree is 3(total number of edges between nodes A and K).
13. Subtree: A subtree is a portion of a tree that consists of a node and all of its descendants (child nodes, their child nodes, and so on). It represents a smaller tree within the larger tree. A, B,C, D is a subtree with A as parent and B, C, D as children of A.
14. Degree: The degree of a node is the number of its child nodes. It represents the count of immediate subnodes a particular node has. Degree of D is 2.
15. Height: The height of a tree is the maximum depth among all the nodes in the tree. It represents the length of the longest path from the root node to any leaf node. The height of the given tree is 3. It is counted from K to A. Height of C is 2(count number of edges from K to C). Height of K is 0.
14. Size of node: size of a node is the number of descendants it has including itself. Size of subtree C is 3.
15. Skew Tree: Every node in a tree has only one child (except leaf node).
17. Right skew trees: if every node has only right child
16. Left skew trees: If every node has only left child
Types of Trees in Data Structure:
- Binary tree: A binary tree is a type of tree where each node can only have two children, known as the left child and the right child. Typically, the right child is bigger than the left child, and vice versa. The Insertion, deletion and search operation in a BST is efficient, with a time complexity of O(log n) on average. For effective searching and sorting algorithms, binary trees are frequently utilized.
2. Binary Search Tree (BST): A type of binary that has right children with values bigger than the node and left children with values smaller than the node is known as a binary search tree. BSTs are appropriate for a variety of applications because they offer quick insertion, deletion, and searching operations.
3. AVL tree: An AVL tree is a self-balancing binary search tree in which each node's left and right subtrees have heights that are different by no more than one. Each node in an AVL tree maintains a balance factor, which is the difference between the heights of its left and right subtrees. The balance factor can be -1, 0, or 1. This factor is used to determine if the tree needs to be rebalanced. When a node is inserted or deleted in an AVL tree, self-balancing operations are performed to maintain the balance factor. For an AVL tree insertion, and deletion operations have a time complexity of O(log n).
The efficiency of the tree in terms of search, insertion, and deletion operations is maintained by this balancing attribute. In cases requiring assured logarithmic time complexity, AVL trees are frequently employed.
4. Red-Black Tree: A red-black tree is another type of self-balancing binary search tree. It ensures that the tree remains balanced by applying specific coloring and rotation rules during insertion and deletion operations. Red-black trees offer efficient logarithmic time complexity for various operations, including searching, insertion, and deletion.
5. B-Tree: The B-tree is a tree data structure where all leaves are at the same level, ensuring balancedness. Its minimum degree 't' is determined by the disk block size. Each non-root node must contain at least 't-1' keys, while the root can hold a minimum of 1 key. The maximum number of keys that any node, including the root, can have is (2*t - 1). The number of children a node has is equal to the number of keys it holds plus 1. Keys within a node are sorted in ascending order, and the child between two keys 'k1' and 'k2' contains all keys falling within that range. Unlike Binary Search Trees, B-trees grow and shrink from the root. Like other balanced Binary Search Trees, search, insertion, and deletion operations have a time complexity of O(log n). Notably, in B-trees, nodes are only inserted at leaf nodes.
Time complexities for insertion, search, and deletion operations in different types of trees:
Binary Tree:
- Insertion: Best case - O(1) (if inserting at a specific position or as a leaf node), Average case - O(n) (if the tree is balanced), Worst case - O(n)
- Search: Best case - O(1) (if the element is at the root node), Average case - O(n) (if the tree is balanced), Worst case - O(n)
- Deletion: Best case - O(1) (if deleting a specific node with no children or with only one child), Average case - O(n) (if the tree is balanced)
Binary Search Tree (BST):
- Insertion: Best case - O(log n), Average case - O(log n)
- Search: Best case - O(log n), Average case - O(log n)
- Deletion: Best case - O(log n), Average case - O(log n)
AVL Tree:
- Insertion: O(log n)
- Search: O(log n)
- Deletion: O(log n)
Red-Black Tree:
- Insertion: O(log n)
- Search: O(log n)
- Deletion: O(log n)
B-Tree:
- Insertion: O(log n)
- Search: O(log n)
- Deletion: O(log n)