Applications of Trees

Binary Search Trees: Searching for items in a list is one of the most important tasks that arises in computer science. Our primary goal is to implement a searching algorithm that finds items efficiently when the items are totally ordered. This can be accomplished through the use of a binary search tree, which is a binary tree in which each child of a vertex is designated as a right or left child, no vertex has more than one right child or left child, and each vertex is labeled with a key, which is one of the items. Furthermore, vertices are assigned keys so that the key of a vertex is both larger than the keys of all vertices in its left subtree and smaller than the keys of all vertices in its right subtree.

This recursive procedure is used to form the binary search tree for a list of items. Start with a tree containing just one vertex, namely, the root. The first item in the list is assigned as the key of the root. To add a new item, first compare it with the keys of vertices already in the tree, starting at the root and moving to the left if the item is less than the key of the respective vertex if this vertex has a left child, or moving to the right if the item is greater than the key of the

ALGORITHM 1:  Locating an Item in or Adding an Item to a Binary Search Tree.

• procedure insertion(T : binary search tree, x: item)
• v := root of T
• {a vertex not present in T has the value null }
• while v = null and label(v) = x
• if x < label(v) then
• if left child of v = null then v := left child of v
• else add new vertex as a left child of v and set v := null
• else
• if right child of v = null then v := right child of v
• else add new vertex as a right child of v and set v := null
• if root of T = null then add a vertex v to the tree and label it with x
• else if v is null or label(v) = x then label new vertex with x and let v be this new vertex
• return v {v = location of x}