Binary Search Trees and Speck the Spider

Binary search trees (BST) organize data to allow efficient searches by value. Data is stored in tree nodes. Each tree node also maintains pointers at most two children nodes: a left child and right child. The tree maintains the property that at each node values in the left subtree are less than the value of the current node. In contrast, values in the right subtree are greater than (or equal to) the values in the current node. This structure allows an efficient search by walking down the tree and branching in the direction of the value for which you are looking. A balanced binary search tree allows O(log N) search.

Speck was a spider. As such, he lived a typical spider lifestyle. He built webs, ate flies, and enjoyed discussing the weather with his neighbors. In fact, for those who had never been to visit his web, he seemed like a perfectly normal spider.

However, the truth was, Speck was not a typical spider. He was obsessive about his food choices and demanded a level of variety that was unheard of for other arachnids. Speck insisted on keeping a supply of at least 25 different types of bugs in his web.

Speck also insisted on absolute organization in his food supply. What good was 25 varieties of bugs, if he could not quickly find the one that he wanted? While most spiders kept their bugs distributed randomly throughout their webs, that prospect seemed absurd to Speck. He loathed such disorganization. Instead, like any rational chef, Speck organized his food choices in alphabetical order.

The result of these preferences was a new type of web design that Speck developed through long days of trial and error. He called it a binary search web. The web consisted of nodes, clusters of webbing that stored his bugs, and strings of web between the nodes. The whole thing was organized vertically. At the top was a single "root" node attached to an old storm gutter. Each node in the web could have at most two "children" nodes below them. These nodes were attached securely to their parent node above using a strong strand of webbing. As a result, the web branched out wider as it progressed downwards, taking on a vaguely triangular shape.

In order to maintain his organizational structure, Speck insisted that the bugs stored at each node obeyed a particular alphabetical ordering. Specifically, the bugs in all of the nodes down the left-hand path from a given node had to be BEFORE the current node's bug in alphabetical order. Similarly, all of the bugs in all of the nodes down the right-hand path from a given node had to be AFTER the current node's bug in alphabetical order. This way, Speck could quickly find any bug that he was looking for by simply descending the web.

For example, one morning Speck decided that he wanted a fly for breakfast. He started at the top of his web, where he slept, and examined the bug there. It was a lady bug. Since flies come before lady bugs, Speck sleepily walked down the thread on the left-hand side of the node. On his way he paused for a drink of dew that had collected during the night. At the next node, Speck found a beetle. Since flies come after beetles, Speck now chose the right-hand path. There he found the three day old fly. Speck happily ate his breakfast and then decided to take a mid-morning nap.

The advantage of the branching structure of the web is that, as long as he kept the structure well balanced, Speck could find any bug that he was looking for in O(log N) time. What this meant was that Speck could double his inventory of bugs while only adding one additional step to his search! Given that Speck only did his searches when he was very hungry, this efficiency was important. He had heard his friends claim that they just ate whatever bug was closest. Imagine that!

The web also leant itself to the addition and removal of bugs. Adding a new bug simply consisted of walking the bug down the web (while making the correct alphabetical branches) until he hit a dead end. Then he would add a new child node, with the new bug, to the correct side of the current node. Adding a new node just meant spinning some webs, and Speck enjoyed that part of being a spider a lot. As he saw it, making webs was definitely the best part of being a spider.

Sadly, despite the obvious advantages of the binary web structure, Speck never managed to encourage wide adoption. Instead, his friends stuck with the classic circular patterns, citing their ascetic value.

-----------------

For more information on tree data structures, see why amoebas have boring family trees.