0
$\begingroup$

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 also be persistent.

I know that there is an candidate like randomized immutable treap, I'd like to know if there are other candidates.

$\endgroup$

1 Answer 1

0
$\begingroup$

There are many data structures for balanced search trees; pick any one. Then, you can make it persistent using path copying, or Driscoll, Sarnak, Sleator, and Tarjan's technique -- these techniques are generic and can be applied to any tree data structure.

$\endgroup$
1
  • $\begingroup$ Sounds great, thanks a lot! $\endgroup$
    – lyhokia
    Jan 23, 2022 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.