Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
0answers
57 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 ...
2
votes
0answers
21 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))=\...
2
votes
0answers
27 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 ...
2
votes
0answers
44 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 ...
1
vote
0answers
58 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 ...
0
votes
0answers
22 views

Do parent pointers affect path-copying in a persistent binary tree?

I am familiar with the concept of path-copying in the context of binary trees to achieve persistent modifications, but I am unsure if the inclusion of parent pointers has any effect on the complexity. ...
0
votes
0answers
33 views

How do Clojure's persistent data structure determine equality?

I'm trying to understand the time complexity of determining equality between persistent data structures in Clojure (Vectors, Maps, Sets, etc.). These are based on data structures pioneered by Phil ...
0
votes
0answers
213 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 ...
0
votes
0answers
34 views

What is a good rule-of-thumb for the size of leaf nodes in a rope?

The formal descriptions of ropes I’ve found use very small numbers like 4 or 8 characters per leaf node as the maximum size. Some also mention that this (obviously) is not a very efficient rope size ...
0
votes
0answers
69 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. ...