The Doc Dialer: Storing Data Elements | WebReference

# The Doc Dialer: Storing Data Elements

## Storing Data Elements

We want to index our eight presidents by their first name + last name, as well as their last name + first name. Adhering to the principles of the trie, here is how we build the trie for the eight presidents. First we allocate memory for the top level 10-element array, called `tree`:

``var tree = new Array(10);``

Then we allocate memory for another 10-element array:

``var tmpArray = new Array(10);``

which we assign `tree[2]` to point to:

``tree[2] = tmpArray;``

Now we have a 10-element array at the second element of the top level `tree` array. The phone key number 2 is associated with the letters A, B, and C. From our eight presidents, the following ones start with either A, B, or C (first name or last name): Carter, Bill (Clinton), Clinton, and Bush. Since we don't have any collision between their second letter, we can store them at the current level of hierarchy:

``````tree[2][2] = 2; // Carter, Jimmy
tree[2][4] = 4; // Bill Clinton
tree[2][5] = 4;  // Clinton, Bill
tree[2][8] = 6; // Bush, George``````

Let's examine what's happening at the digit 3. The key 3 is associated with the letters D, E, and F. Quick scanning of the president list, we find that only Ford is indexed by the digit 3. Hence, we can store him at the top level `tree` array, element number 3:

``tree[3] = 5; // Ford, Gerald``

The digit 4 (associated with G, H, and I) is more crowded. First we create two more levels of hierarchies, one at `tree[4]` and one at `tree[4][3]`:

``````var tmpArray = new Array(10);
tree[4] = tmpArray;
var tmpArray = new Array(10);
tree[4][3] = tmpArray;``````

Two names crowd the digit 4:

``````tree[4][3][7] = 5; // Gerald Ford
tree[4][3][6] = 6; // George Bush``````

The digit 5 is associated with J, K, and L, and is loaded with five names. The first three are Jimmy Carter, Lyndon Johnson, and Kennedy (John). Allocating one array at `tree[5]` is sufficient:

``````var tmpArray = new Array(10);
tree[5] = tmpArray;
tree[5][4] = 2; // Jimmy Carter
tree[5][9] = 7; // Lyndon Johnson
tree[5][3] = 8; // Kennedy, John``````

The interesting pair is John Kennedy and Johnson (Lyndon). As you can see you need five level or hierarchies before you can distinguish between them:

``````var tmpArray = new Array(10);
tree[5][6] = tmpArray;
var tmpArray = new Array(10);
tree[5][6][4] = tmpArray;
var tmpArray = new Array(10);
tree[5][6][4][6] = tmpArray;
tree[5][6][4][6][5] = 8; // John Kennedy
tree[5][6][4][6][7] = 7; // Johnson, Lyndon``````

Nixon (Richard) is alone on digit 6, associated with M, N, and O:

``tree[6] = 3; // Nixon, Richard``

Finally, we need one level of hierarchy at digit 7, associated with P, R, and S, for Reagan (Ronald), Richard Nixon, and Ronald Reagan:

``````var tmpArray = new Array(10);
tree[7] = tmpArray;
tree[7][3] = 1; // Reagan, Ronald
tree[7][4] = 3; // Richard Nixon
tree[7][6] = 1; // Ronald Reagan``````

Produced by Yehuda Shiran and Tomer Shiran

Created: February 14, 2000
Revised: February 14, 2000

URL: http://www.webreference.com/js/column57/3.html