Homework 07
METU CENG310
Data Structures and Algorithms with Python
1 Binary Search Trees
Task-1 For each of the following operation, draw the final state of the binary search tree after the remove
operation.
• Remove node 65 from the original tree.
• Remove node 16 from the original tree.
• Remove node 12 from the original tree.
• Remove node 42 from the original tree.
Task-2 Write a pseudo code for the before() binary search tree operation.
2 AVL Trees
Task-3 Show the results of inserting 23, 11, 48, 57, 90, 34, 69, 72, 78, 82, 81 into an initially empty AVL tree.
Show the state of the tree after each insertion.
Task-4 Show the results of deleting 69, 23, and 11, in this respective order, from the AVL tree that is reached
at Task-3. Show the state of the tree after each deletion.
3 Multiway Search Trees
Task-4 Show the results of inserting 23, 11, 48, 57, 90, 34, 69, 72, 78, 82, 81, 71, 77, 73, 76, 75, 74 into an
initially empty (2,4) tree. Show the state of the tree after each insertion.
4 Instructions
Pertaining to the answers of this homework, correct typing of superscripts (e.g., n
2
) and subscripts (e.g., n0)
matters. Due to this reason, this homework may be done on paper and returned as a PDF file containing
the answer sheet captures (photos, scanned files). If you would like you can use MS Word or Latex, but your
1
deliverable has to be a single PDF file. PDF file should be created so that the answers appears in the same
order as the questions shown in the homework assignment document.
A Homework-07 page will be generated soon after the start date of this homework. All deliveries should
be done over ODTUClass. Please also be aware of the late penalties (Please check the Announcements –
Homework and Assignment Policy in ODTUClass if you have not already done so.). Should you have any
questions pertaining to homework tasks, please ask them in advance (not on the due date) for your own
convenience.
2
