Agnes Scott College
Larry Riddle, Agnes Scott College

Symmetric Binary Tree

Description


 
 

Construction
Animation
To construct a symmetric binary tree, choose an angle θ with 0° < θ < 180° and a scaling factor r with 0 < r < 1. Start with a vertical line segment (the trunk) of length 1. The trunk splits into two branches at the top that each form an angle of θ with the linear extension of the trunk, one to the left and one to the right. Each branch has length r. Each of these two branches forms the trunk of a subtree that splits into two more branches following the same rule. The angle is again θ and the length of each of the four new branches is r2. See the illustration below where θ = 60° and r = 0.65.

construction

The symmetric binary tree is obtained by continuing to add more branches ad infinitum, using the angle θ and scaling factor r for each set of new branch segments.

Here are some examples of symmetric binary trees through 12 iterations.

SBT-0.7-30 SBT-0.6-45
θ=30°, r=0.7 θ=45°, r=0.57
SBT-0.7-120 SBT-150-0.8
θ=120°, r=0.7 θ=150°, r=0.8

The limit points of the branches in a binary tree are called the branch tips.

Iterated
Function
System

The two branches are obtained from the trunk by scaling by a factor of r, rotating counterclockwise by θ (left) and −θ (right), then translating to the top of the trunk. The third function needed is the identity. This keeps the branches already drawn in their current locations while the first two functions add the new branches.
\({f_1}({\mathbf{x}}) = \left[ {\begin{array}{*{20}{c}} {r \cos (\theta )} & { - r\sin (\theta )} \\ {r\sin (\theta )} & {{{r \cos }}(\theta )} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{*{20}{c}} 0 \\ 1 \\ \end{array} } \right]\)
 
   scale by r, rotate by θ°
 
\({f_2}({\mathbf{x}}) = \left[ {\begin{array}{*{20}{c}} {r \cos (\theta )} & { r\sin (\theta )} \\ {-r\sin (\theta )} & {{{r \cos }}(\theta )} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{*{20}{c}} 0 \\ 1 \\ \end{array} } \right]\)
 
   scale by r, rotate by −θ°
 
\({f_3}({\bf{x}}) = \left[ {\begin{array}{*{20}{c}} { 1} & {0} \\ { 0} & { 1} \\ \end{array}} \right]{\bf{x}} \)  

Note that function 3 in this iterated function system is not a contractive mapping. Therefore the theory of contractive iterated function systems cannot necessarily be applied here. However, in this case the iterates of an initial set under this iterated function system do converge to a limit set, but the limit will depend on the initial set [Proof]. This type of iterated function system is often called an IFS with condensation.

thicktrunk    initialsquare
45° tree
thick rectangle as initial set
   45° tree
unit square as initial set

If only the first two functions are used as the iterated function system, the system will be contractive and all initial sets will converge to the branch tips. Both of the trees above have the same branch tips shown below.

45degbranchtips

Branch
Addresses

The paths of a symmetric binary tree can be addressed by finite strings of the letters L and R, with L corresponding to branching to the left and R corresponding to branching to the right. For example, the image below shows the ends of the paths corresponding to the addresses L, R, LL, LR, RL, and RR. The red branches are drawn to the left and the blue branches are drawn to the right.

address2steps

 
 
 
 

The next image shows the first 7 iterations in the construction of a symmetric binary tree. Click on the buttons to the right to see the path corresponding to the button's address.

SBT-0.64044-70

The branch tips are obtained as infinite sequences of L and R. For example, the sequence (RL) = RLRLRL... would be a path alternating right and left branches. Notice the symmetry with the address (LR). The address R corresponds to an infinite spiral of right branches.

70-branchtips3

Self-Contacting
Trees

If the scaling factor r is too small, the branches of the tree will be self-avoiding, while if r is too large the branches will overlap. Mandelbrot and Frame showed that for each angle θ, there is a unique scaling factor rsc such that the symmetric binary tree with that θ and r will be self-contacting, that is, branches may touch at a single point but may not cross. In this case, the branch tips of left-side branches will coincide with branch tips of some right-side branches, but no branch tip will coincide with any non-tip point of the tree. Three examples are shown below for θ=60°.
SBT-60-self-avoiding SBT-60-self-contacting SBT-60-self-overlapping
Self-avoiding
r = 0.58
[Enlarge]
Self-contacting
r = 0.61803
[Enlarge]
Self-overlapping
r = 0.65
[Enlarge]
 
 
[Details]
For 0 < θ ≤ 90°, let Nθ be the smallest integer such that Nθθ ≥ 90°. On this interval, the value of rsc is the unique solution to the equation \[ r^2\cdot \left( {\frac{r^{N_\theta+1}\cos((N_\theta-1)\theta)-r^{N_\theta}\cos(N_\theta\theta)-r\cos(\theta)+1}{r^2+1-2r\cos(\theta)}} \right) = \frac{1}{2}. \] For 90° ≤ θ < 135°, we have \[ r_\text{sc} = \frac{1}{\sqrt{2-3\cos^2(\theta)}-\cos(\theta)} \] and for 135° ≤ θ < 180°, \[ r_\text{sc} = -\frac{1}{2\cos(\theta)} \] Here is a graph of rsc as a function of θ. We see that \(\frac{1}{2} < r_\text{sc} ≤ \frac{1}{\sqrt{2}}\), with the maximum value occurring at θ = 90° and θ = 135°. The dashed lines occur at 135° and 90°/N for N = 1, 2, 3, 4, 5, 6. There should also be many more dashed lines at θ = 90°/N for N > 6 but they would all begin to run together as N gets larger. These values reflect the change in Nθ in the equation for rsc for 0° < θ < 90°.

self-contacting-graph

See a catalog of all self-contacting symmetric binary trees for integer angles from 1° to 179° by clicking on the Play button below. There will be a slight pause at θ=90° (tree is a filled in rectangle) and at θ=135° (tree is a filled in triangle) corresponding to the two transition values in the graph of rsc above.

selfcontactingAnimation3Frame1
 

Similarity
Dimension
(Branch Tips)

When r ≤ rsc, the branch tips form a fractal that is self-similar with 2 non-overlapping copies of itself, each scaled by the factor r < 1. Therefore the similarity dimension, d, of the attractor of the IFS corresponding to the branch tips is the solution to \[ \sum_{k=1}^2 r^d = 1 \quad \Rightarrow \quad d = \frac{\log(1/2)}{\log(r)} = -\frac{\log(2)}{\log(r)} \]

 
 
 
 

Click on the buttons to the left for some examples of branch tips of self-contracting trees and their dimensions.

dim30

Here is a graph of the similarity dimension of the branch tips of the self-contacting trees (r = rsc).

sc-dimension-graph

Symmetric
Binary Tree
Shape

 
 
 
[Details]
Let the tree be defined by the angle θ and scaling factor r. We will take the base of the tree to be at the origin and the initial vertical trunk to be of length 1. By the "top" of the tree we will mean the top of the branch tips, that is, the largest y-coordinate of the branch tips. The "bottom" of the tree will mean the bottom of the branch tips, that is, the smallest y-coordinate of the branch tips. The "right side" of the tree will be the largest x-coordinate of the branch tips (and by symmetry, the left side will be the negative of this x-coordinate.) For most symmetric binary trees, the top of the tree will correspond to the y-coordinate of the branch tip of the path (LR), or equivalently (RL) = R(LR); the right side will correspond to the x-coordinate of the branch tip of the path Rk(LR) where k is the smallest integer with kθ ≥ 90°; and the bottom will correspond to the y-coordinate of the branch tip of the path Rk(LR) where k is the smallest integer with kθ ≥ 180°.

treedimensions
θ = 35°, r = 0.6
blue = right branch, red = left branch
top = 2.6539, side = 1.51964, bottom = 1.15588

As observed by Don West for the top of the tree, however, the branch tip for (LR) or (RL) may not always have the largest y-coordinate. Indeed, for every θ that is not of the form 360°/n for some integer n, there will be a critical value rT such that if r > rT, then the branch tip for the path Rk(LR), or equivalently, Lk(RL), will have a greater y-coordinate, where k is the smallest integer such that kθ ≥ 360°.These scaling factors will be fairly large, however, and the resulting binary trees will have massively overlapping branches as shown in the example below.

SBT-150-0.8twopaths2
θ = 150°, r = 0.8

Similar exceptions hold for the bottom and sides of a binary tree for certain intervals of θ. None of these exceptions will happen, however, for self-contacting trees or when r < rsc. For these trees, the top, bottom, and sides will always be determined by the paths described in the first paragraph. Click for the mathematical details.

Special
Properties

Golden Symmetric Binary Trees

Tara Taylor has studied the four self-contacting symmetric binary trees for which the scaling factor is equal to \(\frac{1}{\phi}\), where \(\phi = \frac{1+\sqrt{5}}{2}\) is the golden ratio. These four trees correspond to the angles 60°, 108°, 120°, and 144° [Proof]. For details about many of the special geometric properties of these trees, see her Ph.D. thesis and other publications.
golden60
θ = 60°
golden108
θ = 108°
golden120
θ = 120°
golden144
θ = 144°
Among the results she has shown is how these trees relate to triangles, pentagons, and hexagons.
triangleSmall HexagonSmall  
3 copies of 60° tree
fit inside an
equilateral triangle
6 copes of 60° tree
fit inside a
hexagon
[Details]

 

insidePentagonSmall pentagramSmall  
5 copes of 108° tree
fit inside a
pentagon
5 copes of 108° tree
fit inside a
pentagram
[Details]

 

triangleSmall hexagonSmall  
3 copes of 120° tree
fit inside an
equilateral triangle
5 copes of 120° tree
fit inside a
hexagon
[Details]

 

snowflakeSm    
5 copes of 144° tree
make a
Golden Koch Snowflake
  [Details]
 
 
 

Lévy
Animation

Lévy Symmetric Binary Tree

The branch tips for a symmetric binary tree with θ = 45° and \(r = \frac{1}{\sqrt{2}}\) form a fractal that is the same as the Lévy Dragon.
SBT45Levy
Symmetric Binary Tree
Levy
Lévy Dragon
 
 
 

Construction
Animation
If four copies of a Lévy symmetric binary tree are placed at right angles, the branch tips will form the outside Lévy tapestry.

LevyTapestry
[Back Stitch Version, 12.5" x 12.5" on 18 count canvas]

Variations

If the three functions in the IFS for the self-contacting 45° symmetric binary tree are composed with the four elements of the Z4 cyclic symmetry group (rotations by 90°), the result will be a new iterated function system of 12 functions that exhibits Z4 symmetry (and in this case also reflective symmetry across horizontal, vertical, and diagonal lines through the center (D4 dihedral group symmetry) because of the symmetry of the base binary tree). In the image below, the random algorithm was used to draw 10 million points in the attractor for this IFS. The image was colored using pixel counting in which the colors represent how many times a particular pixel in the image was plotted (represented by the gradient on the right).
Z4image
[Enlarge]
 
   pixelcountinggradient

 
 

References

  1. Barnsley, Michael and D.P Hardin. "A Mandelbrot set whose boundary is piecewise smooth," Transactions of the American Mathematical Society, Vol. 315, No. 2 (1989), 641-658.
  2. Mandelbrot, Benoit and Michael Frame. "The canopy and shortest path of a self-contacting fractal tree," The Mathematical Intelligencer, vol. 21, No. 2 (1999), 18-27.
  3. Mandelbrot, Benoit and Michael Frame. Geometry of Self-Contacting Binary Fractal Trees website.
  4. Pagon, Dusan. "Self-Similar Planar Fractals Based on Branching Trees and Bushes," Progress of Theoretical Physics Supplement, No. 150, 176-187.
  5. Pons, Bernat Espigulé. Unfolding Symmetric Fractal Trees, Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture, Edited by George Hart and Reza Sarhangi, pp295-302.
  6. Pons, Bernat Espigulé. Adventures into the Mathematical Forest of Fractal Trees, Wolfram Blog, May 22, 2014.
  7. Pons, Bernat Espigulé. Fractal Trees website
  8. Taylor, Tara. Computational Topology and Fractal Trees, Ph.D. Thesis, Dalhousie University (2005).
  9. Taylor, Tara. "Finding Gold in the Forest: Self-contacting Symmetric Binary Fractal Trees and the Golden Ratio".
  10. Taylor, Tara. "A New Classification of Non-overlapping Symmetric Binary Fractal Trees Using Epsilon Hulls", Fractals, Vol. 17, No. 3 (2009), 365-384.
  11. Taylor, Tara. "Excursions through a Forest of Golden Fractal Trees", in The Beauty of Fractals: 6 Different Views, eds. Denny Gulick and Jon Scott, Mathematical Association of America, 2010. [Excerpts available at Google Books]
  12. West, Don. "Self-Contacting Fractal Trees, Comments on and Mathematical Details for an article by Mandelbrot and Frame." Website http://web.archive.org/web/20120313124012/http://faculty.plattsburgh.edu/don.west/trees/index.htm.
  13. Field, Michael and Martin Golubitsky. Symmetry in Chaos: A Search for Pattern in Mathematics, Art, and Nature (2nd Edition), SIAM, 2009. [See Preview at Google Books. Chapter 7 is on Symmetric Fractals.]
  14. Geom-e-tree by John Miller, Tree-Drawing App for iPad and iPhone. Can draw symmetric binary trees among many other possibilities.