[3 points] Draw an Adelson-Velskii and Landis (AVL) tree for the following nodes: 64,28, 51, 66, 15, 36, 74, 73, 12, 78, 82, 83, 86, 99, 21.Hint: No coding is involved with this problem. You need to draw the actual tree for this problem.When you draw your tree, it must an AVL tree instead of just a regular binary tree or abinary search tree (BST). There are a few ways that you can arrange the layout for this tree;however, remember data within the tree must follow the rules of an AVL tree. I recommendthat you first draw the tree with links and empty nodes. Then sort the items in the list andplace them in the appropriate places within the tree so that it forms an AVL tree.(b) [2 points] Briefly explain the differences between a binary search tree and a regular binarytree. Which tree has a better advantage over the other? Briefly explain why.

 

1Problem Set 3: Trees and HashingCS3330 Data Structures and AlgorithmsTerm 1 2016: August 15 – October 15Dr. Jack DavaultOverview:This assignment will cover that material on trees and hashing. Provide the solutionsfor the problems in this assignment within a single Microsoft Word document. However, a PowerPoint file or scanned handwritten drawing for Problem 1(a) is fine. Remember to include yourname and course number within all documents and files that you submit.1.[5 points] Trees.Read the assigned chapter and notes for Week 5 located in the LearningActivities area in Blackboard. Then answer the following questions:(a)[3 points] Draw an Adelson-Velskii and Landis (AVL) tree for the following nodes: 64,28, 51, 66, 15, 36, 74, 73, 12, 78, 82, 83, 86, 99, 21.Hint:No coding is involved with this problem. You need to draw the actual tree for this problem.When you draw your tree, it must an AVL tree instead of just a regular binary tree or abinary search tree (BST). There are a few ways that you can arrange the layout for this tree;however, remember data within the tree must follow the rules of an AVL tree. I recommendthat you first draw the tree with links and empty nodes. Then sort the items in the list andplace them in the appropriate places within the tree so that it forms an AVL tree.(b)[2 points] Briefly explain the differences between a binary search tree and a regular binarytree. Which tree has a better advantage over the other? Briefly explain why.2.[5 points] Hashing.Read the assigned chapter and notes for Week 6 located in the LearningActivities area in Blackboard. Then provide solutions to the following problems:(a)[2 points] Briefly explain the purpose of quadratic probing and provide an example of amathematical function used to implement it based on the size of the hash table. Also, brieflyexplain the problem associated with quadratic probing in terms of the number of itemswithin the hash table.(b)[3 points] Perform an Internet search and briefly discuss in a few paragraphs a computerrelated algorithm based on hashing. Provide an example with a diagram or table to helpillustrate how the algorithm works. List your sources at the end of your paragraphs usingAPA format.Other Notes:Submit your solutions using the Problem Set 3 link provided in the Assignmentsarea. As usual, please do not hesitate to ask questions in theAsk the Instructorforum or via e-mail.

Attachments:

• 1495159033-PS3.pdf