More Related Content
Similar to TREE DATA STRUCTURE SLIDES dsa dsa .pptx (20)
Recently uploaded (20)
TREE DATA STRUCTURE SLIDES dsa dsa .pptx
- 1. TREE Data Structures 1- Linear Data Structures Examples: Arrays, Link List, Stack, Queue 2- Non-Linear Data Structures Examples: Tree, Graphs, etc. Types of Tree a) Natural Tree b) Programming Tree Types of Programming Tree a) Binary Tree b) Binary Search Tree c) AVL/Balance Tree d) Spanning Tree e) 2/3 Tree f) 2/3/4 Tree g) B Tree h) B+ Tree
- 2. What is a Tree? • General Concepts
- 3. Tree Descriptions (Important Terms) • Path − Path refers to the sequence of nodes along the edges of a tree. • Root – The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node. • Parent − Any node except the root node has one edge upward to a node called parent. • Child – The node below a given node connected by its edge downward is called its child node. • Leaf – The node which does not have any child node is called the leaf node. • Subtree − Subtree represents the descendants of a node. • Visiting − Visiting refers to checking the value of a node when control is on the node. • Traversing − Traversing means passing through nodes in a specific order. • Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on. • Keys − Key represents a value of a node based on which a search operation is to be carried out for a node.
- 4. Binary Tree Binary Tree Binary Tree is a tree in which one parent node can have maximum 2 child nodes and minimum 0 child node. a) Strictly BT Strictly Binary Tree is such a binary tree in which one parent node can have maximum 2 child nodes. b) Complete Binary Tree Complete Binary Tree is such a Binary Tree in which all the leaf nodes should be at the same level and at each level there can be maximum 2level nodes. Total number of nodes in complete binary tree = 2d+1 -1, where d represents the depth of tree. • Height of Tree: The total number of levels from root node to leaf node is called height of tree.
- 5. Complete Binary Tree Representation CBT exhibits a special behavior. A node's left child must have a value less than its parent's value and the node's right child must have a value greater than its parent value.
- 6. Traversal of Tree Whenever you visit each node of tree then this process is called traversal or tree traversal. Types of Tree Traversal 1- Pre-Ordered Traversal 2- In-Ordered Traversal 3- Post-Ordered Traversal Pre-Ordered Traversal: a) Visit the root node b) Traverse the lefts of sub-tree c) Traverse the rights of sub-tree
- 7. Traversal of Tree In-Ordered Traversal: a) Traverse the lefts of sub-tree b) Visit the root node c) Traverse the rights of sub-tree Post-Ordered Traversal: a) Traverse the lefts of sub-tree b) Traverse the rights of sub-tree c) Visit the root node
- 8. Binary Search Tree (BST) Binary Search Tree: A binary tree in which the left child node of a tree or sub-tree has lesser value than its root node but the right child node has greater value than its root node, such a binary tree is called Binary Search Tree or BST. When a BST is traversed in-order and the data item of each node is printed/read, then the data item is printed in ascending order. Advantages of BST: Easy to perform operations i.e. insertion, creating new tree, searching and deletion in BST Example: Construction of BST for the given values, such as 45 30 35 25 60 70 80 55 4 3 30 25 16 10 8 5
- 9. Structure for Node Creation struct node { int data; struct node *leftChild; struct node *rightChild; };
- 10. BST Basic Operations • The basic operations that can be performed on a binary search tree data structure, are the following − • Insert ()− Inserts an element in a tree/create a tree. • Search () − Searches an element in a tree. • Delete () – Delete an element in a tree • Pre-order Traversal () − Traverses a tree in a pre-order manner. • In-order Traversal ()− Traverses a tree in an in-order manner. • Post-order Traversal ()− Traverses a tree in a post-order manner.
- 11. Algorithm for insertion in BST If root is NULL then create root node Return If root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert data end If
- 12. BST Insertion Implementation class CBST { private: struct node *root; public: CBST(){root==NULL;} void add_CBST_Node(int x); void delete_CBST_Node(int x); void Pre_Order(); void In_Order(); void Post_Order(); }; void CBST :: add_CBST_Node(int x) { struct node *p, *s, *par; p = new node; p -> info = x; p -> left == NULL; p -> right == NULL; if(root == NULL) root = p; else { s = root; while(s != NULL) { par = s; if(x > s -> info) s = s-> right; else s = s -> left; } if(x < par -> info) par -> left = p; else par -> right = p; } }
- 13. Algorithm for Searching in BST If root.data is equal to search.data return root else while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node Endwhile return data not found end if
- 14. Searching in BST struct node* search(int data) { struct node *current = root; printf("Visiting elements: "); while(current->data != data) { if(current != NULL) printf("%d ",current->data); //go to left tree if(current->data > data) { current = current->leftChild; } //else go to right tree else { current = current->rightChild; } //not found if(current == NULL) { return NULL; } return current; } }
- 15. Deletion in BST Deletion of left most node (Minimum Data Item) s = root; while(s -> left != NULL) { par=s; s=s->left; } par->left=s->right; delete s;
- 16. Deletion in BST Deletion of Right most node (Maximum Data Item) s = root; while(s -> right != NULL) { par=s; s=s->right; } par->right=s->right; delete s;
- 17. Binary Search Tree Deletion Cases Different Cases for Deletion node 1- if deleted node has not null in its left or right link 2- if deleted node has left link null 3- if deleted node has right link null
- 18. BST Deletion Implementation class CBST:: delete_tree_node(int x) { struct node *p, *s, *rp, *f, *par; p=root; par=NULL; while((p!=NULL)&&(p->info!=x)) { par=p; if(x>p->info) p=p->right; else p=p->left; } if (p==NULL) { cout<<“ No Required Node exist Tree”; return; } if(p->left==NULL) rp=p->right; else if(p->right==NULL) rp=p->left; else { f=p; rp=p->right; s=rp->left; while(s!=NULL) { f=rp; rp=s; s=rp->left; } if(f!=p) { f->left=rp->right; rp->right=p->right; } } if(par==NULL) root=rp; if(p==par->right) par->right= rp; else par->left=rp; delete p; }
- 19. In-order Traversal Until all nodes are traversed − Step 1 − Recursively traverse left subtree. Step 2 − Visit root node. Step 3 − Recursively traverse right subtree. void inorder_traversal(struct node* root) { if(root != NULL) { inorder_traversal(root->leftChild); printf("%d ",root->data); inorder_traversal(root->rightChild);
- 20. Pre-Order Traversal Until all nodes are traversed − Step 1 − Visit root node. Step 2 − Recursively traverse left subtree. Step 3 − Recursively traverse right subtree. void pre_order_traversal(struct node* root) { if(root != NULL) { printf("%d ",root->data); pre_order_traversal(root->leftChild); pre_order_traversal(root->rightChild); } }
- 21. Post-Order Traversal Until all nodes are traversed − Step 1 − Recursively traverse left subtree. Step 2 − Recursively traverse right subtree. Step 3 − Visit root node. void post_order_traversal(struct node* root) { if(root != NULL) { post_order_traversal(root->leftChild); post_order_traversal(root->rightChild); printf("%d ", root->data); } }
- 22. AVL (Adelson Velski and landis)Tree / Balance Tree • Balance Factor: BF of any node= Height of left subtree – Height of right subtree • If BF = (-1, 0, 1) No rotation performed • Height of Tree • Reconstruction of Tree • Left rotation (left rotation is made when balance factor of any tree becomes -2) • Right rotation (right rotation is made when balance factor of any tree becomes +2)
- 23. Assignments: Question#1: Write a code for Pre-order, Post-order and In-order procedures of CBST to display data in required formats. Question#2: Write a code which will create a CBST and a coy function which will create exact copy of original CBST. Question#3: Write a code for CBST which will create a tree of even nodes and also for odd nodes. Question#4: Write a code which will create AVL Tree and determine its balance factor, and if balance factor is increasing from 2 or -2, then made its right/left rotations.