1) Answer the following questions, do not give just an answer, show all your work.
a) Calculate the total depth of the nodes in a complete binary tree of height h. Note that total depth is 5 if height is 2 where the depth of the root is one and there are two nodes with depth 2.
b) Calculate the average number of comparisons for a successful search operation in a binary search tree which has the structural property of being complete binary tree.
c) Is there a restriction on the number of nodes in a full binary tree? What is the number of internal nodes and number of leaves in an n node full binary tree?
2) Research about the quadtree structure for two-dimensional point data. Consider using the binary tree representation of general trees in our textbook to implement the quadtree structure.
Insert the following elements one by one into an empty quadtree. Show the nodes traversed during each insertion and resulting tree after each insertion. Assume that the range is (0, 100) for both dimensions. Note that you are expected to draw the binary tree representation of the quadtree.
(30,30), (20,15), (50,40), (10,12), (40,20), (25,60), (15,25)
3) Implement a binary heap (extend the BinaryTree class in the text book) class using node-link structure. Your ternary heap should satisfy the structural property of being a complete tree besides the heap order property. Note that you may need to add some more data fields in the Node class. Implement some additional methods in your binary heap; incrementing the key value of an element, merging two heap structure. Explain your implementation and analyze the methods in your report.
4) Implement an array based binary search tree (implement the SearchTree interface) class. You should use an array to represent the binary tree as in binary heap structure. Explain your implementation and analyze the methods in your report.
REPORT RULES:
• Add all javadoc documentations for classes, methods, variables …etc. All explanations must
be meaningful and understandable.
- You should submit your homework code, Javadoc, and report to MS Teams in a “studentid_hw5.tar.gz” file.
- Use the given homework format including selected parts from the table below:
Detailed system requirements
✔
Class diagrams
✔
Problem solutions approach
✔
Test cases
✔
Running command and results
✔
GRADING :
• No OOP design: -100 -No error handling: -50
• No javadoc documentation: -50
• No report: -90
• Disobey restrictions: -100
• Cheating: -200
◦ Your solution is evaluated over 100 as your performance.
CONTACT : - Teaching Assistant Ferda Abbasoğlu, ferdaabbasoglu@gtu.edu.tr
• Using the Homework Discussion Forum in MSTeams is advised for your questions about the homework.
