1
$\begingroup$

Consider a binary tree constructed as the following. Given a node with a some value $x$, I construct two children nodes each having value $l(x)$ and $r(x)$ respectively. I repeat the same on the children nodes, and so on... After $n$ steps, there are total $\sum_{i=0}^n 2^i$ children nodes.

Depending on the choice of $x$, $l(\cdot)$, $r(\cdot)$, one of the children nodes may or may not have the value $x$, same as the common ancestor node. If there is such a node, then that guarantees that there are infinitely many nodes of the same value, since the tree becomes self-similar.

I am wondering if there is an established way to measure the degree of self-similarity of such a tree. As we construct the tree, we might find the coincident node earlier for some choice of $(x, l, r)$ than another. The tree that has the coincident node in earlier iteration would have "higher" self-similarity, since the self-similarity occurs more frequently.

I can come up with some measure that allows me to compare the self-similarity, but I would like to know if there is an established and maybe general method. Initially it seemed like "fractal dimension" fits the bill, but I am not sure it makes sense (I am not familiar with fractals).

Improve this question
$\endgroup$
1
  • $\begingroup$ Are you calling the initial node a child node? If not, then shouldn't the sum begin with i = 1 ? Also, despite knowing a little about trees, I am not familiar with the concept of the "value" of a node of a tree. Can you at least state what set these "values" are members of? Finally, I do not understand why the existence of a non-initial node with the same value as the initial node implies there are infinitely many of them. (You don't seem to say how child nodes might depend on their parent.) $\endgroup$
    – Daniel Asimov
    Commented Jul 4, 2023 at 4:26

0

Reset to default

You must log in to answer this question.