Lists and Data Structures

(View the complete code for this example.)

A tree contains nodes and edges and starts with a root node. The root node is connected via branches to other nodes, called child nodes. Every node except the root node has exactly one parent node. A tree has no cycles: any two nodes can be connected by a unique path through the tree.

A binary tree is a tree in which every node has at most two child nodes. A binary search tree (BST) is a binary tree in which each node has a value (called a key), a link to a left child node, and a link to a right child node. Either or both child nodes might be null. By starting at the root node, you can quickly determine whether a value is in the tree. If not, you can insert the value into the tree by modifying one of the null left or right child nodes of an existing node.

Figure 6 shows the binary search tree that corresponds to the integer sequence {5, 3, 1, 9, 6, 4}.

In terms of data structures, each node is a list that contains three items: the first item is the key value, and the second and third items are the child nodes. The child nodes are initially empty, but values can be assigned to them as the tree grows. In terms of SAS/IML lists, the following statements define a node in a BST. The call to PROC FORMAT defines a format that will be useful later in this section.

/* L[i] is key value, L[2] is left child, L[3] is right child */
proc format;
    value BSTFmt  1='Key'  2='Left'  3='Right';
run;

proc iml;
/* A node is a three-item list:
   node[1] contains the KEY   value
   node[2] contains the LEFT  value (or empty if null)
   node[3] contains the RIGHT value (or empty if null) */
start BSTNewNode(value);
   node = ListCreate(3);     /* create list with 3 null items */
   call ListSetItem(node, 1, value);   /* set KEY value */
   return node;
finish;

The following algorithm searches a binary tree to determine whether a target value is in the tree:

In particular, the following SAS/IML function uses lists to look up a value in a binary search tree:

/* Search for a target value in a binary search tree.
   Input: root is the root node of a BST,
          value is the target value.
   Output: path contains the path to the node that contains the target
          value or the node where the target value can be inserted.
   Return: 1 if the target value is in the tree; 0 otherwise */
start BSTLookup(path, root, value);
   KEY = 1; LEFT = 2; RIGHT = 3;
   path = {};
   T = root;
   do while (1);
      if value = T$KEY then
         return 1;                  /* found it: return path to subitem */
      else if value < T$KEY then do;
         path = path || LEFT;       /* add to path */
         T = T$LEFT;                /* new root is left child */
      end;
      else do;
         path = path || RIGHT;      /* add to path */
         T = T$RIGHT;               /* new root is right child */
      end;
      if type(T)='U' then
         return 0;                  /* not found: return path to subitem */
   end;
finish;

For example, if the target value is 6 and you run the algorithm on the binary tree in Figure 6, the function does the following:

The previous BSTLookup function assumes that the binary search tree already exists. You can write additional functions to create a BST. The following statements define two functions:

/* pass a vector of key values to this routine to create a BST
   that has those values as keys */
start BSTCreate(x);
   bst =  BSTNewNode( x[1] );
   do i = 2 to nrow(colvec(x));
      run BSTInsert(bst, x[i]);
   end;
   return bst;
finish;

/* Insert a new branch for a key value in a BST. If the value
   already exists, do nothing (so there are never duplicates) */
start BSTInsert(root, value);
   if ListLen(root)=0 then do;   /* List empty. Set root node */
      root = BSTNewNode(value);
      return;
   end;
   /* otherwise, search tree to find value */
   found = BSTLookup(path, root, value);  /* if found, return */
   if ^found then                         /* else add to sub-path */
      call ListSetSubItem(root, path, BSTNewNode(value));
finish;

To illustrate the process of building the tree in Figure 6, the following sequence traces through the algorithm for the key values {5, 3, 1, 9, 6, 4}:

With these functions defined, you can create and search a BST. The following statements create the tree in Figure 6 and determine whether the target values 6 and 10 are in the tree:

x = {5 3 1 9 1 6 4}`;
bst = BSTCreate(x);

found = BSTLookup(path, bst, 6);
print found[L="Was 6 found?"], path[L="Path from root" F=BSTFmt.];
found = BSTLookup(path, bst, 10);
print found[L="Was 10 found?"], path[L="Path from root" F=BSTFmt.];
quit;

There are other algorithms that you can define to operate on binary trees. The LstBST.sas file, which is contained in the SAS/IML sample library, includes functions that produce a graph of a BST (like Figure 6), that compute the depth of a BST, and that return the set of all edges in a BST. For example, Figure 6 is created by using the following statements:

%include sampsrc(LstBST.sas);       /* define modules */
proc iml;
load module = _all_;                /* load modules */
x = {5 3 1 9 1 6 4}`;
bst = BSTCreate(x);
title "Diagram of Binary Search Tree";
call BSTPlot(bst);
quit;

You can specify the SOURCE option in the %INCLUDE statement to display the contents of the program file in the SAS log.