[ Data Structures with Java ] Section 18.1 : Binary Search Trees

Preface :
A binary search tree is a binary tree in which each element resides on a unique path from the root. The tree can store objects that have a natural order. This means that two object satisfy a comparison relation < (less than), == (equal to), or > (greater than). The ordering of objects creates an ordering among nodes in the tree.
Search Tree Ordering :
For each node in the tree, the values in its left subtree are less than the value of the node and the values in its right subtree are greater than the value of the node. Below figure illustrates binary search tree. Note that the order relation on the subtrees dictates that a binary search tree cannot have duplicate values :

A binary search tree has algorithms that maintain the ordering when inserting or deleting an element. Assuming the tree already exists, the insert algorithm becomes the basic for locating an element. Let us explore algorithms using a set of examples.

Building a Binary Search Tree :
Elements are inserted into a binary search tree using a strategy that maintains the ordering among the subtrees. The first element becomes the root node. All subsequent elements are added as leaf nodes at the end of a unique path. Identifying the path is an iterative process that begins at the root. Each step involves comparing the value of the new element, called item, with the value in the current node on the path. The following is the insertion strategy :

If the value of the new element is equal to the value of the current node perform no action. Because the insertion strategy doesn't allow duplicate values.

If the value of the new element is less than the value of the current node. Proceed to the left subtree (left child) of the node. If the left subtree is not empty, repeat the insertion strategy by comparing item with the root of the subtree. Otherwise, the left subtree is empty (left child==null), and we have reached the location for the new element at the end of the "insertion" path. Allocate a new node with item as its value, and attach the node to the tree as the left child. This extends the path to the new element.

If the value of the new element is greater than the value of the current node. Proceed to the right subtree (right child) of the node. If the right subtree is not empty, repeat the insertion strategy by comparing item with the root of the subtree. Otherwise, the right subtree is empty (right child == null). Allocate a new node with item as is value and attach the node to the tree as the right child.

The figure below builds a binary search tree by adding integer values from the sequence {35, 18, 25, 48, 25, 20} :


Locating an Object in a Binary Search Tree :
Each node enters the tree along a specific path. A search for an object uses an iterative process that scans the same path. Compare the value of the root node with the item. If a match occurs, we identify the location of the object in the tree. If the object is less than the node value, the search continues with the left child; otherwise, the search continues with the right child. If the search ends at any empty tree, the object is not in the tree. Let us search for the element 32, 60 and 12 in the below binary search tree :

- Find 32 :

Compare 32 with the root value 50. Because 32 < 50, go left to nodes 30. Compare 32 and 30. Because 30 < 32, go right to nodes 35. Compare 32and 35. Because 32 < 35, go left to node 32. A final comparison 32==32 identifies a match

- Find 60 :

Search down the path 50, 55, and 60. After three comparisons, a match is found.

- Find 12 :

Search down the path 50, 30, 25, 10 and 15. Compare 12 and 15 and go left to an empty subtree. The search ends at an empty tree and no match occurs. The search requires six comparisons, including the last one that identifies that the left subtree of 15 is empty.

Because a search tree is a binary tree, we can apply any of the different scan algorithms to visit the nodes. The inorder scan is particular significant. The order of the visit to a node and its children is LNR, where the values are ordered left child < node < right childe. So the scan visits the elements in ascending order.
With a RNL (inorder_right) scan, the first node visited is along the path of right children and has the maximum value. The scan visits the nodes in descending order.

Removing a Binary Search Tree Node :
In a linked list, removing an element involves unlinking the node and connecting its predecessor to the next node. The process is a little different with a binary search tree. Without detailing the algorithm, let us look at an example that illustrate some of the issues that will concern us as we develop binary search tree as storage collections. In the following search tree, we delete the element 25 in the root node. Note immediately that the root node cannot be removed from the tree because we would be left with two orphaned subtrees.


We need to find a replacement value for 25. At first glance, we might want to use a child of the node, 10 or 37, as the replacement value. Unfortunately either choice destroys the search ordering of the tree because a subtree would be on the wrong side of the root. (Below figure (a) & (b)) We need a strategy that locates a replacement value that is "nearest to 25". Because the example is relatively small, we can identify that 15 in the left subtree of 30 in the right subtree would be a good choice. Let us look at 30 in the right subtree. We locate 30 by moving to the right child of 25 namely 37, and then scanning down the path of left children. Assign 30 as the new root value and splice out (delete) node 30 from the tree by connecting its right subtree (33) as the left child of the parent 37 (below figure (c)). As the example indicates, developing a general algorithm to delete a node in a search tree is challenging since it must maintain the ordering of the tree.

This message was edited 10 times. Last update was at 21/10/2010 14:26:55