4 / 8 Treaps, Splay & The Balanced BST Zoo

Four Kinds Of Log

Four balanced BSTs, four different promises. Which row correctly labels the kind of O(log⁡n)O(\log n) each one actually gives?

A

Splay: amortized. FHQ treap: expected. Scapegoat: expected. AVL: worst case.

B

Splay: amortized. FHQ treap: expected. Scapegoat: amortized. AVL: worst case.

C

Splay: worst case. FHQ treap: expected. Scapegoat: amortized. AVL: worst case.

D

Splay: amortized. FHQ treap: worst case. Scapegoat: amortized. AVL: worst case.