The Linked List (LL)Inserting the element into LLRemoving the element from LLReporting in sorted orderHeapHeap RepresentationsHeap InsertionHeap InsertionSlide 9Heapify AlgorithmExtracting the Maximum from a Heap:Building a HeapBuilding a Heap (cont’d.)Slide 14Finding an ElementRemoving an ElementSlide 17The Binary Search Tree (BST)BST- PropertyExample:In-Order Tree walkIn-Order TraversalSlide 23Other Tree WalksSearching in BST:Examples:BST InsertionInsert KeyLocating the MinimumApplication: SortingSuccessorSlide 32DeletionDeletion:Slide 35Delete ProcedureThe Linked List (LL)Each node x in a linked list contains:Key(x)headkey[x]- The value stored at x.next[x]- Pointer to left child of x.The while list is accessed by a head pointer to the first node.Last one points to NILnext[x]Inserting the element into LLFind a place for it.Point “new’s” next to the next.Point “previous’s”next to new.Key(x)headnext[x]Key(x)next[x]Key(x)next[x]Key(x)next[x]New elementKey(x)next[x]Key(x)next[x]head headRemoving the element from LLFind the element.Point “previous’s” next to the next.Point previous to new.headKey(x)next[x]Key(x)next[x]Key(x)next[x]Key(x)next[x]Deleted elementKey(x)next[x]Key(x)next[x]head headReporting in sorted orderIf you keep the list sorted at all the times the reporting it in sorted order is as simple as iterating through the list and reporting the elements as you encounter them.HeapA heap is a binary tree storing keys, with the following properties:partial order:key (child) < key(parent)left-filled levels:the last level is left-filledthe other levels are fullXT OG S M NA ER B IHeap RepresentationsXT OG S M NA ER B I13284951011 12X T O G S M N A E R B I1 2 3 4 5 6 7 8 9 10 11 126 7• left_child(i)= 2i• right_child(i) = 2i+1• parent(j) = j div 2Heap InsertionXT OG S M NA ER B IXT OG S M NA ER B IPPXT OG S P NA ER B IM•Add the key in the next available spot in the heap.•Upheap checks if the new node is greater than its parent. If so, it switches the two.•Upheap continues up the treeHeap Insertion XT OG S P NA ER B IMXT PG S O NA ER B IMHeap InsertionUpheap terminates when new key is less than the key of its parent or the top of the heap is reached.(total #switches) <= (height of tree- 1) =log nXT PG S O NA ER B IMHeapify AlgorithmAssumes L and R sub-trees of i are already Heaps and makes It's sub-tree a Heap:Heapify(A,i,n)If (2i<=n) & (A[2i]>A[i]) Then largest=2iElse largest=iIf (2i+1<=n) & (A[2i+1]>A[largest]) Then largest=2i+1If (largest != i) Then Exchange (A[i],A[largest]) Heapify(A,largest,n) EndifEnd HeapifyExtracting the Maximum from a Heap:Here is the algorithm:Heap-Extract-Max(A)Remove A[1]A[1]=A[n]n=n-1Heapify(a,1,n)End Heap-Extract-MaxXT PG S O NA ER B IMMT PG S O NA ER B I123Building a HeapBuilds a heap from an unsorted array:Build_Heap(A,n)For i=floor(n/2) down to 1 doHeapify(A,i,n)End Build_HeapExample:4 1 3 2 169 10148 7A41 32 16 9 1014 87iBuilding a Heap (cont’d.)41 32 16 9 1014 87i41 31416 9 10287i413216 9101487i4132169101487iBuilding a Heap (cont’d.)4 132169101487Finding an ElementMust look at each element of the array:For i=1 to n doif A(i) == bbreak;Example:AX T O G S M N A E R B I1 2 3 4 5 6 7 8 9 10 11 12XT OG S M NA ER B I13284951011 126 7Removing an ElementMust find it firstAfter that similar to remove MaxRemove A[i]A[i]=A[n]n=n-1Heapify(a,i,n)AX T O G S M N A E R B I1 2 3 4 5 6 7 8 9 10 11 12XT OG S M NA ER B I13284951011 126 7Removing an ElementXT OG S M NA ER B I13284951011 126 7XT OG I M NA ER B132849510116 7XT OG R M NA EI B132849510116 7The Binary Search Tree (BST)Each node x in a binary search tree (BST) contains:P(x)Key(x)xkey[x]- The value stored at x.left[x]- Pointer to left child of x.right[x]- Pointer to right child of x.p[x]- Pointer to parent of x.left[x] right[x]BST- PropertyKeys in BST satisfy the following properties:Let x be a node in a BST:If y is in the left subtree of x then:key[y]<=key[x] If y is in the right subtree of x then:key[y]>key[x]Example:• Two valid BST’s for the keys: 2,3,5,5,7,8.53 782 5237585In-Order Tree walkCan print keys in BST with in-order tree walk.Key of each node printed between keys in left and those in right subtrees.Prints elements in monotonically increasing order.Running time?In-Order TraversalInorder-Tree-Walk(x)1: If x!=NIL then2: Inorder-Tree-Walk(left[x]) 3: Print(key[x])4: Inorder-Tree-Walk(right[x]) What is the recurrence for T(n)?What is the running time?In-Order TraversalIn-Order traversal can be thought of as a projection of BST nodes on an interval.At most 2d nodes at level d=0,1,2,…5378252 3 5 5 7 8Other Tree WalksPreorder-Tree-Walk(x)1: If x!=NIL then2: Print(key[x])3: Preorder-Tree-Walk(left[x]) 4: Preorder-Tree-Walk(right[x]) Postorder-Tree-Walk(x)1: If x!=NIL then2: Postorder-Tree-Walk(left[x]) 3: Postorder-Tree-Walk(right[x]) 4: Print(key[x])Searching in BST:To find element with key k in tree T:Compare k with the rootIf k<key [root[T ]] search for k in the left sub-treeOtherwise, search for k in the right sub-tree Search(T,k)1: x=root[T]2: If x=NIL then return(“not found”)3: If k=key[x] then return(“found the key”) 4: If k< key[x] then Search(left[x],k)5: else Search(right[x],k)Examples:Search(T,11)53 10112 547Search(T,6)53 10112 547BST InsertionBasic idea: similar to search.BST-Insert: Take an element z (whose right and left children are NIL) and insert it into T. Find a place where z belongs, using code similar to that of Search. Add z there.Insert KeyBST-Insert(T,z)1: y=NIL2: x=root[T]3: While x!=NIL do4: y=x;5: if key[z]<key[x] then6: x=left[x]7: else x=right[x]8: p[z]=y9: if y=NIL the root[T]=z 10: else if key[z]<key[y] then left[y]=z 11: else right[y]=z 53 10112 547Insert(T,8)8Locating the MinimumBST-Minimum(T)1: x=root[T]2: While left[x]!=NIL do3: x=left[x] 4: return x53 10112 5478Application: SortingCan use BST-Insert and Inorder-Tree-Walk to sort list of n numbersBST-Sort1: root[T]=NIL2: for i=1to n do3: BST-Insert(T,A[i])4: Inorder-Tree-Walk(T)53 1054785510Sort Input: 5, 10, 3, 5, 7, 5, 4, 8 Inorder Walk: 3, 4, 5, 5, 7, 8, 10SuccessorGiven x, find node with smallest key greater than key[x]. Here are two cases depending on rightsubtree of x.Successor Case 1:The right subtree of x is not