Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-02-06T22:23:22.248Z Has data issue: false hasContentIssue false

O(1) reversible tree navigation without cycles

Published online by Cambridge University Press:  18 October 2001

RICHARD A. O'KEEFE
Affiliation:
Department of Computer Science, The University of Otago, P.O. Box 56, Dunedin, 9001, New Zealand (e-mail: ok@cs.otago.ac.nz)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Imperative programmers often use cyclically linked trees in order to achieve O(1) navigation time to neighbours. Some logic programmers believe that cyclic terms are necessary to achieve the same in logic-based languages. An old but little-known technique provides O(1) time and space navigation without cyclic links, in the form of reversible predicates. A small modification provides O(1) amortised time and space editing.

Type
PROGRAMMING PEARL
Copyright
© 2001 Cambridge University Press