Data structures are a special way to organize your data and store it on your computer for more effective use. There are different types of data structures. The stack, linked list, and queue are arranged in order. For example, a linked data structure consists of a set of nodes linked by a link or point.
Similarly, a tree data structure is a type of hierarchical data arranged in a tree-like structure. It consists of a central node, a structural node, and subnodes connected by edges. You can also say that roots, branches, and leaves are interconnected in a tree’s data structure.
The tree is non-linear, a hierarchical data structure consisting of a collection of nodes, and each node in the tree contains a value that is a list of references to the node (the “child”).
Types of tree data structure
The different types of tree data structures are:
1. General tree
There is no limit to the number of nodes in a typical tree data structure. This means that the parent node can have any number of child nodes.
2. Binary tree
A binary tree node can have up to two child nodes. In a given dendrogram, nodes B, D, and F are children on the left, and E, C, and G are children on the right.
3. Balance tree
A tree is said to have a balanced tree data structure if the heights of the left and right subtrees are the same or differ by up to one.
4. Binary search tree
As the name implies, the binary search tree is used for various search and sort algorithms. Examples include AVL trees and red-black trees. This is a non-linear data structure. This indicates that the value of the node on the left is smaller than its parent, while the value of the node on the right is greater than its parent.
Features:
The properties of the tree data structure are:
• For n nodes, the edges of the tree are equal (n — 1). For example, as shown in the tree diagram above, five nodes (5–1) contain four edges in the tree data structure.
• Arrows in the structure represent paths. Each edge connects two nodes.
• Each of the two nodes or vertices in the tree graph is connected by exactly one edge.
• Node depth is defined as the length of the path from the root node to node a. The height of node “a” is the longest path from node “a” to the leaf node of the specified tree.
Other properties are:
- Traversal in the tree is performed by a depth-first search and breadth-first search algorithms. No loops or circuits
- There is no self-loop
- That hierarchical model.
There are no.of other trees that are implemented in real life scenarios.
- AVL tree
The AVL tree was invented in 1962 by GM Adelson-Belsky and EM Landis. This tree is named AVL in honor of the inventor.
An AVL tree can be defined as a height-balanced binary search tree. In this tree, each node is associated with an equilibrium constant calculated by subtracting the height of the subtree on the right from the height of the subtree on the left.
If the balance factor for each node is between -1 and 1, the tree is considered balanced. Otherwise, the tree is unbalanced and needs to be balanced.
Balancing factor (k) = height (left (k))-height (right (k))
- Red-Black tree
A red-black tree is a self-balancing binary search tree, and each node contains an additional bit that indicates the node’s color (red or black).
Red-black trees have the following characteristics-
- Each node is color coded either red or black.
- The root node is always black
- Each leaf (NIL) is black.
- If a red node has children, the children are always black. Depth property: For any node, all simple paths from that node to one of its descendants have the same black depth (number of black nodes).