Optimal Binary Tree

Can someone explain me the Optimal Binary Tree algorithm or can someone give me the code for an optimal binary Tree.

Comments

  • : Can someone explain me the Optimal Binary Tree algorithm or can someone give me the code for an optimal binary Tree.
    :

    The binary tree is used to search a sorted list for an item.
    The list must already be sorted, for it to work.

    [b]I'll explain what basically happens:[/b]
    You start with a sorted list and a value that you want to find in that list.

    There are variables to store the upper and lower boundaries of the search.

    Initially the boundries start at the first index and end at the last index of the list.

    Each pass of a loop, the boudries become half of their previous difference.

    The average of the upper and lower boundary is averaged to get an item to compare with the search value.

    If the search value is equal to the item, the search is complete becuase you've found what you were looking for.

    If the search value is greater, the item must be above this item so lowerbound is set to the average, upperbound remains the same.

    If the search value is less than the item, upperbound is set to the average, lower bound stays the same.

    if upperbound = lowerbound, the loop is to exit because the item can't be found in the list.


    After these conditions are complete is the end of the loop.


    Here is a site with some code for you:
    http://www.csm.astate.edu/~rossa/datastruc/optimal.html
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion