Question

Previous bonus - Next bonus
2-4 (“two-four”) trees are equivalent to these self-balancing binary search trees, which store one extra bit of data in each node. For 10 points each:
[10m] Name these trees that can flip that bit during an insertion or deletion to maintain their invariants.
ANSWER: red–black trees [reject “black–red trees”]
[10h] Robert Sedgewick claims that this implementation of red–black trees is simple to code since its condition on red edges reduces the number of cases to consider for insert and delete. However, this implementation’s detractors say that its asymmetry requires more cases to be considered and more rotations to be performed.
ANSWER: left-leaning red–black tree [or LLRB tree; reject “left” or “leaning”]
[10e] Balanced binary search trees guarantee this time complexity for search, insert, and delete. The average case of binary search has this time complexity because each step divides the search space in half.
ANSWER: big O of log n [or log time or logarithmic time; or big O of log base-2 n; or big O of the base-2 logarithm of n; or big O of log 2 of n; accept answers that use a different base in place of 2]
<Other Science>

Back to bonuses

Summary

2024 ACF Nationals2024-04-21Y2114.2981%62%0%

Data

WaterlooChicago D1001020
Chicago CClaremont Colleges001010
McGillColumbia A001010
Columbia BNorth Carolina B1001020
MichiganCornell A0000
DukeChicago B0000
Georgia TechArizona State1001020
HarvardNYU0000
IndianaToronto A1001020
Iowa StateFlorida1001020
BrownMinnesota A1001020
Berkeley BNorth Carolina A1001020
NorthwesternTruman State1001020
MarylandPurdue1001020
TexasSouth Carolina001010
Berkeley AToronto B1001020
KentuckyVirginia001010
Johns HopkinsWUSTL A1001020
Chicago AWUSTL B1001020
Yale ACornell B0000
StanfordYale B1001020