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?

# | User | Rating |
---|---|---|

1 | jiangly | 3678 |

2 | Benq | 3602 |

3 | ecnerwala | 3542 |

4 | maroonrk | 3541 |

5 | cnnfls_csy | 3540 |

6 | orzdevinwang | 3493 |

7 | inaFSTream | 3478 |

8 | Um_nik | 3430 |

9 | Geothermal | 3409 |

9 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 164 |

3 | TheScrasse | 161 |

3 | SecondThread | 161 |

3 | awoo | 161 |

6 | nor | 159 |

7 | maroonrk | 158 |

8 | Um_nik | 156 |

9 | BledDest | 145 |

9 | Geothermal | 145 |

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?

I recently came across a very interesting Data Structure, that to me, was completely revolutionary in how I view data structures. That is, Implicit Treaps. But on to my question: Now that I'm pretty familiar with the implementation of Treaps and its applications, should I learn Splay Trees (I will learn it regardless eventually, but I have a competition coming up and time is limited)? To narrow down the question, are there problems that can be solved with Splay Trees but not with Treaps?

Through a brief research session, I found the following blog from CF that partially answers my question. https://codeforces.com/blog/entry/60499 Apparently, Link Cut Trees can be maintained with Splay Trees in N log N time while Treaps have an additional log factor. Are there other instances of this?

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/23/2024 01:00:20 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|