fork(3) download
copy 
  1.  
  2. /**
  3.  * Binary Search Tree
  4.  */
  5. #[derive(Debug)]
  6. enum BinarySearchTree<T> {
  7.     Bin(
  8.         usize, // size
  9.         i64, // priority
  10.         T, // value
  11.         Box<BinarySearchTree<T>>,
  12.         Box<BinarySearchTree<T>>,
  13.     ),
  14.     Tip,
  15. }
  16.  
  17. // https://w...content-available-to-author-only...e.net/iwiwi/2-12188757
  18. impl<T: Ord> BinarySearchTree<T> {
  19.     pub fn singleton(v: T, pri: i64) -> Self {
  20.         use BinarySearchTree::*;
  21.         Bin(1, pri, v, Box::new(Tip), Box::new(Tip))
  22.     }
  23.     pub fn size(&self) -> usize {
  24.         use BinarySearchTree::*;
  25.         match *self {
  26.             Bin(t, _,  _, _, _) => t,
  27.             Tip => 0,
  28.         }
  29.     }
  30.     // Merges two BST. Their ownership is taken.
  31.     pub fn merge(left: Self, right: Self) -> Self {
  32.         use BinarySearchTree::*;
  33.         match (left, right) {
  34.             (Tip, Tip) => Tip,
  35.             (Tip, x) => x,
  36.             (x, Tip) => x,
  37.             (Bin(lsize, lpri, lelem, lleft, lright),
  38.              Bin(rsize, rpri, relem, rleft, rright)) => {
  39.                 if lpri > rpri {
  40.                     let right = Bin(rsize, rpri, relem, rleft, rright);
  41.                     let mut ret = Bin(lsize, lpri, lelem, lleft,
  42.                                   Box::new(Self::merge(*lright, right)));
  43.                     ret.update();
  44.                     ret
  45.                 } else {
  46.                     let left = Bin(lsize, lpri, lelem, lleft, lright);
  47.                     let mut ret = Bin(rsize, rpri, relem,
  48.                                       Box::new(Self::merge(left, *rleft)),
  49.                                       rright);
  50.                     ret.update();
  51.                     ret
  52.                 }
  53.             }
  54.         }
  55.     }
  56.     pub fn split(self, k: usize) -> (Self, Self) {
  57.         use BinarySearchTree::*;
  58.         match self {
  59.             Tip => (Tip, Tip),
  60.             Bin(size, pri, elem, left, right) => {
  61.                 if k <= left.size() {
  62.                     let (sl, sr) = Self::split(*left, k);
  63.                     let mut ret = Bin(size, pri, elem, Box::new(sr), right);
  64.                     ret.update();
  65.                     (sl, ret)
  66.                 } else {
  67.                     let (sl, sr) = Self::split(*right, k - left.size() - 1);
  68.                     let mut ret = Bin(size, pri, elem, left, Box::new(sl));
  69.                     ret.update();
  70.                     (ret, sr)
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     fn update(&mut self) {
  76.         use BinarySearchTree::*;
  77.         match *self {
  78.             Tip => (),
  79.             Bin(ref mut lsize, ref _pri, ref _elem, ref left, ref right) => {
  80.                 *lsize = left.size() + right.size() + 1;
  81.             },
  82.         }
  83.     }
  84.     fn insert_at(self, v: T, pri: i64, k: usize) -> Self {
  85.         let sing = Self::singleton(v, pri);
  86.         let (left, right) = self.split(k);
  87.         let tmp = Self::merge(left, sing);
  88.         Self::merge(tmp, right)
  89.     }
  90.     fn erase_at(self, k: usize) -> Self {
  91.         let (left, singright) = self.split(k);
  92.         let (sing, right) = singright.split(1);
  93.         assert_eq!(sing.size(), 1);
  94.         Self::merge(left, right)
  95.     }
  96.     fn find_index(&self, t: &T) -> (usize, bool) {
  97.         use BinarySearchTree::*;
  98.         use std::cmp::Ordering;
  99.         match *self {
  100.             Tip => (0, false),
  101.             Bin(_, _, ref elem, ref left, ref right) => {
  102.                 match elem.cmp(t) {
  103.                     Ordering::Equal => (left.size(), true),
  104.                     Ordering::Less =>
  105.                         left.find_index(t),
  106.                     Ordering::Greater => {
  107.                         let (idx, found) = right.find_index(t);
  108.                         (idx + left.size() + 1, found)
  109.                     },
  110.                 }
  111.             }
  112.         }
  113.     }
  114.     fn insert(self, v: T, pri: i64) -> Self {
  115.         let (idx, found) = self.find_index(&v);
  116.         if found {
  117.             self
  118.         } else {
  119.             self.insert_at(v, pri, idx)
  120.         }
  121.     }
  122.     fn erase(self, v: &T) -> Self {
  123.         let (idx, found) = self.find_index(v);
  124.         if found {
  125.             self.erase_at(idx)
  126.         } else {
  127.             self
  128.         }
  129.     }
  130. }
  131.  
  132. fn depth<T>(t: &BinarySearchTree<T>) -> usize {
  133.     match *t {
  134.         BinarySearchTree::Tip => 0,
  135.         BinarySearchTree::Bin(_, _, _, ref left, ref right) => {
  136.             std::cmp::max(depth(left), depth(right)) + 1
  137.         }
  138.     }
  139. }
  140.  
  141. fn main() {
  142.     let mut bst = BinarySearchTree::Tip::<usize>;
  143.     let mut seed: i64 = 0xdeadc0de;
  144.     let mut next = || {
  145.         seed = seed.wrapping_mul(0x12345678deadc0d1).wrapping_add(0x1551);
  146.         seed
  147.     };
  148.     const N: usize = 10000;
  149.     for _ in 0 .. 1000 { next(); }
  150.     let mut cur_depth = 0;
  151.     for i in 0 .. N {
  152.         bst = bst.insert(i, next());
  153.         let dep = depth(&bst);
  154.         if cur_depth != dep {
  155.             println!("i = {}, depth = {}", i, dep);
  156.             cur_depth = dep;
  157.         }
  158.     }
  159. }
  160.  
Success #stdin #stdout 1.29s 14880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
i = 0, depth = 1
i = 1, depth = 2
i = 2, depth = 3
i = 4, depth = 4
i = 5, depth = 5
i = 7, depth = 6
i = 16, depth = 7
i = 27, depth = 8
i = 42, depth = 9
i = 74, depth = 10
i = 82, depth = 11
i = 133, depth = 12
i = 136, depth = 13
i = 137, depth = 14
i = 162, depth = 15
i = 213, depth = 16
i = 219, depth = 17
i = 237, depth = 18
i = 295, depth = 19
i = 395, depth = 20
i = 421, depth = 21
i = 429, depth = 22
i = 882, depth = 23
i = 1352, depth = 24
i = 1834, depth = 25
i = 1957, depth = 26
i = 2167, depth = 27
i = 8104, depth = 28
i = 8345, depth = 29
https://ideone.com/H32Kd4
Treap in Rust<br>Inserting 10^4 elements in ascending order
language:
Rust (rust 1.56)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!