Solved-ASSIGNMENT 2- WRITTEN -Solution

Description

1. (a) Draw the 2-3 tree that results when you insert the keys S E A R C H X M P L Y in that order into an initially empty tree. Construct the corresponding red-black tree.

1. 2. Find a sequence of keys to insert into a BST and a red-back BST such that the height of the BST is less than the height of the red-black BST, or prove that no such sequence is possible.

2. Define right-leaning red-black BSTs as BSTs having red and black edges satisfying the following three restrictions:

1. 2. 1. Red links lean right only.

1. 2. 2. No node has two red links connected to it.

      3. Every path from the root to a leaf has the same black depth.

1. 1. Rewrite the put() method, on page 439 of the Sedgewick book, so that it works for right-leaning red-black trees instead of left-leaning red-black trees.

1. 2. Using a construction proof, show that for every right-leaning red-black tree there is a corresponding left-leaning red-black tree.

3. Let= ( , ), where = { , , , , , , , ℎ} and =

{{ , }, { , }, { , },{ , }, { , }, { , }, { , }, { , }, { , }, { , ℎ}, { , ℎ} }.

1. 1. Draw the corresponding graph with no edges crossing.

   2. How many paths are there in from to ℎ?

1. 3. How many of these paths have length less than 5? List them.

4. Let = ( , ) be an undirected graph, with no parallel edges or self-loops. Let | | = and | | = . Prove by induction that 2 ≤ ² − for all ≥ 1.

4. Consider the graph G shown below:

1. How many spanning subgraphs are there?

2. How many connected spanning subgraphs are there?

3. How many of the spanning subgraphs have vertex 0 as an isolated vertex?