Newsletter sign-up

View all newsletters

Sign up for our technology specific newsletters.

Enterprise Java

Email Address:

Plant your data in a ternary search tree

Create an English dictionary that checks spelling and matches words as you type

By Wally Flint, JavaWorld.com, 02/16/01

Page 3 of 4

Flexible arrays

You may use a TST as an array of type Object. Simply convert the array index to a string and regard it as a TST key. For example, to store myObject into slot int i = 79, call myTST.put(String.valueOf(i), myObject);. You can easily wrap a TST in a class that automatically performs the int-to-string conversion. It isn't necessary to declare the capacity of such an array in advance -- that is, when the array instantiates.

You can use an arbitrary separator (say, '\u0800') to separate indices of multidimensional arrays. For example, to add another index int j = 7 to the prior example, call myTST.put(String.valueOf(i) + '\u0800' + String.valueOf(j), myOtherObject). Just as it isn't necessary to declare the capacity of such an array in advance, it isn't necessary to declare its dimensions in advance either. In fact, a one-dimensional array can occupy the same TST as other multidimensional arrays. In that case, an array's data with a specific dimension will not overwrite those arrays having other dimensions.

A TST database

Let's use a TST to build the following database:

A simple database

Employee ID	Employee eye color	Employee hair color
33	Blue	Blue
37	Brown	Brown

Use special marker characters (e.g., '\u0800', '\u0801', and so on) for a TST node's splitchar to identify database columns. Figure 4 depicts a database with three columns and two entries. The columns are employee ID ('\u0800'), employee eye color (\u0801), and employee hair color ('\u0802').

Figure 4. A TST database
Click on thumbnail to view
full-size image. (25 KB)

The column identified by the splitchar '\u0800' contains an integer ID that is unique for each employee, like a social security number. Such values are known as primary keys. The ID entry for person number 33 is added to the database with the statement myTST.put(String.valueOf(33) + '\u0800', emp33DBEntry), where emp33DBEntry is an instance of a DatabaseEntry class (described below). Placing the marker characters at the end of the keys, rather than at the beginning, allows columns and entries to share TST nodes, thus reducing the memory occupied by the database.

As depicted in Figure 4, an instance of the DatabaseEntry class will be stored in one employee ID node, a '\u0800' node. The same DatabaseEntry instance will also be stored in two linked lists. One of these lists will reside in an eye color node -- a '\u0801' node -- and the other in a hair color node -- a '\u0802' node. The database entry object has a handle to the TST node that terminates its primary key column entry, the '\u0800' node. It also has a handle that points to the LinkedList node storing its eye color entry and another handle that points to the LinkedList node storing its hair color entry. Each of these LinkedList nodes has static handles to the TST nodes that encapsulate the LinkedLists. That allows you to decipher the column value by walking the tree backwards until you reach the root node.

To retrieve the hair color of employee 37, obtain the database entry object indexed by the string "37" + '\u0800'. From this database entry object, obtain the hair color LinkedList node; from this node, obtain the encapsulating TSTNode, '\u0802'. From '\u0802', walk backwards up the tree, reconstructing the hair color value as you go.

 

Improve efficiency with Visual Studio(r) 2010 Beta 2. - Microsoft

About Us | Advertise | Contact Us | Terms of Service/Privacy

Copyright, 2006-2008 Network World, Inc. All rights reserved.