Question

In: Computer Science

Compare and Contrast Hash Map to Binary Search Tree. Memory, Time Efficiency for Operations for Retrieving...

Compare and Contrast Hash Map to Binary Search Tree.

Memory, Time Efficiency for Operations for Retrieving Singular Values, Maintaining relationships between data.

Please be sure to use your own words.

Solutions

Expert Solution

To begin with definition, HashMap is a datastructure for storing key value pairs while Binary Search Tree is used for saving data in ordered manner. HashMap uses hashtable for storing data while Binary Search Tree uses a Binary Tree to store the data.

Memory:

Hashmap - O(n) as hashtable will be atmost of size 2*n.

Binary Search Tree - O(n) as For every data point we have single node and every node takes constant space so order of n.

Retreiving Singular Values/Search:

Hashmap - O(1) Asumming reasonably good hash function is used we can assume that search can be done in constant time.

Binary Search Tree - O(log n). Assuming BST is balanced we can retrieve values in atmost log n time.

Maintaining relationships between data:

Hashmap natively provides support for storing key value pairs i.e. related data.

For BST we need to implement custom node class and define their comparator to be able to maintain relationship between data while maintaining BST structure.


Related Solutions

Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree worst case and best case time. Learning Outcomes Describe AVL tree structure Trace and implement AVL tree operations Explain and prove AVL tree performance
Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the...
Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the template provided under the PolyLearn assignment, using the class TreeNode that is also provided. You may (should) implement helper methods that make your code easier to write, read, and understand. You will also need to write test cases of your own as you develop the methods. You may use iterative and/or recursive functions in your implementation. The following starter files are available . •...
​Define a tree. Distinguish between a tree and a binary tree. Distinguish between a binary tree and a binary search tree.
Define a tree. Distinguish between a tree and a binary tree. Distinguish between a binary tree and a binary search tree.
What does the level of a binary search tree mean in relation to its searching efficiency?...
What does the level of a binary search tree mean in relation to its searching efficiency? In your response discuss what the maximum number of levels to implement a search tree with 100 nodes and what is the minimum number of levels for 100 nodes. In your response to other students discuss if you agree with the other student’s number of levels, how the number of levels was determined and the Big-O efficiency of the maximum and a minimum number...
Beginning with an empty binary search tree, what binary search tree is formed when you insert...
Beginning with an empty binary search tree, what binary search tree is formed when you insert the following values in the given order – consider there alphabetical position for comparison. a. W, T, N, J, E, B, A b. W, T, N, A, B, E, J c. A, B, W, J, N, T, E d. B, T, E, A, N, W, J Alphabetical positions: A-1, B-2, E-5, J-10, N-14,T-20,W-23
In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order...
In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order traversal, preorder traversal, and find. Please separate the code in the four parts and explain in detail what is happening. Also, if you can please basic C language. If not, then I understand. Thank you for your time. The test cases are 'm', 'd', 'g', 'r', 'p', 'b', and 'x'. Output: Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: i Enter...
/** * This class implements a basic Binary Search Tree that supports insert and get operations....
/** * This class implements a basic Binary Search Tree that supports insert and get operations. In * addition, the implementation supports traversing the tree in pre-, post-, and in-order. Each node * of the tree stores a key, value pair. * * @param <K> The key type for this tree. Instances of this type are used to look up key, value * pairs in the tree. * @param <V> The value type for this tree. An instance of this...
Binary Tree Create a binary search tree using the given numbers in the order they’re presented....
Binary Tree Create a binary search tree using the given numbers in the order they’re presented. State if the resulting tree is FULL and/or BALANCED. 37, 20, 18, 56, 40, 42, 12, 5, 6, 77, 20, 54
PLEASE READ CAREFULY AND EXPLAIN YOUR WORK: (JavaScript) only Search the Tree: A binary search tree...
PLEASE READ CAREFULY AND EXPLAIN YOUR WORK: (JavaScript) only Search the Tree: A binary search tree is a data structure that consists of JavaScript objects called "nodes". A tree always has a root node which holds its own integer value property and can have up to two child nodes (or leaf nodes), a left and right property. A leaf node holds a value attribute and, likewise, a left and right attribute each potentially pointing to another node in the binary...
Use recursion function to derive computation time for Binary Search by drawing a recursion tree diagram...
Use recursion function to derive computation time for Binary Search by drawing a recursion tree diagram and using algebra calculation.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT