THREADED BINARY TREE AND BINARY SEARCH TREE

DATA STRUCRURE: THREADED BINARY TREE AND BINARY SEARCH TREE, INSERTION & DELEION OF NODES

1. THREADED BINARY TREE AND BINARY SEARCH TREE

2. Trees Definition: A tree is a finite set of one or more nodes such that: There is a specially designated node called the root. The remaining nodes are partitioned into n ≥ 0 disjoint sets T 1 , …, T n , where each of these sets is a tree. We call T 1 , …, T n the subtrees of the root.

3. Threaded Binary Tree In a linked representation of binary tree, there are more null links can be replaced by pointers, called threads to other nodes. A left null link of the node is replaced with the address of its inorder predecessor , similarly a right null link of node is replaced with the address of its inorder successor.

4. Threaded Trees Binary trees have a lot of wasted space: the leaf nodes each have 2 null pointers We can use these pointers to help us in inorder traversals We have the pointers reference the next node in an inorder traversal; called threads We need to know if a pointer is an actual link or a thread, so we keep a boolean for each pointer

5. Threaded Binary Tree Threading Rules A 0 Right Child field at node p is replaced by a pointer to the node that would be visited after p when traversing the tree in inorder. That is, it is replaced by the inorder successor of p. A 0 Left Child link at node p is replaced by a pointer to the node that immediately precedes node p in inorder (i.e., it is replaced by the inorder predecessor of p).

6. Threaded Tree FIGURE : A H I B D E C G F Inorder sequence: H, D, I, B, E, A, F, C, G

7. Threads To distinguish between normal pointers and threads, two boolean fields, LeftThread and RightThread, are added to the record in memory representation. t- >LeftChild = TRUE => t->LeftChild is a thread t->LeftChild = FALSE => t->LeftChild is a pointer to the left child.

8. Threads To avoid dangling threads, a head node is used in representing a binary tree. The original tree becomes the left subtree of the head node. Empty Binary Tree TRUE FALSE LeftThread LeftChild RightChild RightThread data

9. Memory Representation of Threaded Tree of Figure 5.20 f - f f A f f B f f D f t H t t I t t E t f B f f D f t E t

10. Inserting A Node to A Threaded Binary Tree Inserting a node r as the right child of a node s. If s has an empty right subtree, then the insertion is simple and diagram in Figure 5.23(a). If the right subtree of s is not empty, the this right subtree is made the right subtree of r after insertion. When thisis done, r becomes the inorder predecessor of a node that has a LdeftThread==TRUE field, and consequently there is an thread which has to be updated to point to r. The node containing this thread was previously the inorder successor of s. Figure 5.23(b) illustrates the insertion for this case.

11. Insertion of r As A Right Child of s in A Threaded Binary Tree s r s r before after

12. Threaded Tree Example 8 7 5 3 11 13 1 6 9

13. 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

14. Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Start at leftmost node, print it Outpu t 1

15. Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow thread to right, print node Outpu t 1 3

16. Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow link to right, go to leftmost node and print Outpu t 1 3 5

17. Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow thread to right, print node Outpu t 1 3 5 6

18. Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow link to right, go to leftmost node and print Outpu t 1 3 5 6 7

19. Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow thread to right, print node Outpu t 1 3 5 6 7 8

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

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

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

23. Threaded Tree Modification We’re still wasting pointers, since half of our leafs’ pointers are still null We can add threads to the previous node in an inorder traversal as well, which we can use to traverse the tree backwards or even to do postorder traversals

24. Threaded Tree Modification 8 7 5 3 11 13 1 6 9

25. Advantages of threaded binary tree. Non-recursive preorder traversal can be implemented without a stack. Non-recursive inorder traversal can be implemented without a stack. Non-recursive postorder traversal can be implemented without a stack.

26. Binary Search Tree Binary search tree Every element has a unique key. The keys in a nonempty left sub tree ( right sub tree ) are smaller ( larger ) than the key in the root of subtree. The left and right subtrees are also binary search trees.

27. Binary Search Tree Heap needs O(n) to perform deletion of a non-priority queue. This may not be the best solution. Binary search tree provide a better performance for search, insertion, and deletion. Definition: A binary serach tree is a binary tree. It may be empty. If it is not empty then it satisfies the following properties: Every element has a key and no two elements have the same key (i.e., the keys are distinct) The keys (if any) in the left subtree are smaller than the key in the root. The keys (if any) in the right subtree are larger than the key in the root. The left and right subtrees are also binary search trees.

28. Binary Trees 20 15 25 14 10 22 30 5 40 2 60 70 80 65 Not binary search tree Binary search trees

29. Searching A Binary Search Tree If the root is 0, then this is an empty tree. No search is needed. If the root is not 0, compare the x with the key of root. If x equals to the key of the root, then it ’ s done. If x is less than the key of the root, then no elements in the right subtree can have key value x. We only need to search the left tree. If x larger than the key of the root, only the right subtree is to be searched .

30. Search Binary Search Tree by Rank To search a binary search tree by the ranks of the elements in the tree, we need additional field “ LeftSize ” . LeftSize is the number of the elements in the left subtree of a node plus one. It is obvious that a binary search tree of height h can be searched by key as well as by rank in O(h) time.

31. Searching A Binary Search Tree by Rank template <class Type> BstNode <Type>* BST<Type>::Search(int k) // Search the binary search tree for the kth smallest element { BstNode<Type> *t = root; while(t) { if (k == t->LeftSize) return n; if (k < t->LeftSize) t = t->LeftChild; else { k -= LeftSize; t = t->RightChild; } } return 0; }

32. Insertion To A Binary Search Tree Before insertion is performed, a search must be done to make sure that the value to be inserted is not already in the tree. If the search fails, then we know the value is not in the tree. So it can be inserted into the tree. It takes O(h) to insert a node to a binary search tree.

33. Inserting Into A Binary Search Tree 30 5 40 2 80 30 5 40 2 80 35

34. Insertion Into A Binary Search Tree Template <class Type> Boolean BST<Type>::Insert(const Element<Type>& x) // insert x into the binary search tree { // Search for x.key, q is the parent of p BstNode<Type> *p = root; BstNode<Type> *q = 0; while(p) { q = p; if (x.key == p->data.key) return FALSE; // x.key is already in tree if (x.key < p->data.key) p = p->LeftChild; else p = p->RightChild; } // Perform insertion p = new BstNode<Type>; p->LeftChild = p->RightChild = 0; p->data = x; if (!root) root = p; else if (x.key < q->data.key) q->LeftChild = p; else q->RightChild = p; return TRUE; }

35. Deletion From A Binary Search Tree Delete a leaf node A leaf node which is a right child of its parent A leaf node which is a left child of its parent Delete a non-leaf node A node that has one child A node that has two children Replaced by the largest element in its left subtree, or Replaced by the smallest element in its right subtree Again, the delete function has complexity of O(h)

36. 2 5 Deleting From A Binary Search Tree 30 40 2 80 30 5 40 2 80 35 30

37. Deleting From A Binary Search Tree 2 5 30 40 2 80 30 2 5 30 40 2 80 5 2 2 30 40 80 5

38. THANK YOU