|
Gaurav Keerthi
CS377C
1 May 2001
Name
Binary Trees **
Picture
|
Context
Binary Trees are data structures in which each parent node has two child subtrees, a left subtree and a right subtree, which in return also have their own 2 subtrees until the list is expired of all data. It is commonly used in applications where a list (that is of manageable size) of some data type is required to be sorted and then searched speedily. The algorithm used is simple and commonplace in all programming languages.
* * *
Problem Statement
Sorting and searching a list of values in the most efficient manner has always been an algorithmic challenge for computer scientists. This is further compounded by the need for a dynamically updateable list of values, such that users can add, delete, and insert any key value, and have the data structure easily update itself. Searching the structure for a particular value should be speedy and efficient (where efficiency is determined by the number of operations required before the item is found in a list of size N).
Description
The Binary Tree is created from a list of values, preferably pre-sorted in some manner (but this is not required for it to work, it just balances the tree and speeds up later searching). The first value taken from the list is made the root of the tree. The next value taken, if it is less than the root, is added to the left of the root as a left leaf, but if this second value is greater than the root, it is added to the right leaf. The next value is taken from the list, and in a similar manner, if the key value of this item is less than the root, it moves to the left, if not it moves to the right. If there is another leaf already present to the left or right, then compare the value of this new item with the current leaf, and if it is less, move to the left, if not, move to the right subtree. Continue doing this until you reach the last leaf and can add this new item to the left or right of the leaf. Once all the items in the original list have been added to the tree in this manner, you have created a complete Binary Tree. Hence, intuitively, the smallest value in the entire list should be the left-most leaf, while the greatest value in the list should be the right-most leaf.
Solution
Hence, for an efficient and speedy solution to the problem of sorting, searching, appending, and deleting from a list of values, create a Binary Tree that has recursively each node in the left subtree having lower key values, and each node in the right subtree having higher key values.
Diagram
* * *
References
Other related implementations include the
AVL tree, splay tree, threaded tree, relaxed balance, randomised binary search tree, ternary search tree. Also see algorithms and pseudo code for the insert, search, delete, and various traversal functions.