Homework Balanced Trees (1)

docx

School

Collin County Community College District *

*We aren’t endorsed by this school

Course

3345

Subject

Computer Science

Date

Jan 9, 2024

Type

docx

Pages

Uploaded by aisha13qurffff

2-3-4 Trees (Preemptive Split) 1. Draw the 2-3-4 (M=4) tree that results from inserting the keys: 1, 12, 8, 2, 25, 6, 14, 28, 17, 7, 52, 16, 48, 68, 3, 26, 29, 53, 55, 45. Show your work. 2. Remove in this order: 3, 17, 55, 1, 52, 48, 2, 14, 25 Show your work. 3. Splay Tree a. What is a splay operation? b. Why to prefer splay trees? c. Which of the following options is an application of splay trees?

i. cache Implementation ii. networks iii. send values iv. receive values d. When we have red-black trees and AVL trees that can perform most of operations in logarithmic times, then what is the need for splay trees? e. What is the disadvantage of using splay trees? 4. Given the BST below, show the BST that would result after inserting the key of value 10 if splaying is performed starting at the node that was inserted. 5. Given the BST below, show the BST that would result after inserting the key of value 180 if splaying is performed starting at the node that was inserted.

6. A nice property of splay trees is that each of Find, Insert and Delete takes O(logn) time. True/False? False 7. The keys of value N, N-1, N-2..., 4, 3, 2, 1 are inserted in this order in a splay tree. What is the final configuration of the tree? What is the cost in Big-Oh notation of each insert operation? 8. Assume now that the next 100 operations will be a mix of only Find(1), Find(2) and Find(3), i.e., search in the tree for either the key of value 1, or the key of value 2, or the key of value 3. After each successful search, splaying is performed from the node where the key was found. What are the 3 tree configurations that are possible after these 100 operations are completed? What is the cost in Big-Oh notation of each Find operation? 9. Red-Black Tree Show the result of inserting 50 into the Red-Black tree depicted below: 30 / \ 15 45 / \ 35 60

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

/ 55 10. Show the result of inserting 65 into the Red-Black tree depicted below: 30 / \ 15 45 / \ / \ 10 20 35 60 / \ 55 70 11. Priority Queue Describe the most time-efficient way to implement the operations listed below . Assume no duplicate values and that you can implement the operation as a member function of the class – with access to the underlying data structure. Then, give the tightest possible upper bound for the worst- case running time for each operation in terms of N. Merging two binary min-heaps (both implemented using an array) each containing N elements into a single binary min heap . Explanation: 12. Suppose there is a binary min-heap with exactly 4 nodes, containing items with priorities 3, 9, 11, and 15.

a. Show every potential binary min-heap that could match the description above. For each possibility, draw the appropriate tree and the array representation. b. For one of your answers to part (a), show what happens with 4 deleteMin operations. Clearly indicate which heap you are starting with and show the heap after each deleteMin. You can just draw the tree (not the array) after each step. 13. A three-heap with n elements can be stored in an array A, where A[0] contains the root of the tree. a. Draw the three -heap that results from inserting 5, 2, 8, 3, 6, 4, 9, 7, 1 in that order into an initially empty three-heap . You do not need to show the array representation of the heap. You are only required to show the final tree, although you draw intermediate trees. b. Assuming that elements are placed in the array starting at location A[0] , give expressions to calculate the left, middle, and right children of the element stored in A[i]: Left child: Middle child: Right child: c. Draw the array representation of your heap from part b. 14. Removing Arbitrary Items from Heaps: One way to remove any object from a binary min heap is to decrease its priority value by 1 and then call

deleteMin. An alternative is to remove it from the heap, thus creating a hole, and then repair the heap. a. Write pseudocode for an algorithm that performs the remove operation using the alternative approach described above. Your pseudocode should implement the method named remove (int index), where index is the index into the heap array for the object to be removed. Your pseudocode can call the following methods: insert, deleteMin, percolateUp, and percolateDown. You may assume that objects are just priority integers (no other data). b. What is the worst-case complexity of the algorithm you wrote in part (a)? 15. AVL Tree 1. Create a 10 AVL node object to be inserted into the AVL tree 2. At each insert, detect imbalance and fix the AVL tree 3. Report each imbalance detection and the node where it occurred; and output the message: Example Output: Imbalance condition occurred at inserting ISBN 12345; fixed in LeftRight Rotation Imbalance condition occurred at inserting ISBN 87654; fixed in Left Rotation Imbalance condition occurred at inserting ISBN 974321; fixed in RightLeft Rotation class AVLNode { String ISBN; String Title; int height; AVLNode leftPtr; AVLNode rightPtr; }

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Related Documents

SU_NSG6601_W4_A2_Sornoza_S.docx

C207 Task 2 Jones.docx

practiceProblems-2.pdf

Module 6_ Logic Model.docx

Lab9Unit5.docx

Analyzing a Network Issue.docx

Week 8 SAFMEDS Assignment copy.pdf

Week5_SAFMEDS Assignment copy.pdf

Week 8 SAFMEDS Assignment copy.docx

IT-FP2280 Assessment 2.docx

IT FP2280- Assessment 6.docx

Murphy_Lab5_WorkInsideLab.docx

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

New Perspectives on HTML5, CSS3, and JavaScript

Computer Science

ISBN:9781305503922

Author:Patrick M. Carey

Publisher:Cengage Learning

Oracle 12c: SQL

Computer Science

ISBN:9781305251038

Author:Joan Casteel

Publisher:Cengage Learning

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE

Computer Science

ISBN:9780357392676

Author:FREUND, Steven

Publisher:CENGAGE L

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
New Perspectives on HTML5, CSS3, and JavaScript
Computer Science
ISBN:9781305503922
Author:Patrick M. Carey
Publisher:Cengage Learning
Oracle 12c: SQL
Computer Science
ISBN:9781305251038
Author:Joan Casteel
Publisher:Cengage Learning
COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:9780357392676
Author:FREUND, Steven
Publisher:CENGAGE L