The Binary Tree

The idea of “discrete” can be modeled by a binary tree…by the parent/child relationship. The space between branches are the “holes” in the structure or the two parts separated by a boundary (“branches” in a binary tree: the two “children” of the one “parent”). The idea starts with a blank tree devoid of labels.

Blank Binary Tree Structure

We next consider what labels we want to apply to the vertices and by extension to the “leaves” of the tree…the limits of an infinite tree….the points on the horizon. The most basic labels are those given by counting in binary starting at 1 on the right side (for the moment think of [e] as being 0), then labeling the left side by complementing the labels from the right side. The labels (count) on the right and the complement on the left have distinct roles in the structure of the tree and in the resulting set of binary strings.

Labels on the left half of a row are just the count of all the vertices on the right side of the tree up to but not including the vertices on the right half of the row. We can think of the labels on the left of a row as the “history” of the labels to its right. As such the left labels are therefore static, or fixed…not the “wave front” (the present), rather its “echo” or “the return of the reverse wave”, its record…the past. We can also think of the left half of a row as compressing that 2D history into 1D…a 2D table “linearized” via concatenation into a 1D “list”…a sort of “space filling curve” relation. The right half is active, the left half is a fixed list of the “growth” that has taken place on the right. To stretch a metaphor: the left is the rings of the tree, the right is where growth takes place. See below.

Next let’s take note of the fact that if we assign 0 to the left branch/child of a parent and 1 to the right branch/child we see that the labels are built up as strings by appending moves as 0 or 1 to the right end of the strings in the previous row. The labels assigned to vertices are records of paths that start at [e], records of left/right moves through the tree that pass through that vertex.

The lead 0 is not shown for labels on the right

The result is the basic binary tree with the usual (standard) labels. This tree will be the basis for describing relationships between sets of labels for a tree of binary structure. It is the starting point for comparisons between sets of labels attached to the parent/child tree with exactly two children per parent. It will be the basis for “compare and contrast”.

Published by Bob H

worker bee

Leave a comment