Splay trees, compression, encryption, and embedding (by alaric)
There's a little-known data structure with some useful properties; the Splay tree.
It's quite a useful data structure in its own right, but it also has interesting applications in data compression, and cryptography...
Read the Wikipedia article for details, but in summary, it's a "dictionary"; a data structure mapping keys to values. The canonical example is a telephone directory, where you look up a name to get a phone number. The splay tree stores the entries in a tree; one entry is the "root" of the tree, and each entry potentially has left and right child entries (so any given entry may have no children, a left child, a right child, or both) - with the rule that all the entries in the subtree starting from the left child of an entry have names that come before the name in that entry, and all in the right subtree have names that come after the name in the entry.
To find an entry, just start at the root, comparing the name in that entry to the one you're after. If you find it, then hey presto, you have your entry. If not, does the name you're looking for came before the one you've found? If so, try the left child. If not, try the right. If that child doesn't exist, then give up, because that name's not in the tree.
As described so far, this is a Binary search tree, of which there are many variants. The unique thing about a splay tree, however, is that when the desired entry is found, the tree is then rearranged so that the found entry is closer to the root (I've seen descriptions that imply the node is moved all the way up and becomes the new root, and descriptions that just imply it moves up a level, so would need to be found several times to end up as the root).
The closer an entry is to the root, the less search steps are required to find it, so if some names looked up in the tree are more common than others, splay trees will end up with those nearer the root and so faster to find, thus improving their performance. Which is quite useful.
ARGON, Crypto / security | alaric | 
Thu 24th Aug 2006 9:41 pm
Subscribe