Treap on Rust

Правка en9, от kobae964, 2017-04-24 10:06:53

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:

(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/yxVe6d
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/263af7e258cf37bd48902f027e4e1f38b016b7d0.png

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/yxVe6d

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)