4 ms·

One data structure I recently found myself wanting is a tree-based "array", with O(log n) access by index / insertion anywhere / deletion anywhere. Kinda weird

• Munksgaard 4y ago
  That sounds like a pretty run-of-the-mill balanced binary tree? Rust has a BTreeMap: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...
  • vanviegen 4y ago
    Inserting into an array increments the indexes of all subsequent values. How would a regular BTree emulate that behavior?
    • AstralStorm 4y ago
      It would rebalance on insert with O(log N) performance but chunky constant factor, keeping the ordering so access by index is also O(log N) with low constant factor... Which is why usually you would use a red-black tree rather than a BTree, as it has much lower constant for insertion and access by index. However higher for traversal in order.
• vanviegen 4y ago
  That does sound useful, although I'm having some trouble thinking of what for exactly. :-) And indeed, I don't recall seeing something like that. At a first glance O(log n) seems easy to do in the average case, but perhaps not in the worst case.
  • socksy 4y ago
    I suppose it's quite similar to the idea of Bagwell's persistent data structures[1] — those are particularly useful for lock free coding and with a high enough branching factor could be not as much overhead as a linked list or just plain copying. [1] https://hypirion.com/musings/understanding-persistent-vector-pt-1 https://hypirion.com/musings/understanding-persistent-vector...
• Koshkin 4y ago
  Well, doesn’t the “index” need to be stored in the tree itself for this to work? If so, the tree just represents an ordered map. (Changing indexes after deletion or insertion would be a problem, though.)
  • im3w1l 4y ago
    https://stackoverflow.com/a/837911 https://stackoverflow.com/a/837911 disregard the O(1) discussion.