Data Structures and Recursion

Intro

Trees

Intro
Data structures store data in a way that reflects some relationship between the data, and is easily useable in a program. Lingo provides some built-in data structures such as lists. This section describes how data structures are created using objects, and some of their common uses in animation. Make sure you’re familiar with the material in Object-Oriented Fundamentals.

The two types of structures covered here are lists and trees, which are both very common and useful. Lingo provides an implementation of lists already; this section shows how to make lists using objects as an intro to making trees.

Uses for lists are fairly obvious. Some uses for trees:

  • 3D world hierarchy
  • working with XML, HTML, etc, which are hierarchical document formats
  • hierarchical displays (such as a file system display)
  • decision trees
  • and many others

Terminology
An object data structure is made of objects that are created from the same script (class). When these objects are assembled into a data structure they are often called nodes of the data structure.

Each node will have properties that are references to other nodes. These object references are what bind the data structure together and are called pointers. How the nodes are arranged using these pointers determines the type of data structure created.

In the diagrams of this section, a square represents a node and an arrow represents a pointer.

Lists
A list is a sequence of nodes. Each node has a pointer to the next node in the list. The nodes in this diagram are created from a script called “listNode”.

To store data in a list, each node has a property or properties that store the data.

The script shown below can be used for the nodes of a list data structure. It has methods for adding a node to the end of the list, and for getting a node at a given position. The property key stores some type of data.

property nextNode
property key

on new(me, _key)
key = _key
return me
end

on addNode(me, _key)
if nextNode = void then
nextNode = script(“listNode”).new(_key)
else
nextNode.addNode(_key)
end if
end

on getNodeAt(me, index)
if index = 1 then return me
if nextNode = void then return void  –index out of range
return nextNode.getNodeAt(index – 1)
end if

script “listNode”

Recursion
It might appear strange that the addNode() and getNodeAt() methods in the listNode script actually call themselves. This programming technique is known as recursion, and is essential for making efficient use of lists and trees.

To understand what is happening, trace the execution from when the method is called on the first node in the list. Each time the method calls itself it moves one node down the list, which is called “traversing” the list. Eventually, the execution reaches what is called a base case at which point there are no further recursive method calls.

In the addNode() method the base case is nextNode = void, which means the end of the list has been reached and the new node can be added.

In the getNodeAt() method there are two base cases. Either the desired node is reached (index = 1) or the end of the list is reached before finding the desired node (nextNode = void). When the getNodeAt() method reaches its base case, the result is returned back through the stack of recursive method calls.

Recursion is useful for working with lists because a list is a recursive data structure. That is, a list is defined in terms of itself. The recursive definition of a list is: “a list is a node followed by a list, or void.”

Try writing recursive methods for the listNode script that:

  • delete the last node in the list
  • delete a node at a given position
  • add a node at a given position
  • return the node whose key matches a given value
  • return the number of nodes in the list
  • return a string that contains the keys of the nodes
  • return the sum of the keys of the nodes (if key is numeric)

Some of these methods are easier to write if each node also has a pointer to the previous node in the list. Such a list is called a “double-linked” list. A listNode script that contains the methods above can be downloaded here. It doesn’t support deleting the first node in the list for the sake of simplicity (how would you do it? Hint: it requires a list implementation using two scripts).

Trees
A tree is also a recursive data structure. It’s similar to a list, except that it can have more than one “next node”. Usually it is drawn vertically to emphasize its heirarchical nature, with next nodes called ‘children’ and the previous node called the ‘parent’.

The top node of the tree is usually called the ‘root’, and is the only node that has no parent. The bottom nodes, which have no children, are called ‘leaves’. Following successive parent pointers from a node will eventually reach the root, and the nodes on this path are the ancestors of the node (not to be confused with the script ancestor property used for inheritance).

Each node in the tree is the root of a sub-tree. A sub-tree can be described as “the sub-tree rooted at this node”.

property parent
property child
property a   –numerical

on new(me, _a)
child = []
a = _a
return me
end

on addChild(me, node)
child.add(node)
node.parent = me
end

on addTo(me, b)
a = a + b
repeat with ch in child
ch.addTo(b)
end repeat
end

on sumTree()
sum = a
repeat with ch in child
sum = sum + ch.sumTree()
end repeat
return sum
end

Sample tree node script that stores a single number

The script above can be used for the nodes of a tree that stores a single number at each node. Like the methods that traverse the list data structure, a recursive method can be written to traverse and process a tree data structure. The example methods addTo() and sumTree() both traverse the tree.

n.addTo(num) increments by num the value in each node in the sub-tree rooted at n. If n is the root of the tree, all nodes in the tree are incremented.

n.sumTree() returns the sum of the values stored in the nodes in the sub-tree rooted at n. If n is the root of the tree, the sum of all nodes in the tree is returned.

These recursive methods visit the nodes in the tree in this order:

This is called a ‘depth-first’ traversal since it travels to the bottom of the tree first, rather than processing one level before going to the next.

Here is another tree node script that shows some more recursive tree methods

One thought on “Data Structures and Recursion

  1. Pingback: Space Viewport 1.0 | Join My Conversation