The post title, "On Loggin'," is a pun on the algorithmic time-complexity of an ordered binary tree seek operation: O(n * log(n)). This lecture provides my advice in regard to sorting data by using binary trees. (From Bouvier's Law Dictionary, Revised 6th Ed (1856) [bouvier]: ADVICE, com. law. A letter [...] intended to give notice of [facts contained].) My lectures are in the Public Domain, and are free of charge. "By order of the Author." - Mark Twain, _Huckleberry Finn._ A tree is a directed acyclic graph. ("Tree" (1998-11-12) via FOLDOC 30jan2010.) Other sort methods besides tree sort include quicksort, bubble sort, heap sort, and insertion sort. ("Sort" (1997-02-12) via FOLDOC, 30th January 2010.) This pattern can be seen almost everywhere that data are represented as discrete notional objects: for example, the directory trees contained within the file systema of your personal computer, the technology/skill trees that are likely to present themselves in your favorite video game, and in any computer program that maintains the logical order of a data set as new data are added. These aren't necessarily treelike data structures; but, because the perceived "shape" of the data is a tree, they're probably similar if coded in object-oriented language. I imagine a file system as "what an object even is;" although a computer program is volatile, whereas files are nonvolatile, the idea is much the same. See also: object-oriented programming, procedural vs. functional languages, file systems, {non,}volatile memory such as RAM and EEPROM, sort algorithms. Of course, treelike structures aren't always the optimum schematic to represent a hierarchical assortment of data; definitively, like all other object-oriented designs, they're mere abstractions employed to delineate pieces of a contiguous unidimensional memory space (the Turing model of a logic machine considers RAM to be just a big empty pair of set brackets; data are populated & operated-upon arbitrarily, but the container is merely a set) and to signify correlation. An object is a collection of related data; which comprise a several datum. See also: pointers, heap memory, set theory, discrete math, and Boolean logic. Â¶ The following (til the next pilcrow) is nearly a verbatim excerpt from FOLDOC. The data stored in a tree is processed by traversal. The algorithm begins at root node, transforms or collects or computes against the data, and then repeats itself for the root's child-nodes ("branches") in some specific order. Three common traversal orders are pre-order, post-order, and in-order traversal. For the binary tree illustrated below: T / \ I S / \ D E A pre-order traversal visits the nodes in the order T I D E S. A post-order traversal visits them in the order D E I S T. An in-order traversal visits them in the order D I E T S. Â¶ "Traversal" (2001-10-01) via FOLDOC, ed. 30th January 2010. See also: recursion, the call stack (subroutine invocation), digraph traversal. To encode a tree walk via recursive algorithm is straightforward, and is how the concept of data set traversal is introduced to novitiate computer programmers. (Well, after they've learned how to loop over an array with "for.") Succinctly: function put (pNode, value) { if (pNode.isEmpty()) { pNode.datum = value; } else if (value < pNode.datum) { put(pNode.bLeft, value); } else if (value > pNode.datum) { put(pNode.bRight, value); } } // Ordered insertion. function tell (pNode, value) { if (value < pNode.datum) { return tell(pNode.bLeft, value); } else if (value > pNode.datum) { return tell(pNode.bRight, value); } else if (pNode.isEmpty()) { return NULL; } return pNode; } // Seek pointer to inserted. _Any_ recursive algorithm can be reduced to an iterative algorithm, provided you can use variable-length arrays to simulate the function of the call stack, which stores the arguments to the subroutine you invoked and the address to restore to the instruction pointer when the subroutine returns. That is, the call stack is like bookmarks or tabbed indices to tell the routine where it was before a jump. Replace the "instruction pointer and arguments" model of a stack frame with any constant-width data set that remembers what you were doing before you jumped to the next node in the digraph, and, naturally, you can remember the same stuff as if you had utilized the convenient paradigm that is recursivity. (Stack frames don't really all have to be the same size, but a definite frame width spares you from doing yet another algorithm to parse frames. See: network protocol stacks.) The "stuff you remember" is the state of the finite state automaton who tends to the mechanism whereby the machine knows which instruction to execute next. Recursion provides this automaton "for free," because it crops up so frequently; but, for whatever reason (such as the 3000-call recursion limit in Firefox 3.6), you might want to write a tree sort without using recursion at all. Gentlemen, behold... corm = GenProtoTok( Object, function () { this.tree = new this.Hop(); return this; }, "Hopper", undefined, "locus", undefined, "seek", function (u_val) { while (this.locus[2] != undefined) { if (u_val > this.locus[2]) { this.locus = this.hop(1); } else if (u_val == this.locus[2]) { return false; } else { this.locus = this.hop(0); } // u < loc[2] || u == undef } return true; }, // end function Hopper::seek "tellSorted", function () { if (this.tree == undefined) { return undefined; } var evaluation = new Array(); for (var orca = new Array(this.tree), did = new Array(false); orca.length>0; ) { this.locus = orca.pop(); if (did.pop()) { evaluation.push(this.locus[2]); if (this.locus[1] != undefined) { orca.push(this.locus[1]); did.push(false); } } else { orca.push(this.locus); did.push(true); if (this.locus[0] != undefined) { orca.push(this.locus[0]); did.push(false); } } } return evaluation; }, // end function Hopper::tellSorted "hop", function (index) { if (this.locus[index]==undefined) { this.locus[index] = new this.Hop(); } return this.locus[index]; }, // end function Hopper::hop "addUnique", function (value) { this.locus = this.tree; if (this.seek(value)) { this.locus[2] = value; return true; } return false; }, // end function Hopper::addUnique "Hop", GenPrototype(Array, new Array()) ); ... corm! Here is how corm works: it's an Array retrofitted with a binary tree algorithm. Each node of the tree is an Array whose members, at these indices, signify: 0. Left-hand ("less-than") branch pointer. 1. Right-hand ("greater-than") branch pointer. 2. Value stored in the node. Values are added via the corm object's addUnique method, which resets a pointer to the algorithm's location in the tree and then seeks a place to put the datum. Seeking causes a node to be created, if no node yet contains the datum; so, the corm::seek method's name is misleading, but seeking is exactly what it does. In-order traversal is executed by corm::tellSorted which returns the sorted set. Recursion is simulated using a state stack whose frames each contain a pointer to the "previous" node and a boolean value that signifies whether its left child has been visited. Here is the main loop, step-by-step, in natural English: for (var orca = new Array(this.tree), did = new Array(false); orca.length>0; ) { "Given the stack, which I consider until it is exhausted..." this.locus = orca.pop(); "I am here." -^ if (did.pop()) { "If I did the left branch already," evaluation.push(this.locus[2]); "then this value occurs at this location in the ordered set;" if (this.locus[1] != undefined) { "if the right branch exists," orca.push(this.locus[1]); "visit the right child on the next loop iteration" did.push(false); "(and, naturally, I haven't visited the right child's left child yet)" } "." } else { "If I haven't done the left branch already," orca.push(this.locus); "then I have to visit this node again when I come back" did.push(true); "(except I shall have visited the left child by then);" if (this.locus[0] != undefined) { "if the left branch exists," orca.push(this.locus[0]); "visit the left child on the next loop iteration" did.push(false); "(and, naturally, I haven't visited the left child's left child yet)" } "." } "... I consume pointers and bools, doing all that there stuff" } "." And that is how to do everything I did with the Hopper data structure (which is here renamed corm, because I like corm) in quadrare-lexema.js. Full disclosure: whereas; although I do put on women's clothing; and although indeed I sleep all night and work all day; and, in addition, despite that I have been known, of an occasion: to eat eat my lunch, go to the lavatory, pick wild flowers, hang around in bars, and want to be a girlie; my Wednesdays have not historically been known to involve shopping or buttered scones, I don't know how to press a flower, I have neither suspenders nor heels nor a bra (but thanks for offering), and am not, in fact, a lumberjack.

Advertisements