Explain Comparison Trees...

The comparison trees also called decision tree or search tree of an algorithm, is obtained by tracing through the actions of the algorithm, representing each comparison of keys by a vertex of the tree (which we draw as a circle). Inside the circle we put the index of the key against which we are comparing the target key. Branches (lines) drawn down from the circle represent the possible outcomes of the comparison and are labeled accordingly. When the algorithm terminates, we put either F (for failure) or the location where the target is found at the end of the appropriate branch, which we call a leaf, and draw as a square. Leaves are also sometimes called end vertices or external vertices of the tree. The remaining vertices are called the internal vertices of the tree. The comparison tree for sequential search is especially simple.