I recently implemented Treap, one of various kinds of binary search trees (BSTs), on Rust. It ensures that tree depth is always O(log(n)) where n = (the number of items in a tree), by using randomness. (For more details see Wikipedia.)
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Treap on Rust
I recently implemented Treap, one of various kinds of binary search trees (BSTs), on Rust. It ensures that tree depth is always O(log(n)) where n = (the number of items in a tree), by using randomness. (For more details see Wikipedia.)
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
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) |
Name |
---|