Treap on Rust

Правка en15, от kobae964, 2017-04-25 19:56:58

UPD: Fixed the code (insertion in a random order), based on the comment.

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 where n =  (the number of items in a tree). That is achieved by using randomisation. (For more details see Treap — Wikipedia.)

Experiments

Here are results of some experiments (UPD: these experiments themselves take O(n2)-time, because function depth() takes O(n)-time, which is called in each iteration.):

(1) Insertion of 10000 elements in the ascending order:
http://ideone.com/tSrw7u
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:
http://ideone.com/pW7sBf
It took 15.011.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. The horizontal line shows the number of nodes in the treap and the vertical one shows the depth of the treap.

Conclusion

We have a balanced BST, whose depth is bounded by !
Unfortunately, a solution (25637342) to 785E - Anton and Permutation that uses this treap, which should work in -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
http://ideone.com/tSrw7u
http://ideone.com/pW7sBf

This implementation of treap largely depends on the slide (https://www.slideshare.net/iwiwi/2-12188757, written in Japanese) by iwiwi. 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 ).

Теги rust, binary search tree, treap, experiment

История

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