06-27-2012, 06:25 PM
Suppose you are given a task to develop an electronic phone book in which you have to store names and phone numbers of employees of a company. The data structures available to you are linked list and Binary Search Tree (BST) and you have to choose only one data structure. Moreover, while selecting any data structure, you also have to keep in consideration insertion, deletion and search operations, because, the company can hire some new employees, search for an employee’s phone number and some old employees can also leave this company. Discuss which data structure do you think would be more suitable for the above discussed scenario. Also discuss the reason why would you prefer this data structure over the other?
Solution:
A binary search tree will provide logarithmic searching which is pretty good. Insertions or deletions will be more costly because they may require some tree rebalancing.
For your linked list, are you still going to keep the data in order or just stuff the nodes one after another? If you are putting them in no order, retrieval will be slow (linear) and insertions and deletions still won’t be that fast. The problem with a linked list, if I remember correctly, is that you can’t jump in the middle of a linked list. You start at the root and go to the next node then the next, etc. So you really can’t perform a binary search or any kind of hashing on the data.
The most popular variation of the Binary Tree is the Binary Search Tree (BST). BSTs are used to quickly and efficiently search for an item in a collection. Say, for example, that you had a linked list of 1000 items, and you wanted to find if a single item exists within the list. You would be required to linearly look at every node starting from the beginning until you found it. If you’re lucky, you might find it at the beginning of the list. However, it might also be at the end of the list, which means that you must search every item before it. This might not seem like such a big problem, especially nowadays with our super fast computers, but imagine if the list was much larger, and the search was repeated many times. Such searches frequently happen on web servers and huge databases, which makes the need for a much faster searching technique much more apparent. Binary Search Trees aim to Divide and Conquer the data, reducing the search time of the collection and making it several times faster than any linear sequential search.
not sure there are necessarily hard and fast rules for this, so this is more than opinion (to a large extent). Consider this hypothetical program. Suppose you have an address book and want to store People objects somehow so that you can retrieve information about the person (name, age, address, etc) Suppose the key is the person’s name. (snowz) Now, as you might imagine, people are going to want to get Sue Johnson, Albert Zudo, Michael Allan, etc. in any order. So, from the perspective of a program, the order you will be retrieving data will be random. IMO, a tree structure would be better here than a linked list. For a linked list to get to Albert Zudo you are going to have to retrieve the data by going through every entry before Albert Zudo (all A’s, B’s, etc) For a tree structure you can use a binary search (Binary search algorithm - Wikipedia, the free encyclopedia). A binary search essentially lets you eliminate half of the possible choices on each comparison. A linked list only lets you eliminate one.
Similarly with insertions, to add someone to the address book you can simply do a binary search to find the insertion point for a tree. For a linked list you have to go through each item to find it’s insertion points.
Solution:
A binary search tree will provide logarithmic searching which is pretty good. Insertions or deletions will be more costly because they may require some tree rebalancing.
For your linked list, are you still going to keep the data in order or just stuff the nodes one after another? If you are putting them in no order, retrieval will be slow (linear) and insertions and deletions still won’t be that fast. The problem with a linked list, if I remember correctly, is that you can’t jump in the middle of a linked list. You start at the root and go to the next node then the next, etc. So you really can’t perform a binary search or any kind of hashing on the data.
The most popular variation of the Binary Tree is the Binary Search Tree (BST). BSTs are used to quickly and efficiently search for an item in a collection. Say, for example, that you had a linked list of 1000 items, and you wanted to find if a single item exists within the list. You would be required to linearly look at every node starting from the beginning until you found it. If you’re lucky, you might find it at the beginning of the list. However, it might also be at the end of the list, which means that you must search every item before it. This might not seem like such a big problem, especially nowadays with our super fast computers, but imagine if the list was much larger, and the search was repeated many times. Such searches frequently happen on web servers and huge databases, which makes the need for a much faster searching technique much more apparent. Binary Search Trees aim to Divide and Conquer the data, reducing the search time of the collection and making it several times faster than any linear sequential search.
not sure there are necessarily hard and fast rules for this, so this is more than opinion (to a large extent). Consider this hypothetical program. Suppose you have an address book and want to store People objects somehow so that you can retrieve information about the person (name, age, address, etc) Suppose the key is the person’s name. (snowz) Now, as you might imagine, people are going to want to get Sue Johnson, Albert Zudo, Michael Allan, etc. in any order. So, from the perspective of a program, the order you will be retrieving data will be random. IMO, a tree structure would be better here than a linked list. For a linked list to get to Albert Zudo you are going to have to retrieve the data by going through every entry before Albert Zudo (all A’s, B’s, etc) For a tree structure you can use a binary search (Binary search algorithm - Wikipedia, the free encyclopedia). A binary search essentially lets you eliminate half of the possible choices on each comparison. A linked list only lets you eliminate one.
Similarly with insertions, to add someone to the address book you can simply do a binary search to find the insertion point for a tree. For a linked list you have to go through each item to find it’s insertion points.
0300-9520262
Get solution in 24 hour |cpmputer & internet
mileys81:[SIZE="4"][SIZE="3"]....[/SIZE][/SIZE]