14 - Red-Black Trees

Which of the following IS NOT a property of red-black trees?

• every sentinel/leaf node has the same number of red ancestors
• every sentinel/leaf node has the same number of black ancestors
• the root of the tree must be black
• every red node must have black children
• every sentinel/leaf node is black

Red-black trees use color to ensure…

• O(h) recolorings and O(1) restructurings
• O(1) recolorings and O(h) restructurings
• O(log n) restructurings for each insert
• O(log n) restructurings for each delete

When inserting a new entry into a red-black tree, the newly created node will be…

• red, if the new node is not the root node
• red, if the new node is the root node
• black, if the new node is not the root node
• the same color as its sibling

When inserting into a red-black tree, what condition might happen?

• double-red
• double-black
• triple-red
• triple-black

What (2,4) tree scenario is represented by the following red-black subtree?

• overflow

• underflow

• splay

• transfer

• fusion

When deleting a node from a red-black tree, what condition might happen?

• double-black
• double-red
• triple-red
• triple-black
• too much!

What corresponding (2,4) tree operation should be performed to resolve the double-black?

• transfer

• fusion

• split

• splay

• merge

What corresponding (2,4) tree operation should be performed to resolve the double-black?

• fusion

• transfer

• split

• splay

• merge

Which of the following data structures has worst-case O(log n) runtime for map behaviors (put, get, remove)?

• red-black trees

• AVL trees

• skip lists

• splay trees

• (2,4) trees