Question

Question 46

2 pts

Which of the following is incorrect about a red-black tree?

Group of answer choices

a. The leaves are always red

b. A red-black tree is equivalent to a 2-4 tree

c. A red node must have a black parent

d. Every path from the root to the leaves must have the same number of red nodes

e. a and d

Flag this Question

Question 47

2 pts

Given the following maxheap, assuming heap entries start at index 1, show the heap after adding the entry 87 using the array representation.

index	0	1	2	3	4	5	6
value		45	12	40	8	7	24

Group of answer choices

a.

index	0	1	2	3	4	5	6	7
value		45	12	40	8	7	24	87

b.

index	0	1	2	3	4	5	6	7
value		45	12	87	8	7	24	40

c.

index	0	1	2	3	4	5	6	7
value		87	45	12	24	40	8	7

d.

index	0	1	2	3	4	5	6	7
value		87	45	12	40	24	8	7

e.

index	0	1	2	3	4	5	6	7
value		87	12	45	8	7	24	40

Answer 1

1

a) Leaves are alway red. This statement as false. Only condition of R-B tree is root is always black. suppose there are 3 levels, then leaf will be black, as no two levels can have same color

b) 2-4 trees and red black trees are equivalent. This statement is correct.

c) A red node must have black parent. Since no adjacent level nodes can have same color and root is always black, this statement is also true.

d) Every path from the root to the leaves must have the same number of red nodes. This statement is false. The correct answer would be black nodes instead of red in above statement as per definition of red black tree.

So correct answer for question 1 would option e) which states option b) and d) are false.

2. In a max heap, root element will be always 1. Left child of node is available at index 2i and right child at index 2i + 1, parent will have index i/2, if heap is implemented as an array.

Initial heap: [45, 12, 40, 87, 24]

add 87

array [45, 12, 40, 87, 24, 87]

heapify [87, 12, 45, 87, 24, 40]

Operations in heapify.

87 added at index 6 is compared with parent at index floor(6/2) = 3. ie. 40. Since 87 is larger than 40(max heap), we will swap them. New array after swap is

[45, 12, 87, 87, 24, 40]

We will be checking 87 at index 3 with it's parent at index floor(3/2) = 1 i.e. 45. Since 87 is larger than 45, swap them to get the heap.

[87, 12, 45, 87, 24, 40] corresponds to option (e)

KINDLY REVIEW.