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

Автор biximo, история, 4 месяца назад, По-английски

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
  • Проголосовать: не нравится

Автор biximo, история, 8 месяцев назад, По-английски

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?

Полный текст и комментарии »

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