|
|
|
|
|
by nightcracker
2795 days ago
|
|
Ignore all the other noise about expected vs amortized vs just O(1). It's not what's relevant here. 1. Zip trees do not have O(1) insert/remove. They have O(log n) insert/remove (because they have to search the tree to find where to insert/remove), with O(1) additional restructuring time. 2. You can have an ordered data structure with O(1) insert, but not O(1) insert and O(1) find-min simultaneously. You can have O(1) insert trivially by just delaying all actual inserts by putting them into an array, and only actually insert them later when a search happens. |
|