2
$\begingroup$

While working on a math problem the following tree structure came up:

    o
     \
      o
     /
    o
   / \
  o   o
 / \ /

It is a binary tree with the following constraints:

  • all nodes except the root have a left child
  • all left-child nodes have a right child
  • none of the right-child nodes have a right-child

It also has the following emerging properties:

  • The nodes are indexable:
    • the root node has index 0
    • for a given node indexed n, its left child has index 2n and right child n + 1
    0
     \
      1
     /
    2
   / \
  4   3
 / \ /
8  5 6  
  • the number of edges at each level matches the fibonacci sequence:
    o
     \    1
      o
     /    1
    o
   / \    2
  o   o
 / \ /    3 // Then will be 5, 8 etc... 

I would like to know more about this specific kind of tree, for example other emerging properties, what kind of problem it can help to solve or how is it typically used, but despite this seeming like a basic data structure I can't find any information on it. Searching for "fibonacci restricted tree" yields unrelated results such as Fibonacci Heaps.

Questions:

  • Is there an accepted name for this specific kind of binary tree?
  • What are some examples of usage of this kind of tree in computer science?
$\endgroup$
7
  • $\begingroup$ The index is not continuous ($n$ doubles on every level, but a level does not hold twice as many nodes). You could as well number the nodes as $F_l+k$ on level $l$. $\endgroup$ Feb 4 at 15:49
  • $\begingroup$ (@YvesDaoust: sure? From a quick "mental labelling", low labels may end up pretty for down paths alternating between left&right.) $\endgroup$
    – greybeard
    Feb 4 at 16:17
  • $\begingroup$ "the number of edges at each level matches the fibonacci sequence:" That doesn't sound too hard to prove, but did you actually prove it? $\endgroup$
    – Stef
    Feb 5 at 11:38
  • $\begingroup$ @Stef By induction on the number of right and left children in each level. These form two successive Fibonacci numbers. $\endgroup$ Feb 5 at 21:12
  • $\begingroup$ @HendrikJan Are you telling me that the OP proved it by induction? $\endgroup$
    – Stef
    Feb 5 at 21:47

1 Answer 1

3
$\begingroup$

Just a quick association to your tree structures and Fibonacci numbers.

The numbering scheme and hence the tree structure seems related to the concept of exponentiation by squaring. The power of a number (or matrix) can be recursively computed as follows.

  • $A^{2n} = A^n * A^n $
  • $A^{2n+1} = A * A^{2n} $

In this formula you recognize the left and right branches of your trees.

Computer scientists usually learn this when they see the Fibonacci sequence in their programming course. Straightforward recursion of the Fibonacci numbers leads to an exponential number of recursive calls, much worse that computing the numbers iteratively from the bottom. The Fibonacci numbers can be computed using matrix squaring using the matrices $\left(\begin{array}{cc}1 & 1 \\ 1 & 0 \end{array}\right)^n = \left(\begin{array}{cc}F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{array}\right)$.

Fibonacci / exponentiation by squaring

The depth of the nodes is sequence A014701 in the On-Line Encyclopedia of Integer Sequences, "Number of multiplications to compute n-th power by the Chandah-sutra method".

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.