Did someone say ADTs? Here's another one!
Binary Search Trees are specialized types of Trees. Let's break up the name:
Binary- They can have a maximum of two children
Search - They have a special protocol when structuring elements. All elements which as lesser than the root are placed to once side of the root, and the greater values, to the other side. These are usually left and right, respectively. If you were to do an inorder traversal of a BST, you would get a list of values in ascending order.
Because of their strict form, binary search trees are useful for a number of applications. The most obvious being for conducting binary searches. Everytime a node is checked for a value, the remaining pool of values to check is more or less halved.
No comments:
Post a Comment