Questions tagged [persistent-data-structure]
A persistent data structure is a data structure that is never modified in place, but by creating a new data structure.
20 questions
2 votes
0 answers
118 views
Persistent sequences with insert and delete and canonical structure?
I am wondering if there can be such a thing as a persistent data structure for sequences that a) supports the following operations: insert(index, elem) in $O(log\, ...
- 21
0 votes
1 answer
96 views
Which particular data structure should I use if I want a persistent balanced search tree?
As title, I'm trying to implement a text editor with the rope data structure, which is backed by binary search tree. Since I want it to have persistent undos, the underlaying data structure should ...
- 3
3 votes
1 answer
83 views
Formal semantics of a mutable/imperative stack
When introducing formal semantics for data structures, immutable stacks are a nice simple example : $\mathit{is\_empty}(\mathit{create()})=\mathrm{True}$ $\mathit{is\_empty}(\mathit{push}(e, s))=\...
- 233
2 votes
0 answers
87 views
Distributed Computing: Persistent Data Structures in Functional Programming versus Wait-Free Data Structures
Persistent (aka immutable) data structures in functional programming sidestep issues of shared memory mutual exclusion, and thus also issues such as data races that arise and which may be difficult to ...
3 votes
0 answers
240 views
Persistent data structures representing a directed graph's paths
Are there any standard persistent data structures that facilitate the following? tabulating, for each arc in a rooted, oriented, acyclic multigraph, the set of root-emanating paths containing the arc ...
- 113
2 votes
0 answers
88 views
Persistent data structure with double and subtract operations
I am seeking a data structure that maintains an array of N numbers and supports the following two operations: Double the first i numbers Subtract the first i numbers of a previous version from the ...
- 121
0 votes
0 answers
619 views
Analysis of finding the k-th largest element in a subsegment of an array
Given an array $A$ of length $N$. There are $Q$ queries, each queries will be in the form ...
1 vote
0 answers
85 views
combine divergent persistent red-black tree instances
Given a persistent red-black tree, I've been searching for an algorithm, approach, or equivalent data structure that allows me to efficiently merge two instances of the tree produced by divergent ...
- 123
4 votes
1 answer
233 views
How do confluently persistent data structures handle merge conflicts?
From my limited understanding fully persistent data structures allow changes to be made to previous nodes, with new nodes creating a branch rooted at the changed node, resulting in a tree of nodes and ...
- 143
3 votes
2 answers
2k views
What is the "Chairman Tree"?
My competitive programming coach told me of a balanced binary tree used by a lot of Chinese competitors that has all the functions of any other balanced binary tree and is fully persistent and runs ...
- 133
3 votes
2 answers
187 views
Using persistence on a constant database
I'm quite new to understanding persistent data structures, so bear with me. Consider some database with data of the form $(\text{id}, d_1, d_2)$. The last two could e.g. mean production data and ...
- 219
5 votes
2 answers
767 views
Is it possible to build a heap from the root to the leaves?
Most books on data-structures will briefly introduce heaps (aka priority queues) and then move to describe the "trick" allowing heaps to be implemented as arrays. I've been looking for a way ...
- 1,388
3 votes
1 answer
128 views
Guessing the structure of a finger tree from the number of elements
I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger ...
- 525
0 votes
0 answers
113 views
Immutable data structures for 2d+ lattices
I would like to find an immutable/persistent data structure that allows efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. ...
- 101
4 votes
2 answers
703 views
How append, prepend, and generally insertAt work in RRB-tree
I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can't get is how insertion at an index should be performed step by step. Can anyone proficient ...
- 255