Question

(20 Points) Insert the keys: 4,8,10,12,13,11,9,6,7,5,2,3,1 (in order) into an initially empty Binary Search Tree T. (Note: use the Binary Search Tree Insert algorithm to do this.) a. ( 5 Points) Give the keys of T in the order printed by a pre-order tree walk. b. ( 5 Points) Give the keys of T in the order printed by a post-order tree walk. c. (5 Points) Determine an assignment of colors { Red, Black } to the vertices of the BST you found above, such that the Red-Black Tree properties are satisfied, bh(T)=3, and bh(12)=1. Specify your coloring by stating the set of keys belonging to Red nodes. Be sure to count nil children when computing the black-height of T. (Note: just assign colors, do not run any RBT algorithm.) d. (5 Points) Determine an assignment of colors { Red, Black } to the vertices of the BST you found above, such that the Red-Black Tree properties are satisfied, bh (T)=3, and bh(8)=3. Specify your coloring by stating the set of keys belonging to Red nodes. Be sure to count nil children when computing the black-height of T. (Note: just assign colors, do not run any RBT algorithm.) Some BST Algorithms:

Answer 1

a. Pre-order tree walk: 4, 2, 1, 3, 8, 6, 5, 7, 10, 9, 12, 11, 13

b. Post-order tree walk: 1, 3, 2, 5, 7, 6, 9, 11, 13, 12, 10, 8, 4

c. One possible assignment of colors to satisfy the Red-Black Tree properties and the given black-heights is:

Red nodes: {6, 2, 1}

Black nodes: {4, 3, 5, 7, 10, 8, 9, 12, 11, 13}

This coloring ensures that the Red-Black Tree properties are satisfied, bh(T) = 3, and bh(12) = 1.

d. One possible assignment of colors to satisfy the Red-Black Tree properties and the given black-heights is:

Red nodes: {8, 5, 2}

Black nodes: {4, 3, 1, 6, 7, 10, 9, 12, 11, 13}

This coloring ensures that the Red-Black Tree properties are satisfied, bh(T) = 3, and bh(8) = 3.