Treap on Rust

Revision en2, by kobae964, 2017-03-23 04:15:49

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 randomness. (For more details see Wikipedia.)

Tags rust, binary search tree, treap, experiment

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)