Please answer 3.3.16 please draw diagram in steps and circle final result. CHAPT
ID: 3881319 • Letter: P
Question
Please answer 3.3.16 please draw diagram in steps and circle final result.
CHAPTER3Searching EXERCISES (continued) 3.3.12 Draw the red-black BST that results after each transformation (color fli rotation) during the insertion of P for our standard indexing client. 3.3.13 True or false: If you insert keys in increasing order into a red-black BST, the tr height is monotonically increasing 3.3.14 Draw the red-black BST that results when you insert letters A through K in order into an initially empty tree, then describe what happens in general when trees are built by insertion of keys in ascending order (see also the figure in the text). 3.3.15 Answer the previous two questions for the case when the keys are inserted in descend ing order 3.3.16 Show the result of inserting n into the red-black BST drawn at right (only the search path is shown, and you need to include only these nodes in your answer). 3.3.17 Generate two random 16-node red- black BSTs. Draw them (either by hand or with a program). Compare them with the (unbalanced) BSTs built with the same keys. 3.3.18 Draw all the structurally different red-black BSTs with n keys, for n to 10 (see EXERCISE 3.3.5). from 2 up ys, 33.19 With I bit per node for color, we can represent 2-, 3-, and 4-nodes. Howee 3.3 .20 Compute the internal path length in a perfectly balanced BST of n no bits per node would we need to represent 5-, 6-,7-, and 8-nodes with a binary n is a power of 2 minus 1. 3.3.21 Create a test dient for RedB1ackBST, based on your solutio of n nodes, when 3.3.22 Find a sequence of keys to insert into a BST and into a re , based on your solution to EXERCISE the height of the BST is less than the height of the red-black BST, or p sequence is possible B-black BST such that or prove that no stExplanation / Answer
3.3.16:Name the node red(R) and black(B) on the basis of tree provided.
(B)j
(B)u
/
(R)t
/
(B)s
/
(R)r
/
(B)q
/
(R)p
/
(B)l
/
(R)k (B)o
/
(R)m
Inserting n
Find the all 12 steps to insert n.
Step 1
(B)j
(B)u
/
(R)t
/
(B)s
/
(R)r
/
(B)q
/
(R)p
/
(B)l
/
(R)k (B)o
/
(R)m
(R)n
Step 2
(B)j
(B)u
/
(R)t
/
(B)s
/
(R)r
/
(B)q
/
(R)p
/
(B)l
/
(R)k (B)o
/
(R)n
/
(R)m
Step 3
(B)j
(B)u
/
(R)t
/
(B)s
/
(R)r
/
(B)q
/
(R)p
/
(B)l
/
(R)k (B)n
/
(R)m (R)o
Step 4
(B)j
(B)u
/
(R)t
/
(B)s
/
(R)r
/
(B)q
/
(R)p
/
(B)l
/
(R)k (R)n
/
(B)m (B)o
Step 5
(B)j
(B)u
/
(R)t
/
(B)s
/
(R)r
/
(B)q
/
(R)p
/
(R)l
/
(B)k (B)n
/
(B)m (B)o
Step 6
(B)j
(B)u
/
(R)t
/
(B)s
/
(R)r
/
(B)p
/
(R)l (R)q (q's left child is now p's former right child)
/
(B)k (B)n
/
(B)m (B)o
Step 7
(B)j
(B)u
/
(R)t
/
(B)s
/
(R)r
/
(R)p
/
(B)l (B)q
/
(B)k (B)n
/
(B)m (B)o
Step 8
(B)j
(B)u
/
(R)t
/
(B)r
/
(R)p (R)s (s's left child is now r's former right child)
/
(B)l (B)q
/
(B)k (B)n
/
(B)m (B)o
Step 9
(B)j
(B)u
/
(R)t
/
(R)r
/
(B)p (B)s
/
(B)l (B)q
/
(B)k (B)n
/
(B)m (B)o
Step 10
(B)j
(B)t
/
(R)r (R)u (u's left child is now t's former right child)
/
(B)p (B)s
/
(B)l (B)q
/
(B)k (B)n
/
(B)m (B)o
Step 11
(B)j
(R)t
/
(B)r (B)u
/
(B)p (B)s
/
(B)l (B)q
/
(B)k (B)n
/
(B)m (B)o
Step 12
(B)t
/
(R)j (B)u
(B)r
/
(B)p (B)s
/
(B)l (B)q
/
(B)k (B)n
/
(B)m (B)o
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.