Trees Data Structure
- A tree is a type of data structure that is organized in a hierarchy. The root of a tree is the very highest portion of the tree.
- Every element in a tree, excluding the root, has a parent element and zero or more child elements.
- In sorting order, all elements in the left sub-tree come before the root, and all elements in the right sub-tree come after the root.
- When you need to store hierarchical data, the tree is the most appropriate data structure.
- Consider the directory structure of a file system; you'll find many different types of trees. Red-black tree, threaded binary tree, AVL tree, and others are among them.
Let's understand some key points of the Tree data structure.
- A tree data structure is made up of nodes, which are items or entities that are joined together to represent or simulate hierarchy.
- Because it does not store data in a sequential order, a tree data structure is a non-linear data structure. Because the pieces in a Tree are grouped at numerous levels, it is a hierarchical structure.
- The root node in a Tree data structure is the topmost node. Each node has some data, which can be of any kind. Because the node in the above tree structure contains the employee's name, the data type is a string.
- Each node includes data as well as a link or reference to other nodes known as children.
Root:
- The root node is the node at the very top of the tree structure. To put it another way, the root node is the one that has no children.
- The root node of the tree is numbered 1 in the above structure. A parent-child relationship exists when one node is directly linked to another node.
Child node:
- A node is considered a child node if it is a descendent of another node.
Parent:
- If a node contains any sub-nodes, that node is considered to be the parent of those sub-nodes.
Sibling:
- Nodes with the same parent are referred to as siblings.
Leaf Node:
- A leaf node is a node in a tree that does not have any child nodes. A leaf node is the tree's bottommost node.
- In a generic tree, there can be any number of leaf nodes. External nodes are also known as leaf nodes.
Internal nodes:
- An ancestor of a node is any predecessor node on a path from the
- An ancestor of a node is any predecessor node on a path from the root to that node.
- There are no ancestors for the root node. Nodes 1, 2, and 5 are the ancestors of node 10 in the tree depicted above.
Descendant:
- A descendant of a node is the direct successor of the supplied node. In the diagram above, node 10 is a descendent of node 5.
Properties of Tree data structure
Recursive data structure:
- A recursive data structure is similar to a tree. Because the distinct node in a tree data structure is known as a root node, a tree can be defined as recursively.
- The tree's root node contains a link to all of its subtrees' roots.
- In the diagram below, the left subtree is depicted in yellow, while the right subtree is shown in red.
- The left subtree can be further divided into three different colored subtrees.
- Recursion refers to the reduction of something in a self-similar way.
- As a result, the tree data structure's recursive characteristic is used in a variety of applications.
Number of edges:
- There would be n-1 edges if there were n nodes. The link or path is represented by each arrow in the structure.
- Except for the root node, each node will have at least one inbound link, referred as as an edge. For the parent-child relationship, there would be only one link.
Depth of node x:
- The length of the path from the root to node x can be defined as the depth of node x. In the path, one edge contributes one unit of length.
- As a result, the number of edges between the root node and node x can alternatively be described as the depth of node x.
- The depth of the root node is zero.
Height of node x:
- The longest path from node x to the leaf node can be described as the height of node x.
