Threaded Binary Tree

OVERVIEW:
Introduction
Definition
Example of Threaded BT.
Types & Structure
One-way .
Double-way.
Structure.
Traversal
Algorithm for Traversal
Traversal Example
Inserting
Algorithm for Inserting
Inserting Example

Comparison With Binary Tree
Advantages and Disadvantages
Why Threaded BT are used?
Conclusion
Reference

1. Presented to: Md. Shamsujjoha Senior Lecturer of CSE department East West University Presented by: Md . Khabbab Hossain Tusher Date:03/04/2016 Threaded Binary Tree

2. Threaded binary tree OVERVIEW: Introduction Definition Example of Threaded BT. Types & Structure One-way . Double-way. Structure. Traversal Algorithm for Traversal Traversal Example Inserting Algorithm for Inserting Inserting Example Comparison With Binary Tree Advantages and Disadvantages Why Threaded BT are used? Conclusion Reference

3. A binary search tree in which each node uses an otherwise-empty left child link to refer to the node's in-order predecessor and an empty right child link to refer to its in-Order Successor. Definition Slide 1

4. A Simple Binary Tree A B D E C G F Slide 2

5. A B C Null D Null Null E Null Null G Null Null F Null Slide 3 Threaded binary tree

6. Threaded Binary Tree In above binary tree, there are 8 null pointers & actual 6 pointers. In all there are 14 pointers. We can generalize it that for any binary tree with n nodes there will be (n+1) null pointers and 2n total pointers. The objective here to make effective use of these null pointers. A. J. perils & C. Thornton jointly proposed idea to make effective use of these null pointers. According to this idea we are going to replace all the null pointers by the appropriate pointer values called threads. Slide 4

7. And binary tree with such pointers are called threaded tree. In the memory representation of a threaded binary tree, it is necessary to distinguish between a normal pointer and a thread. Slide 5

8. Threaded Binary Tree: One-Way We will use the right thread only in this case. T o implement threads we need to use in-order successor of the tree Slide 6

9. Threaded Binary Tree: One-Way A B C Null D Null E Null G Null Null F Inorder Traversal of The tree: D, B, E, A, F, C, G Slide 7

10. Two way Threaded Tree/Double Threads Again two-way threading has left pointer of the first node and right pointer of the last node will contain the null value. The header nodes is called two-way threading with header node threaded binary tree. Slide 8

11. A B D Inorder Traversal of The tree: D, B, E, A, F, C, G E C F G Dangling Dangling Slide 9

12. • Dangling can be solved as follows Introduce a header node. The left and right pointer of the header node are treated as normal links and are initialized to point to header node itself. Slide 10

13. A B D Inorder Traversal of The tree: D, B, E, A, F, C, G E C F G Head Slide 11

14. Structure of Thread BT Node structure For the purpose of our evaluation algorithm, we assume each node has five fields : LTag Left data Right RTag We define this node structure in C as: Struct Node{ int data; struct Node *Left,*Right; bool Ltag ; boolRtag ; }; Slide 12

15. L.Tag L.Child head R.child R.Tag 1 A 1 1 1 0 D 0 0 E 0 0 F 0 0 G 0 1 B 1 1 C 1 Inorder Traversal of The tree: D B E A F C G Slide 13

16. Threaded Tree Traversal We start at the leftmost node in the tree, print it, and follow its right thread If we follow a thread to the right, we output the node and continue to its right. If we follow a link to the right, we go to the leftmost node, print it, and continue. Slide 14

17. Threaded Tree Traversal 8 7 5 3 1 6 Start at leftmost node, print it Outpu t 1 9 Slide 15

18. Threaded Tree Traversal 8 7 5 3 1 6 Follow thread to right, print node Outpu t 1 3 9 Slide 16

19. Threaded Tree Traversal 8 7 5 3 1 6 Follow link to right, go to leftmost node and print Outpu t 1 3 5 9 Slide 17

20. Threaded Tree Traversal 8 7 5 3 1 6 Follow thread to right, print node Outpu t 1 3 5 6 9 Slide 18

21. Threaded Tree Traversal 8 7 5 3 1 6 Follow link to right, go to leftmost node and print Outpu t 1 3 5 6 7 9 Slide 19

22. Threaded Tree Traversal 8 7 5 3 1 6 9 Follow thread to right, print node Outpu t 1 3 5 6 7 8 Slide 20

23. Threaded Tree Traversal 8 7 5 3 9 1 6 Follow link to right, go to leftmost node and print Outpu t 1 3 5 6 7 8 9 Slide 21

24. void inOrder ( struct Node *root) {      struct Node *cur = leftmost(root);     while (cur != NULL)     {          printf ("%d ", cur->data);           // If this node is a thread node, then go to         // inorder successor         if (cur-> rightThread )             cur = cur->right;         else // Else go to the leftmost child in right subtree             cur = leftmost(cur->right);     } } 8 7 5 3 1 6 9 Slide 22

25. Threaded Binary Trees In threaded binary trees, The null pointers are used as thread. We can use the null pointers which is a efficient way to use computers memory. Traversal is easy. Completed without using stack or reccursive function. Structure is complex. Insertion and deletion takes more time. Normal Binary Trees In a normal binary trees, the null pointers remains null. We can’t use null pointers so it is a wastage of memory. Traverse is not easy and not memory efficient. Less complex than Threaded binary tree. Less Time consuming than Threaded Binary tree. Comparison of Threaded BT Slide 23

26. Inserting a node to Threaded Binary Tree: Inserting a node X as the right child of a nodes . 1 st Case: - If G has an empty right subtree, then the insertion is simple Slide 24

27. A B D Inserting X as a right child of G E C F G Head X New inorder traversal is: D,B,E,A,F,C,G,X Slide 25

28. 2 nd Case: If the right subtree of C is not empty, then this right child is made the right child of X after insertion . Slide 26

29. A B D New Inorder Traversal of The tree: D, B, E, A, F, C, X,G E F G Head x C Slide 27

30. Advantage 1. By doing threading we avoid the recursive method of traversing a Tree , which doesn’t use of stack and consumes a lot of memory and time . 2 . The node can keep record of its root . 3. Backward Traverse is possible. 4. Applicable in most types of the binary tree. Disadvantage 1. This makes the Tree more complex . 2 . More prone to errors when both the child are not present & both values of nodes pointer to their ancestors. 3. Lot of time consumes when deletion or insertion is performed. Threaded binary tree Slide 28

31. Same as any kind of Binary Tree. Used in search and Traverse based work APPLICATIONS Slide 29

32. Conclusion E xcellent concept in modern computer science. S aves Time and memory. Traversal and search are very efficient. I nsertion and deletion are not so efficient. Slide 30

33. References http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack / http:// www.delorie.com/gnu/docs/avl/libavl_183.html http:// www.math-cs.gordon.edu/courses/cs321/lectures/threaded.html https://prezi.com/1yitau0wnwlg/threaded-binary-tree-in-data-structures / http:// stackoverflow.com/questions/6744770/confusion-with-threaded-binary-tree Various Text Book for data structure.

34. THANK YOU

35. ANY QUESTION Or Suggestion? Contacts us :[email protected]/ [email protected]