(a)
Explain the assumption that Line 7 can be performed in O(1) actual time.
(a)
Explanation of Solution
For performing line 7, the time taken is proportional to the number of children does x have. For adding each child in the root list requires to update the parent’s pointer to NULL instead of x.
Therefore, the updating of parent pointer to x is wrong in this assumption.
(b)
Give anupper bound on the actual time of PISANO-DELETE, when node x is not inH.min .
(b)
Explanation of Solution
An actual cost of bounded by x.degree and updating all children of x takes constant time so, the actual time of PISANO-DELETE is
Hence, the upper bound on the actual time is
(c)
Use PISANO-DELETE( H,x ), describe that the node x is not a root, bound the potential of H’ in terms of x.degree, c, t ( H ) and m ( H ).
(c)
Explanation of Solution
Explanation:
As given CASCASDING-CUT rule we know that if it marked more than one node then
If the children increased from the previous that x had then equation will become
Now taking the consideration and according to question, combiningthese expressions the bound of potential is −
(d)
Conclude that the amortized time for PISANO-DELETE is asymptotically no better than for FIB-DELETE, even when x
(d)
Explanation of Solution
The amortized time for PISANO-DELETE is asymptotically is
When x
Therefore, the amortized time for PISANO-DELETE is asymptotically no better than for FIB-DELETE, even when x
Want to see more full solutions like this?
Chapter 19 Solutions
Introduction to Algorithms
- Using Java Design an algorithm for the following operations for a binary tree BT, and show the worst-case running times for each implementation:preorderNext(x): return the node visited after node x in a pre-order traversal of BT.postorderNext(x): return the node visited after node x in a post-order traversal of BT.inorderNext(x): return the node visited after node x in an in-order traversal of BT.arrow_forwardEven though binary tree sort uses a self-balancing binary search tree, it is still slower than merge sort. In the worst case, it takes O(n log n) time.arrow_forwardIn the worst case, binary tree sort utilising a self-balancing binary search tree requires O(n log n) time, but it is still slower than merge sort.arrow_forward
- Use a triply linked structure as opposed to an array for implementing a priority queue using a heapordered binary tree. Each node will require three links: two to move up the tree and one to move down it. Even if the maximum size of the priority queue is unknown at the outset, your solution should nonetheless provide logarithmic running times for each operation.arrow_forwardSplaysort. Splaysort is similar to heapsort and described in (VI.13 (p. 22). It is reportedly quite efficient in practice. In this question, we want to simulate this algorithm to sort the following input sequence of numbers: 89, 32, 11, 52, 46, 76, 29, 99, 23, 60, 42, 24. Begin by inserting each of these numbers into an initially empty splay tree, and then repeatedly deleteMin. Show the splay trees at the end of each operation.arrow_forwardHow many references must you change to insert a node to a binary search tree? What is the average time complexity for search, insert and delete operations in a balanced Binary Search Tree of size n? What is the worst case time complexity for search, insert and delete operations in a Binary Search Tree of size n? Suppose some numbers (given) are inserted in that order into an initially empty binary search tree. What is the In-order/Pre-order/Post-order traversal sequence of the resultant tree?arrow_forward
- There is an algorithm for making the heap complete:1. Remove the node at the root.2. Move the node in the last position to the root.3. Trickle the last node down until it is below.When this algorithm is applied continually, the data is removed from theheap in sorted order. imlement the code for the Remove and TrickleDownmethods:arrow_forwardCreate a min-heap from a binary search tree. Show the technique in action using the following binary search tree.arrow_forwardIn the heapify algorithm, heapilying a node Z is implemented by Select one a. Compare and exchange the values of the let child and nght chld of node 2 b. Compare and exchange the values of the node Z and its parent node c. Delete the node Z and its chid d Find the largest element among the node Z and its children, exchange the values of the largest and node Z. and recursively caling heapily r the largest Which of the following is not correct about the Quick-Sort algorithm Select one a Include a partitioning procedure b. Designed based on Divide and Conquer e Required two recursive call of the algonithm on the left and right parts of the partinoned array d. Required extra memory to implement the partiton procedurearrow_forward
- - What is the worst-case performance of the remove method in a full binary search tree with linked nodes? O(n) O(log n) O(n2) O(1) - What is the worst-case performance of the remove method in a binary search tree with linked nodes? O(n2) O(n) O(log n) O(1)arrow_forwardThe BST remove algorithm traverses the tree from the root to find the node to remove. When the node being removed has 2 children, the node's successor is found and a recursive call is made. One node is visited per level, and in the worst-case scenario, the tree is traversed twice from the root to a leaf. A BST with N nodes has at least log2N levels and at most N levels. Therefore, the runtime complexity of removal is best case O(logN) and worst case O(N). Two pointers are used to traverse the tree during removal. When the node being removed has 2 children, a third pointer and a copy of one node's data are also used, and one recursive call is made. Thus, the space complexity of removal is always O(1)." I have to explain this clearly! and the advantages of the BST algorithimarrow_forwardConstruct a priority queue using a heapordered binary tree, but instead of an array, use a triply linked structure. Each node will require three links: two to go down the tree and one to traverse up the tree. Even if no maximum priority-queue size is specified ahead of time, your solution should ensure logarithmic running time per operation.arrow_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education