Tree Data Structure PDF

TREE Prepared By : Dr.Asmaa Awad What is a Tree? ▪ Tree is a non-linear data structure which organizes data in a hierarchical structure ▪ A tree data structure is a hierarchical model that represents relationships between elements, often referred to as nodes. It is an abstract data type that sim...

TREE Prepared By : Dr.Asmaa Awad What is a Tree? ▪ Tree is a non-linear data structure which organizes data in a hierarchical structure ▪ A tree data structure is a hierarchical model that represents relationships between elements, often referred to as nodes. It is an abstract data type that simulates a hierarchical tree structure with a root value and subtrees of children, represented as a set of linked nodes. Tree Terminology ▪ Important terms related to tree are Root ▪ The first node from where the tree originates is called as a root node. ▪ In any tree, there must be only one root node. ▪ We can't have multiple root nodes in a tree data structure. Edge ▪ The connecting link between any two nodes is called as an edge. ▪ In a tree with n number of nodes, there are exactly (n-1) number of edges Parent ▪ The node which has a branch from it to any other node is called as a parent node. ▪ In other words, the node which has one or more children is called as a parent node. ▪ In a tree, a parent node can have any number of child nodes. Child ▪ The node which is a descendant of some node is called as a child node. ▪ All the nodes except root node are child nodes siblings ▪ Nodes which belong to the same parent are called as siblings. ▪ In other words, nodes with the same parent are sibling nodes Degree ▪ Degree of a node is the total number of children of that node. ▪ Degree of a tree is the highest degree of a node among all the nodes in the tree internal node ▪ The node which has at least one child is called as an internal node. ▪ Internal nodes are also called as non-terminal nodes. ▪ Every non-leaf node is an internal node. Leaf Node ▪ The node which does not have any child is called as a leaf node. ▪ Leaf nodes are also called as external nodes or terminal nodes.. Level ▪ Level: The number of edges on the path from the root to the node. ▪ In tree data structures, the root node is said to be at level 0, and the root node's children are at level 1, and the children of that node at level 1 will be level 2, and so on.. Height ▪ Height: The length of the longest path from the node to a leaf. ▪ In a tree data structure, the number of edges from the leaf node to the particular node in the longest path is known as the height of that node. ▪ In the tree, the height of the root node is called "Height of Tree". ▪ The tree height of all leaf nodes is 0. Depth ▪ Depth: The length of the path from the root to the node ▪ In a tree, many edges from the root node to the particular node are called the depth of the tree. ▪ In the tree, the total number of edges from the root node to the leaf node in the longest path is known as "Depth of Tree". ▪ In the tree data structures, the depth of the root node is 0 Subtree ▪ Subtree: A portion of the tree that includes a node and its descendants. ▪ In a tree, each child from a node forms a subtree recursively. ▪ Every child node forms a subtree on its parent node. Path ▪ In the tree in data structures, the sequence of nodes and edges from one node to another node is called the path between those two nodes. ▪ The length of a path is the total number of nodes in a path Ancestors ▪ Ancestors of a node are all the nodes along the path from the root to that node ▪ The ancestor of node 9 are 7, 3 and 1 ▪ The ancestor of node 6 is 3 and 1 Types of Trees ▪ A binary Tree is defined as a Tree data structure with at most 2 children ▪ A Ternary Tree is a tree data structure in which each node has at most three child nodes “left”,”mid”,”right” ▪ Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children Binary Tree Types ▪ A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible. ▪ A full binary tree is a binary tree with either zero or two child nodes for each node. Binary Tree Types ▪ A perfect binary tree is a special type of binary tree in which all the leaf nodes are at the same depth, and all non-leaf nodes have two children. Binary Search Tree ▪ A Binary Search Tree (or BST) is a data structure used in computer science for organizing and storing data in a sorted manner. ▪ Each node in a Binary Search Tree has at most two children, a left child and a right child, with the left child containing values less than the parent node and the right child containing values greater than the parent node. ▪ This hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree. Basic Operations of BST ▪ Tree Traversal ▪ Insert ▪ Search ▪ Delete Tree Traversal ▪ Tree Traversal refers to the process of visiting or accessing each node of the tree exactly once in a certain order ▪ Tree traversal algorithms help us to visit and process all the nodes of the tree Inorder Traversal ▪ Inorder traversal visits the node in the order: Left -> Root -> Right Time Complexity: O(N) Preorder Traversal ▪ Preorder traversal visits the node in the order: Root -> Left -> Right Postorder Traversal ▪ Postorder traversal visits the node in the order: Left -> Right -> Root Level Order Traversal ▪ Level Order Traversal is mainly used as Breadth First Search to search or process nodes level-by-level. Insert in BST Insert in BST Insert in BST Insert in BST Insert in BST Insert in BST Insert BST Search BST Search in BST Search in BST Search in BST Delete BST Delete BST Delete BST Application ▪ Hierarchical Data Representation: Such as file systems. ▪ Databases: For indexing purposes ▪.Network Routing Algorithms: To determine the shortest path. ▪ Artificial Intelligence: Decision trees for decision-making processes. Trees are a fundamental part of computer science and are used in various applications due to their efficiency in searching and sorting