### What is the length of a binary tree?

• 10 Replies
• 391 Views

0 Members and 1 Guest are viewing this topic.

#### TGlad

• •     • Posts: 78 #### What is the length of a binary tree?

« on: November 28, 2018, 05:17:22 AM »
I have a maths question.
Let's say we have a binary tree like the one in the picture. The branch lengths scale by 0.5 each branching, so the total length of the branches is infinity.
The leaf points are a fractal dust with dimension 1, so the fractal dimension of the whole tree should be just 1.

But if the branch length is infinity, how do we compare the size of different similar fractal trees? If we extract two random pieces of the tree, how do we know which contains more of the tree?

Almost all the 'mass' of this tree seems to be located at the leaves, but the leaves don't have a larger dimensionality than the branches. #### hobold #### Re: What is the length of a binary tree?

« Reply #1 on: November 28, 2018, 12:00:45 PM »
Isn't this the question that led to the definition of fractal dimension? I mean, euclidian length cannot describe the "size" of this tree's branches. And while the set of all leaves appears to be one dimensional, it does not have a clearly defined length, does it?

So maybe the fractal dimension of the tree, or the subset of branches, or the subset of leaves, is the relevant measure?

#### TGlad

• •     • Posts: 78 #### Re: What is the length of a binary tree?

« Reply #2 on: November 28, 2018, 12:45:53 PM »
It seems a very sneaky one.
The leaves have dimension 1 and you could call it a 'length' for the leaves, but I find it better to use the adjective from its topological dimension, so the 'number of' leaves has dimension 1. But to be formal it is the Hausdorff measure.

It seems like the geometry is such that the amount of points in the branches is basically 0 (has measure 0?) compared to the leaves.

So to compare the size of two such trees you just compare the Hausdorff measure of their leaves. If this measure is identical then you compare the total lengths of the branches.

It is a bit weird, but I think that has to be the right answer.

#### lkmitch #### Re: What is the length of a binary tree?

« Reply #3 on: November 28, 2018, 04:59:15 PM »
Perhaps I'm misunderstanding the original question, but the length of any branch is not infinite just because the branch is made up of an infinity of "twigs." In the particular example, scaling by 0.5 gives a convergent series so the length would be 1 + 0.5 + 0.25 + 0.125 + ... = 2. Or did I miss something?

#### claude #### Re: What is the length of a binary tree?

« Reply #4 on: November 28, 2018, 07:11:34 PM »
the length of a single branch from root to tip is 2 as you observe, but the number of branches in the whole tree goes up so for the total length of all branches you get 1 + 2 * 0.5 + 4 * 0.25 + ... = 1 + 1 + 1 + ... -> infty

#### fractower #### Re: What is the length of a binary tree?

« Reply #5 on: November 28, 2018, 07:33:38 PM »
How about comparing trees based on the ratio of growth for each branching. In the case described each branching adds a total length of 1 so the ratio is just 1. If the length was scaled by 0.6 however the growth would be 2*0.6=1.2.

By this measure a the 0.5 binary tree and and 0.25 quad tree are equivalent.

It is kind of trivial but does some work.

#### claude #### Re: What is the length of a binary tree?

« Reply #6 on: November 28, 2018, 07:45:11 PM »
It seems like the geometry is such that the amount of points in the branches is basically 0 (has measure 0?) compared to the leaves.

The 1-dimensional Hausdorff measure of the branches is infinite (assuming it coincides with the intuitive notion of length?).  So the proportion in any given branch is 0 (a finite length divided by the infinite total).

I have not done the calculation of the 1-dimensional Hausdorff measure of the leaves, which may be finite (in which case the branches dominate) or infinite (in which case we don't know without more information).

#### TGlad

• •     • Posts: 78 #### Re: What is the length of a binary tree?

« Reply #7 on: November 29, 2018, 05:39:43 AM »
For any pixel width w the number of pixels covered by the set of leaf points is about 1/w when the full tree height is about 1.
So the fractal measure (in the box counting method) is about 1, but the measure of the tree branches is infinite.

This would suggest that the leaf points are an infinitely small part of the fractal. I think that strictly speaking this is true.

However if you look at how much of the fractal is within some tiny distance of the leaf points, then it turns out that an infinite length of branches are within this tiny distance, and only a finite length are outside this distance. So the exact opposite is the case - the parts of the tree away from the leaves contribute basically nothing to the size of the tree.

Speaking practically, the Hausdorff measure of the leaves seems to represent the size of the set, this is what you'd use to compare the size of two subsets of the tree.

But mathematically it is still rather confounding... all the mass is near the leaves but yet only an infinitely small part of the mass is at the leaves.

#### fractower #### Re: What is the length of a binary tree?

« Reply #8 on: November 30, 2018, 01:52:39 AM »
How are you defining a leaf if the branching goes on forever?

#### TGlad

• •     • Posts: 78 #### Re: What is the length of a binary tree?

« Reply #9 on: November 30, 2018, 02:23:11 AM »
The leaves are the limit of the sequence of smaller branches.
It seems that the mass of the tree is less than a finite distance from the leaf points, but is not just the leaf points.

#### fractower #### Re: What is the length of a binary tree?

« Reply #10 on: November 30, 2018, 07:19:01 AM »
Rather than drawing the tree as recursive "Y"s draw it as recursive "T"s. The first T is one unit high with two half size "T"s at either end of the cross bar. Rinse repeat. With this representation a horizontal line will cross only "T"s at one bifurcation level.

The total height of all "T"s cut by the line is 1.
A line at 2 will not cut any "T"s.
A line at 2 minus an infinitesimal amount will cut a countably infinite number of "T"s (dimension 0). The sum of heights will still be 1.

Any subset of the tree would obey the same rules except it would have a fractional height sum constant.

### Similar Topics ###### Binary Beast--"Mark of the Binary Beast"--3D Fractals and Music

Started by Paigan0 on Fractal movie gallery

3 Replies
171 Views August 16, 2019, 11:03:15 PM
by gerson ###### reading off external angles from binary decomposition images

Started by claude on Fractal Mathematics And New Theories

4 Replies
232 Views May 12, 2019, 06:18:19 PM ###### Ghosts Tree

Started by utak3r on Fractal Image Gallery

0 Replies
118 Views March 09, 2018, 10:02:16 PM
by utak3r ###### Snail Tree

Started by AlexH on Fractal Image Gallery

1 Replies
120 Views October 07, 2018, 01:37:11 AM
by AlexH ###### Lux Glynn Tree

Started by Lux on Fractal Image Gallery

0 Replies
210 Views September 20, 2017, 07:49:37 PM
by Lux