You are here
Homeweightbalanced binary trees are ultrametric
Primary tabs
weightbalanced binary trees are ultrametric
Let $X$ be the set of leaf nodes in a weightbalanced binary tree. Let the distance between leaf nodes be identified with the weighted path length between them. We will show that this distance metric on $X$ is ultrametric.
Before we begin, let the join of any two nodes $x,y$, denoted $x\lor y$, be defined as the node $z$ which is the most immediate common ancestor of $x$ and $y$ (that is, the common ancestor which is farthest from the root). Also, we are using weightbalanced in the sense that

the weighted path length from the root to each leaf node is equal, and

each subtree is weightbalanced, too.
Lemma: two properties of weightbalanced trees
Because the tree is weightbalanced, the distances between any node and each of the leaf node descendents of that node are equal. So, for any leaf nodes $x,y$,
$d(x,x\lor y)=d(y,x\lor y)$  (1) 
Hence,
$d(x,y)=d(x,x\lor y)+d(y,x\lor y)=2*d(x,x\lor y)$  (2) 
Back to the main proof
We will now show that the ultrametric three point condition holds for any three leaf nodes in a weightbalanced binary tree.
Consider any three points $a,b,c$ in a weightbalanced binary tree. If there exists a renaming of $a,b,c$ such that $d(a,b)\leq d(b,c)=d(a,c)$, then the three point condition holds. Now assume this is not the case. Without loss of generality, assume that $d(a,b)<d(a,c)$.
Applying Eqn. 2,
$\displaystyle 2*d(a,a\lor b)$  $\displaystyle<$  $\displaystyle 2*d(a,a\lor c)$  
$\displaystyle d(a,a\lor b)$  $\displaystyle<$  $\displaystyle d(a,a\lor c)$ 
Note that both $a\lor b$ and $a\lor c$ are ancestors of $a$. Hence, $a\lor c$ is a more distant ancestor of $a$ and so $a\lor c$ must be an ancestor of $a\lor b$.
Now, consider the path between $b$ and $c$. One way to get from $b$ to $c$ is to go from $b$ up to $a\lor b$, then up to $a\lor c$, and then down to $c$. Since this is a tree, this is the only path. The highest node in this path (the ancestor of both b and c) was $a\lor c$, so the distance $d(b,c)=2*d(b,a\lor c)$.
But by Eqn. 1 and Eqn. 2 (noting that $b$ is a descendent of $a\lor c$), we have
$d(b,c)=2*d(b,a\lor c)=2*d(a,a\lor c)=d(a,c)$ 
To summarize, we have $d(a,b)\leq d(b,c)=d(a,c)$, which is the desired ultrametric three point condition. So we are done.
Note that this means that, if $a,b$ are leaf nodes, and you are at a node outside the subtree under $a\lor b$, then $d(\textrm{you},a)=d(\textrm{you},b)$. In other words, (from the point of view of distance between you and them,) the structure of any subtree that is not your own doesn’t matter to you. This is expressed in the three point condition as “if two points are closer to each other than they are to you, then their distance to you is equal”.
(above, we have only proved this if you are at a leaf node, but it works for any node which is outside the subtree under $a\lor b$, because the paths to $a$ and $b$ must both pass through $a\lor b$).
Mathematics Subject Classification
05C05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new question: numerical method (implicit) for nonlinear pde by roozbe
new question: Harshad Number by pspss
Sep 14
new problem: Geometry by parag
Aug 24
new question: Scheduling Algorithm by ncovella
new question: Scheduling Algorithm by ncovella