News for hackers. Stuff that matters.
Re:Zip Trees by nightcracker on Wednesday October 24, 2018 @11:05AM (#18293033)
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.

There are no comments on this comment yet.