In-Memory Trees in Mathematica

Meyer WTC 2013

The Notion

Trees are a basic computer science data structure that allow orderable data sets to be organized so that solving certain common problems is easy and efficient.

Find the element(s) of a set nearest to some search key

Find the element(s) of a set whose keys are exact matches to some search key

Find subsets that satisfy general predicates

Implement databases

Definitions

A graph is a set of nodes and a set of edges.

Nodes hold data

Edges hold connectivity information

A tree is a directed graph having no cycles.

Trees are Recursive

Because a tree is a set of nodes and edges, the empty tree (no nodes and no edges) is a tree.

A single node is a tree.

A node can have nodes/trees “below” or “inside” it.

=

A child node is a node inside/below another node.

The one-and-only root node is the child of no other node.

A node without children is a leaf node.

Properties of Trees

How many children are allowed per node?
What is the ordering imposed on the keys?
Are duplicated insertions allowed? 
If so, what is done with the duplicated data? 
Does the tree support hierarchical insertions (compound keys)?
Is the tree balanced?
Is the tree persistent?

Many Types of Trees

Although there are many types of trees, fairly generic code can be written to implement a great many of them.

The only difference is a list of predicates supplied by the user a a function that resolves duplication insertions.

Operations on Trees

Create

Create an empty tree.

Insert

Insert a key into a tree.

Find

Return the data in a node whose key is nearest to a search key.

Traverse

Return all the nodes in a tree following a depth-first traversal.

Delete

Remove a node from a tree

Example 1: Binary Search Tree for Numerics

Properties:

A set of random keys is inserted in logarithmic time. Sorted keys are inserted in linear time, which is worst case.

Finding a key is usually accomplished in logarithmic time, or linear time worst case.

Creating a BST

SetDirectory["D:\\MyDocumentsD\\Mathematica Stuff\\Trees"];
Needs["nAryTree`"];

nAryCreate[keyValue, testingFunctions] returns a n-ary tree with a single node containing keyValue.

testingFunctions is a list of predicate functions: {equality,(Subscript[child, 1]),(Subscript[child, 2]),...,(Subscript[child, n])}

Predicate functions must return either True or False and nothing else for any valid key value.

testingFunctions={Equal,Less,Greater};

tree=nAryCreate[10,testingFunctions]

The first element is the data stored in this node. The second element is the left subtree. The third element is the right subtree. There are two children because the testing function list has two (Subscript[child, i]) elements.

More insertions

tree=nAryInsert[tree,5,testingFunctions]

tree=nAryInsert[tree,15,testingFunctions]

tree=nAryInsert[tree,1,testingFunctions]

tree=nAryInsert[tree,20,testingFunctions]

Traversal

An in-order traversal of a binary search tree produces a sorted list. Traversal is implemented here as 

Print the key in the current node;
Recursively Print the children nodes in the order they occur;

nAryTraverse[tree]

Search

Test that all elements in the tree can be found by searching

nAryFind[tree,#,testingFunctions]&/@nAryTraverse[tree]

Create a big tree and try to find everything in it.

keyList=RandomInteger[{0,1000},100];

tree=nAryBatchCreate[keyList,testingFunctions];
trav=Sort[nAryFind[tree,#,testingFunctions]&/@nAryTraverse[tree]]

Union[keyList]==trav

Example 2: Binary Search Tree for Strings

The same code works for Strings. All I need do is change the predicate functions.

stringEqual[newKey_String,existingKey_String]:=Order[newKey,existingKey]==0

stringEqual["hello","hello"]

stringEqual["Hello","hello"]

stringBefore[newKey_String,existingKey_String]:=Order[newKey,existingKey]==1

stringBefore["hello","hello"]

stringBefore["hello","world"]

stringAfter[newKey_String,existingKey_String]:=Order[newKey,existingKey]==-1

stringAfter["hello","hello"]

stringAfter["hello","world"]

Try it out

testingFunctions={stringEqual,stringBefore,stringAfter};

TheRaven=StringSplit[ExampleData[{"Text","TheRaven"}]];

tree=nAryBatchCreate[TheRaven,testingFunctions];
trav=Sort[nAryFind[tree,#,testingFunctions]&/@nAryTraverse[tree]]

Actually, Order works with Numerics, too, so I could have used it for everything

Order[1,8]

and even for things that aren’t immediately clear to me what they mean

Order["hi",8]

Example 3: Duplicates

Duplicate key insertions can be allowed.
When duplicate keys are allowed, the user must decide what to do with the duplicates. Some strategies include

keep a list of the duplicated insertions

the item being inserted can be a complicated record having many pieces and the key is but one part of the whole, so keeping records with duplicated keys does not necessarily imply keeping lists of fully duplicated data.

keep a count of the duplicated insertions

insert the duplicates in to a subtree contained as the data of this node

called a compound key

I take the first strategy. Write my predicates to handle keys that are lists of duplicates

myEqual[x_,key_List]:=x==First[key]
myEqual[x_,key_]:=x==key

myLess[x_,key_List]:=x<First[key]
myLess[x_,key_]:=x<key

myGreater[x_,key_List]:=x>First[key]
myGreater[x_,key_]:=x>key

When a duplicate is encountered, replace the key with a list of the duplicated keys

duplicateAction[x_,key_List]:=Append[key,x]
duplicateAction[x_,key_]:={key,x}

testingFunctions={{myEqual,duplicateAction},myLess,myGreater};

tree=nAryCreate[10,testingFunctions]

tree=nAryInsert[tree,10,testingFunctions]

tree=nAryBatchCreate[RandomInteger[{0,1000},100],testingFunctions];
nAryTraverse[tree]

nAryFind[tree,#,testingFunctions]&/@Union[Flatten@nAryTraverse[tree]]

Example 4: Spatial Data Structure: Quadtree

Recursively divide space into quadrants whose common corner is at the data points.
To insert a point, compare to the point in the current node and insert into one of four children corresponding to the SW, SE, NE, NW quarter planes defined by the node’s point.

qtEqual[x:{xe_,xn_},key:{ke_,kn_}]:=x==key

sw[x:{xe_,xn_},key:{ke_,kn_}]:=xe≤ke&&xn≤kn

nw[x:{xe_,xn_},key:{ke_,kn_}]:=xe≤ke&&xn>kn

se[x:{xe_,xn_},key:{ke_,kn_}]:=xe>ke&&xn≤kn

ne[x:{xe_,xn_},key:{ke_,kn_}]:=xe>ke&&xn>kn

testingFunctions={qtEqual,sw,nw,ne,se}

Quadtree Insertions

tree=nAryCreate[{0,0},testingFunctions]
nAryTraverse[tree]
nAryFind[tree,#,testingFunctions]&/@nAryTraverse[tree]

tree=nAryInsert[tree,{-1,1},testingFunctions]
nAryFind[tree,#,testingFunctions]&/@nAryTraverse[tree]

Make a big tree

nPoints=100;
points=RandomReal[{-1000,1000},{nPoints,2}];
ListPlot[points,AspectRatio->Automatic]

tree=nAryBatchCreate[points,testingFunctions];
nAryTraverse[tree]

Depth[tree]

Subsets

All points SW of the first point are in the first child tree

tree[[1]]

Partition[Flatten[tree[[2]]],2]