g Q 2 Suppose I need a data structure having the following characteristics: a) must be very space efficient, and b) I have a good idea of how much total data needs to be stored. b) must have fastest access possible, and c) once I add an item to the data structure, I do not remove it. Part 1: What data structure would I choose and why? (2,4) Part 2: If I remove characteristic b, what similar data structure is a possible candidate?

Question

Wayne Conley

Computers & Technology

8 November, 21:46

g Q 2 Suppose I need a data structure having the following characteristics: a) must be very space efficient, and b) I have a good idea of how much total data needs to be stored. b) must have fastest access possible, and c) once I add an item to the data structure, I do not remove it. Part 1: What data structure would I choose and why? (2,4) Part 2: If I remove characteristic b, what similar data structure is a possible candidate?

+2

Answers (1)

Know the Answer?

Colt Prince · Answer 1

a. I would choose an advanced data structure like dispersion tables.

Scatter tables, better known as hash tables, are one of the most frequently used data structures. To get an initial idea, scatter tables make it possible to have a structure that relates a key to a value, such as a dictionary. Internally, the scatter tables are an array. Each of the array positions can contain none, one or more dictionary entries.

It will normally contain a maximum of one, which allows quick access to the elements, avoiding a search in most cases. To know at which position in the array to search or insert a key, a scatter function is used. A scatter function relates each key to an integer value. Two equal keys must have the same dispersion value, also called a hash value, but two different keys can have the same dispersion value, which would cause a collision.

B. If I eliminated the characteristic b, a possible candidate keeping the previous characteristics would be: Balanced binary trees

Balanced binary trees are data structures that store key-data pairs, in an orderly way according to the keys, and allow quick access to the data, given a particular key, and to go through all the elements in order.

They are appropriate for large amounts of information and have less overhead than a scatter table, although the access time is of greater computational complexity.

Although the storage form has a tree structure internally, this is not externalized in the API, making the handling of the data transparent. They are called balanced because, each time they are modified, the branches are rebalanced in such a way that the height of the tree is as low as possible, thus shortening the average time of access to the data.