Arbor digitalis

Arbor digitalis est structura datorum pure functionalis cum alias functionales datorum structuras efficienter exsequitur. Arbor digitalis accessum arboris digitis (folia) tempore constanti amortizato praebet, ubi data reponuntur, et in quoque nodo interno exitum operationis associativae ad proles adhibitae acervat. Haec data summaria in nodis internis acervatis adhiberi possunt ad functionalitatem structurarum datorum praeter arbores praebandam. Exempli gratia, nodos internos per minimum prolum in arbore primatum notare ordinem primatus exsequi potest, vel nodos per summam foliorum in liberis notare numerum indicatum exsequi potest.

Programmatores arbores digitales exsequi possunt cum aut sine^[1] aestimatione pigra, sed pigritia exsecutiones simpliciores sinit.

Arbores digitales primum anno 1977 a Leonida J. Guibas et aliis publicatae sunt,^[2] temporibus statis post expolitae, in exemplis quae arbores AVL,^[3] arbores digitales impigras, simpliciores arbores digitales 2–3,^[4] arbores B, aliasque res adhibent.

Nexus interni

Notae

↑ Kaplan et Tarjan 1995.
↑ Guibas et alii 1977.
↑ Tsakalidis 1985.
↑ Hinze et Paterson 2006.

Bibliographia

Guibas, Leonidas. J., E. M. McCreight, M. F. Plass, et J. R. Roberts. 1977. A new representation for linear lists. Conference Record of the Ninth Annual ACM Symposium on Theory of Computing, pp. 49–60.
Hinze, Ralf, et Ross Paterson. 2006. Finger Trees: A Simple General-purpose Data Structure. Journal of Functional Programming 16(2):197–217. doi:10.1017/S0956796805005769. PDF.
Kaplan, H., et Robert E. Tarjan. 1995. Persistent lists with catenation via recursive slow-down. Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, 93–102.
Tsakalidis, A. K. 1985. AVL-trees for localized search. Information and Control 67(1–3):173–194. doi:10.1016/S0019-9958(85)80034-6.

Nexus externi

De arboribus digitalibus, www.soi.city.ac.uk
Archivum EdisonCore, hackage.haskell.org
Exemplum arborum 2–3 in C#, blogs.msdn.com
Exemplum arborum digitalium Hinze-Patersonianarum in C#, dnovatchev.wordpress.com
Examplum arborum digitalium Hinze-Patersonianarum in Java, code.google.com
"Finger tree library for Clojure," github.com
"Finger tree in Scalaz," github.com
"Monoids and Finger Trees in Haskell," apfelmus.nfshost.com
"Verified Finger Trees in Isabelle/HOL," afp.sourceforge.net

[1] Kaplan et Tarjan 1995.

[2] Guibas et alii 1977.

[3] Tsakalidis 1985.

[4] Hinze et Paterson 2006.

[1]

[2]

[3]

[4]