Trees:Binary Search Trees

By -

Binary Search Trees

Definition

A binary search tree (BST) is a binary tree that has a key associated with each of its nodes. The keys in the left subtree of a node are smaller than or equal to the key in the node and the keys in the right subtree of a node are greater than or equal to the key in the node. To simplify the discussion, we will assume that the keys in the binary search tree are distinct. Figure 3.9 shows some binary trees to illustrate the definition.

image

Search

We describe a recursive algorithm to search for a key k in a tree T : first, if T is empty, the search fails. Second, if k is equal to the key in T ’s root, the search is successful. Otherwise,

Trees 3-11

we search T ’s left or right subtree recursively for k depending on whether it is less or greater than the key in the root.

image

Insert

To insert a key k, we first carry out a search for k. If the search fails, we insert a new node with k at the null branch where the search terminated. Thus, inserting the key 17 into the binary search tree in Figure 3.9(b) creates a new node which is the left child of 18. The resulting tree is shown in Figure 3.10(a).

image

Delete

The procedure for deleting a node x from a binary search tree depends on its degree. If x is a leaf, we simply set the appropriate child pointer of x’s parent to 0 and delete x. If x has one child, we set the appropriate pointer of x’s parent to point directly to x’s child and then delete x.

In Figure 3.9(c), node 20 is deleted by setting the right child of 15 to 25.

If x has two children, we replace its key with the key in its inorder successor y and then delete node y. The inorder successor contains the smallest key greater than x’s key. This key is chosen because it can be placed in node x without violating the binary search tree property. Since y is obtained by first following a RightChild pointer and then following LeftChild pointers until a node with a null LeftChild pointer is encountered, it follows that y has degree 0 or 1. Thus, it is easy to delete y using the procedure described above.

Consider the deletion of 12 from Figure 3.9(b). This is achieved by replacing 12 with 14 in the root and then deleting the leaf node containing 14. The resulting tree is shown in Figure 3.10(b).

Miscellaneous

Although Search, Insert, and Delete are the three main operations on a binary search tree, there are others that can be defined which we briefly describe below.

• Minimum and Maximum that respectively find the minimum and maximum elements in the binary search tree. The minimum element is found by starting at the root and following Left Child pointers until a node with a 0 Left Child pointer is encountered. That node contains the minimum element in the tree.

• Another operation is to find the kth smallest element in the binary search tree. For this, each node must contain a field with the number of nodes in its left subtree. Suppose that the root has m nodes in its left subtree. If k ≤ m, we recursively search for the kth smallest element in the left subtree. If k = m + 1, then the root contains the kth smallest element. If k > m+ 1, then we recursively search the right subtree for the k − m − 1st smallest element.

• The Join operation takes two binary search trees A and B as input such that all the elements in A are smaller than all the elements of B. The objective is to obtain a binary search tree C which contains all the elements originally in A and

B. This is accomplished by deleting the node with the largest key in A. This node becomes the root of the new tree C. Its Left Child pointer is set to A and its Right Child pointer is set to B.

• The Split operation takes a binary search tree C and a key value k as input. The binary search tree is to be split into two binary search trees A and B such that all keys in A are less than or equal to k and all keys in B are greater than k. This is achieved by searching for k in the binary search tree. The trees A and B are created as the search proceeds down the tree as shown in Figure 3.11.

• An inorder traversal of a binary search tree produces the elements of the binary search tree in sorted order. Similarly, the inorder successor of a node with key k in the binary search tree yields the smallest key larger than k in the tree. (Note that we used this property in the Delete operation described in the previous section.)

All of the operations described above take O(h) time, where h is the height of the binary search tree. The bounds on the height of a binary tree are derived in Lemma 3.7. It has been shown that when insertions and deletions are made at random, the height of the binary search tree is O(log n) on the average.

image

Comments

Post a Comment

Popular posts from this blog

0/1 Knapsack Problem Memory function.

By -
Image
0 / 1 Knapsack Problem Memory function Definition: Given a set of n items of known weights w1,…,wn and values v1,…,vn and a knapsack of capacity W, the problem is to find the most valuable subset of the items that fit into the knapsack. Knapsack problem is an OPTIMIZATION PROBLEM Dynamic programming approach to solve knapsack problem Step 1: Identify the smaller sub-problems. If items are labeled 1..n, then a sub-problem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k } Step 2: Recursively define the value of an optimal solution in terms of solutions to smaller problems. Initial conditions: S te p 3: Bottom up computation using iteration Question: Apply bottom-up dynamic programming algorithm to the following instance of the knapsack problem Capacity W= 5 Solution: Using dynamic programming approach, we have: What is the composition of the optimal subset? The composition of the optimal subset if found by tracing back the computations for the...
Read more

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

By -
Image
BSP Tree as a Hierarchy of Regions Another way to look at BSP Trees is to focus on the hierarchy of regions created by the recursive partitioning, instead of focusing on the hyperplanes themselves. This view helps us to see more easily how intersections are efficiently computed. The key idea is to think of a BSP Tree region as serving as a bounding volume: each node v corresponds to a convex volume that completely contains all the geometry represented by the sub tree rooted at v . Therefore, if some other geometric entity, such as a point, ray, object, etc., is found to not intersect the bounding volume, then no intersection computations need be performed with any geometry within that volume. Consider as an example a situation in which we are given some test point and we want to find which object if any this point lies in. Initially, we know only that the point lies somewhere space ( Figure 20.12). By comparing the location of the point with respect to the first partitioning hyper pl...
Read more

Drawing Trees:HV-Layout

By -
Image
HV-Layout An hv -layout of a binary tree is an upward (but not strictly upward) straight line orthogonal drawing with edges drawn as rightward horizontal or downward vertical segments. The ”hv” stands for horizontal-vertical. For any vertex v in a binary tree T we either have: 1. A child of v is either • aligned horizontally with v and to the right of v or • vertically aligned below v . 2. The smallest rectangles that cover the area of the subtrees of the children of v in the layout do not intersect. Figure 45.12 shows an example of a hv -layout A hv -layout is generated by applying a dived and conquer approach. The divide step constructs the hv -layout of the left and the right subtrees, while the conquer step either performs a ho rizontal or a ver t i c a l combination . Figure 45.13 shows the two types of com- bination. If the left subtree a node v is placed to the left in a horizontal combination and below in a vertical combination, the layout preserves ...
Read more