Problem 7 Below is a list of data structures and an application. Select two data
ID: 642065 • Letter: P
Question
Problem 7
Below is a list of data structures and an application. Select two data structures that you think would be the most useful for the particular application. Of the two data structures that you selected, pick the better of the two and explain why it is better for that particular application. State all relevant assumptions.
Data Structures:
Simple Array
Single Linked list
Binary Tree
Binary Search Tree
AVL Tree
B-Tree
Dictionary: You need a way to search a dictionary quickly to see if a word is spelled correctly. The access times need to be as quick as possible. You can assume that the entire dictionary can be loaded into memory and doesn
Explanation / Answer
simple array can be used but it is inefficient
binary search tree is next best option
Dictionary can be implemented using binary search tree. A binary search tree is a binary tree such that each node stores a key of a dictionary.
Key 'k' of a node is always greater than the keys present in its left sub tree.
Similarly, key 'k' of a node is always lesser than the keys present in its right sub tree.
Example:
well
/
bus xmas
/
air aero zebra
In the above example, keys present at the left sub-tree of the root node are lesser than the key of the root node. And also, the keys present at the right sub-tree are greater than the key of the root node.
To insert an element in a binary search tree, check whether the root is present or not. If root is absent, then the new node is the root.
If root node is present, check whether the key in new node is greater than or lesser than the key in root node.
If key in new node is less than the key in root, then traverse the left sub-tree recursively until we reach the leaf node. Then, insert the new node to the left(newnode < leaf)/right(newnode > leaf) of the leaf.
If the key in new node is greater than the key in root, then traverse the right sub-tree recursively until we reach the leaf node. Then, insert the new node to the left(newnode < leaf)/right of the leaf
apart from above given data structures ternary binary tree is best for dictionary search