Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title Downloads

In-Memory Trees in Mathematica

Thomas H. Meyer Ph.D.
Organization: University of Connecticut
Department: Natural Resources Management and Engineering

Wolfram Technology Conference 2013
Conference location

Champaign, Illinois, USA

Nested lists are one of Mathematica primary data structures, and nested lists are also called trees. However, Mathematica provides no explicit support for user-defined trees (other than TreePlot). A generic tree data structure is presented. The tree is polymorphic so it can be constructed from arbitrary objects (not just keys), which in essence implements a user-defined, in-memory database. The tree supports both unique and redundant keys that are handled with compound keys. Keys are ordered with a user-defined function, which allows trees like binary search trees or even more exotic spatial trees, like quadtrees. (However, this implementation does no balancing.)

Mathematica's unique functional language permits a single function for each fundamental operation: insertions, retrievals, deletions, and updates. The user provides functions to control the insertions, which is why a single generic suite of basic functions is sufficient for a very broad variety of trees. The code is presented along with several examples that illustrate some of the possibilities.

*Wolfram Technology

Downloads Download Wolfram CDF Player

WTC1013-TomMeyer.nb (457.7 KB) - Mathematica Notebook