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 | tourist | 3856 |
2 | jiangly | 3747 |
3 | orzdevinwang | 3706 |
4 | jqdai0815 | 3682 |
5 | ksun48 | 3591 |
6 | gamegame | 3477 |
7 | Benq | 3468 |
8 | Radewoosh | 3462 |
9 | ecnerwala | 3451 |
10 | heuristica | 3431 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | -is-this-fft- | 162 |
3 | Dominater069 | 160 |
4 | Um_nik | 158 |
5 | atcoder_official | 156 |
6 | Qingyu | 155 |
7 | djm03178 | 151 |
7 | adamant | 151 |
9 | luogu_official | 150 |
10 | awoo | 147 |
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.net/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?
Name |
---|