Amoebas Having Boring Family Trees

Trees are computational data structures used for storing and searching data. Data is stored at tree nodes. Each node can also contain a link to zero or more "children" nodes. These links can be used in a search algorithm to traverse the tree. Correspondingly, each node may have up to one "parent" node. Only one node in the tree, the "root" node, does not have a parent node.

Abby's class project was due tomorrow morning, and she was still not sure what she was doing wrong. As she looked at her paper, panic began to set in.

The example family tree that her teacher had given her showed a clear network of nodes. There were levels for grandparents, parents, and siblings. But, Abby's tree did not look anything like that. Sometimes, being the only amoeba in her second grade class made life complicated.

Being an amoeba, Abby's family worked differently from those of her classmates. Instead of having two biological parents, she had exactly one. She was born through mitosis, when her parent had literally split in half to form her and her sister Venn. So, Abby's tree started at a single grandparent and branched out as it went down. Each parent could have exactly zero or two children, and each child had exactly one parent node. It was a perfect binary tree. Unfortunately, it looked nothing like what the teacher would be expecting.

On the plus side, Abby found it remarkably easy to trace her lineage back for centuries. Each amoeba on her family tree could have only one parent. Thus, she could follow her family all the way back to her great, great, great grandfather, "Sir Edward the Adventurous", who had been the first amoeba to colonize this particular petri dish. And starting at her great great grandfather, she could search down through the layers and find out how she was related to any other amoeba in the whole dish. But, none of that helped on this class project.

Abby carefully finished labeling her tree. She had one grandfather who had two children: her father and her aunt. Her father then had two children: her and Venn. And her aunt also had two children. All three generations formed only seven nodes on the tree.

Discouraged, Abby gave a bubbly sigh of despair as only amoebas can. She only hoped that her teacher would understand.

Epilogue: Abby actually received double credit for her assignment after she launched into a impromptu 30 minute monologue on the wonderful computational properties of her family tree. First, she described how she could determine the exact relationship to anyone in her family in O(log N) time regardless of the number of generations included. Then, seizing the moment of inspiration, she noted that her family tree was in fact a heap sorted by age. Each amoeba in the tree could have up to two children and the ages of both children were strictly less than that of their parent. Her descriptions were so inspiring that the entire class gave her a standing ovation.

.

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.