Download to read offline
More Related Content
gayathri23.pptx
- 1. NADAR SARASWATHI COLLEGEOF ARTS AND SCIENCE Name : P. Gayathri Class : I M.Sc (CS) Topic : Optimal binary search trees
- 2. Optimal binary searchtree an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree , is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static dynamic.
- 3. In thestatic optimality problem, the tree cannot be modified after it has been constructed. In this case, there exists some particular layout of the nodes of the tree which provides the smallest expected search time for the given access probabilities. Various algorithms exist to construct or approximate the statically optimal tree given the information on the access probabilities of the elements. In the dynamic optimality problem, the tree can be modified at any time, typically by permitting tree rotations. The tree is considered to have a cursor starting at the root which it can move or use to perform modifications. In this case, there exists some minimal-cost sequence of these operations which causes the cursor to visit every node in the target access sequence in order. The splay tree is conjectured to have a constant competitive ratio compared to the dynamically optimal tree in all cases, though this has not yet been proven.
- 4. If the keysare 10, 20, 30, 40, 50, 60, 70 Example:
- 5. For example: 10,20, 30 are the keys, and the following are the binary search trees that can be made out from these keys. The Formula for calculating the number of trees: When we use the above formula, then it is found that total 5 number of trees can be created.
- 6. The cost requiredfor searching an element depends on the comparisons to be made to search an element. Now, we will calculate the average cost of time of the above binary search trees. In the above tree, total number of 3 comparisons can be made. The average number of comparisons can be made as:
- 7. In the abovetree, the average number of comparisons that can be made as:
- 8. In the abovetree, the total number of comparisons can be made as 3. Therefore, the average number of comparisons that can be made as:
- 9. In the abovetree, the total number of comparisons can be made as 3. Therefore, the average number of comparisons that can be made as:
- 10. In thethird case, the number of comparisons is less because the height of the tree is less, so it's a balanced binary search tree. Till now, we read about the height-balanced binary search tree. To find the optimal binary search tree, we will determine the frequency of searching a key. Let's assume that frequencies associated with the keys 10, 20, 30 are 3, 2, 5. The above trees have different frequencies. The tree with the lowest frequency would be considered the optimal binary search tree. The tree with the frequency 17 is the lowest, so it would be considered as the optimal binary search tree.
- 11.