Treap on Rust
Difference between en10 and en11, changed 58 character(s)
I recently implemented Treap, one of various kinds of binary search trees (BSTs), on Rust. It is a balanced BST, which means that it ensures that tree depth is always $O(\log(n))$ where $n =$ (the number of items in a tree). That is achieved by using randomisation. (For more details see <a href="https://en.wikipedia.org/wiki/Treap">Treap &mdash; Wikipedia</a>.)↵
↵
Experiments↵
------------------↵
Here are results of some experiments:↵
↵
(1) Insertion of 10000 elements in the ascending order:<br>↵
http://ideone.com/tSrw7u <br>↵
It took 11.7 seconds to insert 30000 elements in the ascending order, and it got Time Limit Exceeded (>15.0sec) when the number of elements is >100000. You'll see that the depth of the treap increases in logarithmic speed.↵
↵
(2) Insertion of 10000 elements in a random order: <br>↵
http://ideone.com/yxVe6d <br>↵
It took 11.8 seconds to insert 30000 elements in a random order. Like (1), the depth of the treap increases in logarithmic speed, too.↵
↵
↵
Here is a graph that indicates how the depth of the treap grows as the number of elements increases.↵
↵
/predownloaded/26/3a/263af7e258cf37bd48902f027e4e1f38b016b7d0a5/1c/a51c479dd2e7492acf685532dd97f6624bd7b961.png↵
↵
Conclusion↵
------------------↵
We have a balanced BST, whose depth is bounded by $O(\log(\mathrm{size}))$ !<br>↵
Unfortunately, a solution ([submission:25637342]) to [problem:785E] that uses this treap, which should work in $O(n\log(n) + q(\log(n))^2)$-time, got the Time limit exceeded verdict. That seems because of its heavy constant factor, but I'm not sure.↵
↵
References↵
------------------↵
The code I used in these experiments is avaliable at: https://github.com/koba-e964/contest/blob/906fcb07057b72496407b3c6e6a422e48e60dc6f/comm/Treap.rs<br>↵
http://ideone.com/tSrw7u <br>↵
http://ideone.com/yxVe6d <br>↵
↵
This implementation of treap largely depends on the slide (https://www.slideshare.net/iwiwi/2-12188757, written in Japanese) by [user:iwiwi,2017-04-24].↵
This implementation of treap is verified by http://arc061.contest.atcoder.jp/submissions/1172709 (AtCoder ARC 061 D, problem statement is avaliable at http://arc061.contest.atcoder.jp/tasks/arc061_b ).↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English kobae964 2017-04-25 19:56:58 1 Tiny change: ' the vertial one sho' -> ' the vertical one sho'
en14 English kobae964 2017-04-24 11:48:52 1 Tiny change: 'n.):<br>\n.\n(1) Inse' -> 'n.):<br>\n\n(1) Inse'
en13 English kobae964 2017-04-24 11:41:10 421 Fix insertion in a random order
en12 English kobae964 2017-04-24 10:13:32 70
en11 English kobae964 2017-04-24 10:12:22 58
en10 English kobae964 2017-04-24 10:10:28 2 Tiny change: '/arc061_b)\n' -> '/arc061_b).\n' (published)
en9 English kobae964 2017-04-24 10:06:53 479 Tiny change: '$O(q(\log(n))' -> '$O(n\log(n) + q(\log(n))'
en8 English kobae964 2017-04-24 09:52:19 81
en7 English kobae964 2017-04-24 09:50:35 297
en6 English kobae964 2017-04-24 09:37:25 251 Add graph
en5 English kobae964 2017-04-24 09:05:27 820 Add results of experiment
en4 English kobae964 2017-03-23 07:25:05 41 Tiny change: '</a>.)\n\n' -> '</a>.)\n\nHere are results of some experiments:\n\n'
en3 English kobae964 2017-03-23 05:14:54 78 Tiny change: 'ipedia.)\n\n' -> 'ipedia.)\n$n$\n<math>n</math>\n\n'
en2 English kobae964 2017-03-23 04:15:49 62
en1 English kobae964 2017-03-22 20:51:47 248 Initial revision (saved to drafts)