(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.
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.
Define right-leaning red-black BSTs as BSTs having red and black edges satisfying the following three restrictions:
Red links lean right only.
No node has two red links connected to it.
Every path from the root to a leaf has the same black depth.
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.
Using a construction proof, show that for every right-leaning red-black tree there is a corresponding left-leaning red-black tree.
Let= ( , ), where = { , , , , , , , ℎ} and =
{{ , }, { , }, { , },{ , }, { , }, { , }, { , }, { , }, { , }, { , ℎ}, { , ℎ} }.
Draw the corresponding graph with no edges crossing.
How many paths are there in from to ℎ?
How many of these paths have length less than 5? List them.
Let = ( , ) be an undirected graph, with no parallel edges or self-loops. Let | | = and | | = . Prove by induction that 2 ≤ 2 − for all ≥ 1.
Consider the graph G shown below:
How many spanning subgraphs are there?
How many connected spanning subgraphs are there?
How many of the spanning subgraphs have vertex 0 as an isolated vertex?
