Font size
S
M
L
XL
WorksheetsRed Black Trees
Total questions: 10
Worksheet time: 5mins
Name
Class
Date
1.
Which of the following IS NOT a property of red-black trees?
a)
every sentinel/leaf node has the same number of red ancestors
b)
every sentinel/leaf node has the same number of black ancestors
c)
the root of the tree must be black
d)
every red node must have black children
e)
every sentinel/leaf node is black
2.
Red-black trees use color to ensure…
a)
O(h) recolorings and O(1) restructurings
b)
O(1) recolorings and O(h) restructurings
c)
O(log n) restructurings for each insert
d)
O(log n) restructurings for each delete
3.
When inserting a new entry into a red-black tree, the newly created node will be…
a)
red, if the new node is not the root node
b)
red, if the new node is the root node
c)
black, if the new node is not the root node
d)
the same color as its sibling
4.
When inserting into a red-black tree, what condition might happen?
a)
double-red
b)
double-black
c)
triple-red
d)
triple-black
5.
What (2,4) tree scenario is represented by the following red-black subtree?
a)
overflow
b)
underflow
c)
splay
d)
transfer
e)
fusion
6.
When deleting a node from a red-black tree, what condition might happen?
a)
double-black
b)
double-red
c)
triple-red
d)
triple-black
e)
too much!
7.
What corresponding (2,4) tree operation should be performed to resolve the double-black?
a)
transfer
b)
fusion
c)
split
d)
splay
e)
merge
8.
What corresponding (2,4) tree operation should be performed to resolve the double-black?
a)
fusion
b)
transfer
c)
split
d)
splay
e)
merge
9.
Which of the following data structures has worst-case O(log n) runtime for map behaviors (put, get, remove)?
a)
red-black trees
b)
AVL trees
c)
skip lists
d)
splay trees
e)
(2,4) trees
10.
What is the time complexity of level order traversal?
a)
O(1)
b)
O(n)
c)
O(logn)
d)
O(nlogn)
Reset
