Блог пользователя biximo

Proving certain binary tree property
Автор biximo, история, 10 месяцев назад, По-английски

I recently came across a claim about binary trees that I was unable to prove. Given a binary tree, $$$\sum{|child_l|\times |child_r| } = O(N^2)$$$

Could someone provide proof and/or a way to intuitively explain this?

  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

»
10 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

Actually, I guess I have some kind of intuitive explanation behind this. If we imagine that each node "contributes" to the $$$N^2$$$ count, we can observe that no matter how the tree is structured, the total number that it contributes will be maximum $$$N$$$, since once two subtrees "merge" they will no longer multiply within themselves to count towards the $$$N^2$$$. So, since each node will add a maximum of $$$N$$$ towards the count, the total number will add up to maximum $$$N^2$$$. I think I am more interested in formal proof.

→ Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Another way to think about it is that any pair of nodes $$$(u, v)$$$ is considered at most (exactly, in fact) once and this happens at their LCA.

→ Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Suppose we want to count number of pairs $$$(u, v)$$$ such that $$$LCA(u, v) = i$$$. If children of $$$i$$$ are $$$l$$$ and $$$r$$$, then the number is equal of $$$\text{SubtreeSize}(l) \times \text{SubtreeSize}(r)$$$ if we consider pairs $$$(u, v)$$$ and $$$(v, u)$$$ equal. Therefore the sum you mentioned is equal to total number of pairs of vertices in the tree (number of subsets of size two).

→ Ответить
  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Total number of pairs except the ones $$$\{u,v\}$$$ where $$$u$$$ is an ancestor of $$$v$$$ since $$$LCA(u,v) = u$$$ but this is not counted in $$$\text{SubtreeSize} (l_u) \times \text{SubtreeSize} (r_u)$$$

    → Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

The given sum is same as the union of cross products of sets of vertoces of left and right subtrees. Now we can see that each unordered pair of vertices $$$(u,v)$$$ occurs atmost once in the above union. This also gives an upper bound of $$$N*(N-1)/2$$$

→ Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

https://codeforces.net/blog/entry/124538?#comment-1105664

→ Ответить