Binary Sorted Trees

A linked list,stack or a queue work fine for a small number of items, but when it comes to search for an item all the three data structures require a lot of time. Searching for an item's position requires comparing the value to be searched with each item in the list. Suppose there are 100 values in a linked list and the value that we want to find is stored in the last node, then it will take 100 comparisons to find the desired value.

Binary Sorted Tree

A binary sorted tree is a type of binary tree in which values are stored in respect to the root node. All the nodes having data less than the root's data are stored to the left of the root, while the nodes having a value more than the root's value are stored to the right of root. A binary tree can be used to store an ordered list of strings, or other items, in a way that makes both searching and insertion efficient. A binary tree used in this way is called a binary sort tree.

A binary sort tree has the following properties

For every node in the tree, the item in that node is greater than every item in the left subtree of that node, and it is less than or equal to all the items in the right subtree of that node. Take a look at the picture, you will see that all the nodes to the left of the root have smaller data while the right ones have larger data in comparison to the root.

The Advantage

Binary sorted trees offer a very useful advantage - When we traverse a binary sorted tree using the inorder method, all the values of the tree are accessed in ascending order. An inorder traversal of the tree will process the items in increasing order. For example, if an inorder traversal is used to print the items in the tree shown above, then the items will be in increasing order of their numerical value. The inorder traversal ensures that 1 will be printed before 2 and 2 will be printed before 3.Suppose that we want to search for a given item in a binary search tree. The item will be first compared with the root item of the tree. If they are equal,the search operation stops there. If the item we are searching for is less than the root item, then the value will be searched in the left subtree of the root ,the right subtree can be eliminated because it only contains items that are greater than or equal to the root. Similarly, if the item we are looking for is greater than the item in the root, then we only need to look in the right subtree. In either case, the same procedure can then be applied to search the subtree. Inserting a new item is similar: Start by searching the free for the position where the new item belongs. When that position is found, create a new node and attach it to the tree at that position.

Searching and inserting are efficient operations on a binary search tree, provided that the tree is close to being balanced.

A binary tree is balanced if for each node, the left subtree of that node contains approximately the same number of nodes as the right subtree. In a perfectly balanced tree, the two numbers differ by at most one. Not all binary trees are balanced, but if the tree is created randomly, there is a high probability that the tree is approximately balanced. During a search of any binary sort tree, every comparison eliminates one of two subtrees from further consideration. If the tree is balanced, that means cutting the number of items still under consideration in half.