Find and skim the paper ``Planar point location using persistent search trees\'\

Question

Find and skim the paper ``Planar point location using persistent search trees'' by Sarnak and Tarjan (1986). (In Emory's network, you can get the full text via dl.acm.org.) In this paper, they describe a persistent red-black search tree (but fancier than ours), using a combination of path-copying and ``fat nodes''. This paper is also discussed on wikipedia, so you can look there (under ``persistent data structures'').

(a).They do not implement ``full persistence'', but a more limited kind (that suffices for their ``point location'' problem). Describe the limited kind of persistence that they implement.

(b).What are their big-Oh bounds on the time and space used, per update (insertion or deletion)? Also for each bound, state whether it is a worst-case bound or an amortized bound.

Explanation / Answer

a) They implemeneted using 2 paths in structure.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.