See Our team

Wondering how we keep quality?

Got unsolved questions?

Ask Questions

You are here:Open notes-->VTU-->Data-structure-with-C-10CS35-unit-8

**Data structure with C 10CS35 unit-8**

# UNIT - 8 EFFICIENT BINARY SEARCH TREES

**8.1 Optimal Binary Search Trees**

An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum. For the purpose of a better presentation of optimal binary search trees, we will consider ―extended binary search trees‖, which have the keys stored at their internal nodes. Suppose ―n‖ keys k1, k2, … , k n are stored at the internal nodes of a binary search tree. It is assumed that the keys are given in sorted order, so that k1< k2 < … < kn. An extended binary search tree is obtained from the binary search tree by adding successor nodes to each of its terminal nodes as indicated in the following figure by squares:

the extended tree: the squares represent terminal nodes. These terminal nodes represent unsuccessful searches of the tree for key values. The searches did not end successfully, that is, because they represent key values that are not actually stored in the tree; the round nodes represent internal nodes; these are the actual keys stored in the tree; assuming that the relative frequency with which each key value is accessed is known, weights can be assigned to each node of the extended tree (p1 … p6). They represent the relative frequencies of searches terminating at each node, that is, they mark the successful searches.If the user searches a particular key in the tree, 2 cases can occur:

1 – The key is found, so the corresponding weight ‗p‘ is incremented;

2 – The key is not found, so the corresponding ‗q‘ value is incremented.

GENERALIZATION: the terminal node in the extended tree that is the left successor of k1 can be interpreted as representing all key values that are not stored and are less than k1. Similarly, the terminal node in the extended tree that is the right successor of kn, represents all key values not stored in the tree that are greater than kn. The terminal node that is successed between ki and ki-1 in an inorder traversal represents all key values not stored that lie between ki and ki - 1.

An obvious way to find an optimal binary search tree is to generate each possible binary search tree for the keys, calculate the weighted path length, and keep that tree with the smallest weighted path length. This search through all possible solutions is not feasible, since the number of such trees grows exponentially with ―n‖. An alternative would be a recursive algorithm. Consider the characteristics of any optimal tree. Of course it has a root and two subtrees. Both subtrees must themselves be optimal binary search trees with respect to their keys and weights. First, any subtree of any binary search tree must be a binary search tree. Second, the subtrees must also be optimal. Since there are ―n‖ possible keys as candidates for the root of the optimal tree, the recursive solution must try them all. For each candidate key as root, all keys less than

**8.2 AVL Trees**

**8.3 Red-Black Trees**

Properties

A binary search tree in which The root is colored black All the paths from the root to the leaves agree on the number of black nodes No path from the root to a leaf may contain two consecutive nodes colored red Empty subtrees of a node are treated as subtrees with roots of black color. The relation n > 2h/2 - 1 implies the bound h < 2 log 2(n + 1). Insertions

Insert the new node the way it is done in binary search trees

Color the node red

If a discrepancy arises for the red-black tree, fix the tree according to the type of discrepancy.

A discrepancy can result from a parent and a child both having a red color. The type of discrepancy is determined by the location of the node with respect to its grand parent, and the color of the sibling of the parent. Discrepancies in which the sibling is red, are fixed by changes in color. Discrepancies in which the siblings are black, are fixed through AVL-like rotations. Changes in color may propagate the problem up toward the root. On the other hand, at most one rotation is sufficient for fixing a discrepancy.

**Deletions**

Delete a key, and a node, the way it is done in binary search trees.

A node to be deleted will have at most one child. If the deleted node is red, the tree is still a redblack

tree. If the deleted node has a red child, repaint the child to black.

If a discrepancy arises for the red-black tree, fix the tree according to the type of discrepancy.

A discrepancy can result only from a loss of a black node.

Let A denote the lowest node with unbalanced subtrees. The type of discrepancy is determined by the location of the deleted node (Right or Left), the color of the sibling (black or red), the number of red children in the case of the black siblings, and and the number of grand-children in the case of red siblings. In the case of discrepancies which result from the addition of nodes, the correction mechanism may propagate the color problem (i.e., parent and child painted red) up toward the root, and stopped on the way by a single rotation. Here, in the case of discrepancies which result from the deletion of nodes, the discrepancy of a missing black node may propagate toward the root, and stopped on the way by an application of an appropriate rotation.

**8.4 Splay Trees**

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of non-random operations, splay trees perform better thanother search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Dominic Sleator and Robert Endre Tarjan in 1985. All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase

**Splaying**

When a node x is accessed, a splay operation is performed on x to move it to the root. To perform a splay operation we carry out a sequence of splay steps, each of which moves x closer to the root. By performing a splay operation on the node of interest after every access, the recently-accessed nodes are kept near the root and the tree remains roughly balanced, so that we achieve the desired amortized time bounds.

Each particular step depends on three factors:

Whether x is the left or right child of its parent node, p,

whether p is the root or not, and if not

whether p is the left or right child of its parent, g (the grandparent of x).

It is important to remember to set gg (the great-grandparent of x) to now point to x after any splay operation. If gg is null, then x obviously is now the root and must be updated as such. There are three types of splay steps, each of which has a left- and right-handed case. For the sake of brevity, only one of these two is shown for each type. These three types are: Zig Step: This step is done when p is the root. The tree is rotated on the edge between x and p. Zig steps exist to deal with the parity issue and will be done only as the last step in a splay operation and only when x has odd depth at the beginning of the operation.

**Zig-zig Step: **This step is done when p is not the root and x and p are either both right children or are both left children. The picture below shows the case where x andp are both left children. The tree is rotated on the edge joining p with its parent g, then rotated on the edge joining x with p. Note that zig-zig steps are the only thing that differentiate splay trees from the rotate to root method introduced by Allen and Munro[3] prior to the introduction of splay trees.

**Zig-zag Step: **This step is done when p is not the root and x is a right child and p is a left child or vice versa. The tree is rotated on the edge between p and x, and then rotated on the resulting edge between x and g.

## Use Me ?