fork download
copy 
  1. /// 2-3 Tree
  2. /// Reference: https://e...content-available-to-author-only...a.org/wiki/2%E2%80%933_tree
  3. /// https://w...content-available-to-author-only...e.net/sandpoonia/23-tree
  4. /// Verified by: ARC061-D (http://a...content-available-to-author-only...r.jp/submissions/1243868)
  5. #[derive(Clone, Debug)]
  6. enum TwoThreeTree<T> {
  7.     Tip,
  8.     Two(
  9.         usize, // size
  10.         T, // value
  11.         Box<TwoThreeTree<T>>, // left
  12.         Box<TwoThreeTree<T>>, // right
  13.     ),
  14.     Three(
  15.         usize, // size
  16.         T, // val1
  17.         T, // val2
  18.         Box<TwoThreeTree<T>>, // left
  19.         Box<TwoThreeTree<T>>, // middle
  20.         Box<TwoThreeTree<T>>, // right
  21.     ),
  22. }
  23.  
  24. impl<T: Ord> TwoThreeTree<T> {
  25.     pub fn new() -> Self {
  26.         TwoThreeTree::Tip
  27.     }
  28.     fn size(&self) -> usize {
  29.         use TwoThreeTree::*;
  30.         match *self {
  31.             Tip => 0,
  32.             Two(sz, _, _, _) => sz,
  33.             Three(sz, _, _, _, _, _) => sz,
  34.         }
  35.     }
  36.     fn leaf_one(x: T) -> Self {
  37.         use TwoThreeTree::*;
  38.         Two(1, x, Box::new(Tip), Box::new(Tip))
  39.     }
  40.     fn leaf_two(x: T, y: T) -> Self {
  41.         use TwoThreeTree::*;
  42.         Three(2, x, y, Box::new(Tip), Box::new(Tip), Box::new(Tip))
  43.     }
  44.     fn node_two(x: T, left: Self, right: Self) -> Self {
  45.         TwoThreeTree::Two(left.size() + right.size() + 1, x,
  46.                           Box::new(left), Box::new(right))
  47.     }
  48.     fn node_three(x: T, y: T, left: Self, middle: Self, right: Self) -> Self {
  49.         TwoThreeTree::Three(left.size() + middle.size() + right.size() + 2,
  50.                             x, y,
  51.                             Box::new(left), Box::new(middle), Box::new(right))
  52.     }
  53.     fn divide_four(t1: Self, v1: T, t2: Self, v2: T,
  54.                        t3: Self, v3: T, t4: Self) -> (Self, Self, T) {
  55.         (Self::node_two(v1, t1, t2), Self::node_two(v3, t3, t4), v2)
  56.     }
  57.     // Ok(x) -> ordinary tree
  58.     // Err((t1, t2, v)) -> propagating v, whilst dividing the tree into t1, t2
  59.     fn insert_sub(self, x: T) -> Result<Self, (Self, Self, T)> {
  60.         use TwoThreeTree::*;
  61.         match self {
  62.             Tip => Ok(Self::leaf_one(x)),
  63.             Two(1, val, _, _) => // leaf
  64.                 Ok(match x.cmp(&val) {
  65.                     std::cmp::Ordering::Equal => Self::leaf_one(val),
  66.                     std::cmp::Ordering::Less => Self::leaf_two(x, val),
  67.                     std::cmp::Ordering::Greater => Self::leaf_two(val, x),
  68.                 }),
  69.             Three(2, val1, val2, _, _, _) => { // leaf
  70.                 // $a, $b, $c should be increasing in this order.
  71.                 macro_rules! err_3 {
  72.                     ($a:expr, $b:expr, $c:expr) => {
  73.                         Err((Self::leaf_one($a),
  74.                              Self::leaf_one($c),
  75.                              $b))
  76.                     }
  77.                 }
  78.                 if val1 == x || val2 == x {
  79.                     Ok(Self::leaf_two(val1, val2))
  80.                 } else if x < val1 {
  81.                     err_3!(x, val1, val2)
  82.                 } else if x < val2 {
  83.                     err_3!(val1, x, val2)
  84.                 } else {
  85.                     err_3!(val1, val2, x)
  86.                 }
  87.             }
  88.             Two(size, val, left, right) => {
  89.                 match x.cmp(&val) {
  90.                     std::cmp::Ordering::Equal => 
  91.                         Ok(Two(size, val, left, right)),
  92.                     std::cmp::Ordering::Less => {
  93.                         match left.insert_sub(x) {
  94.                             Ok(t) => Ok(Self::node_two(val, t, *right)),
  95.                             Err((t1, t2, sub_up)) =>
  96.                                 Ok(Self::node_three(sub_up, val,
  97.                                                     t1, t2, *right)),
  98.                         }
  99.                     },
  100.                     std::cmp::Ordering::Greater => {
  101.                         match right.insert_sub(x) {
  102.                             Ok(t) => Ok(Self::node_two(val, *left, t)),
  103.                             Err((t1, t2, sub_up)) =>
  104.                                 Ok(Self::node_three(val, sub_up,
  105.                                                     *left, t1, t2)),
  106.                         }
  107.                     },
  108.                 }
  109.  
  110.             }
  111.             Three(size, val1, val2, left, middle, right) => {
  112.                 if x == val1 || x == val2 {
  113.                     return Ok(Three(size, val1, val2, left, middle, right));
  114.                 }
  115.                 if x < val1 {
  116.                     match left.insert_sub(x) {
  117.                         Ok(sub_tr) =>
  118.                             Ok(Self::node_three(val1, val2,
  119.                                                 sub_tr, *middle, *right)),
  120.                         Err((t1, t2, sub_up)) => {
  121.                             let (t1, t2, v) = Self::divide_four(
  122.                                 t1, sub_up, t2, val1,
  123.                                 *middle, val2, *right);
  124.                             Err((t1, t2, v))
  125.                         },
  126.                     }
  127.                 } else if x < val2 {
  128.                     match middle.insert_sub(x) {
  129.                         Ok(sub_tr) =>
  130.                             Ok(Self::node_three(val1, val2,
  131.                                                 *left, sub_tr, *right)),
  132.                         Err((t1, t2, sub_up)) => {
  133.                             let (t1, t2, v) = Self::divide_four(
  134.                                 *left, val1, t1, sub_up,
  135.                                 t2, val2, *right);
  136.                             Err((t1, t2, v))
  137.                         },
  138.                     }
  139.                 } else {
  140.                     match right.insert_sub(x) {
  141.                         Ok(sub_tr) =>
  142.                             Ok(Self::node_three(val1, val2,
  143.                                                 *left, *middle, sub_tr)),
  144.                         Err((t1, t2, sub_up)) => {
  145.                             let (t1, t2, v) = Self::divide_four(
  146.                                 *left, val1, *middle, val2,
  147.                                 t1, sub_up, t2);
  148.                             Err((t1, t2, v))
  149.                         },
  150.                     }
  151.                 }
  152.             }
  153.         }
  154.     }
  155.     fn insert(self, x: T) -> Self {
  156.         match self.insert_sub(x) {
  157.             Ok(t) => t,
  158.             Err((t1, t2, v)) =>
  159.                 Self::node_two(v, t1, t2),
  160.         }
  161.     }
  162.     fn into_vec_sub(self, ret: &mut Vec<T>) {
  163.         use TwoThreeTree::*;
  164.         match self {
  165.             Tip => (),
  166.             Two(_, val, left, right) => {
  167.                 left.into_vec_sub(ret);
  168.                 ret.push(val);
  169.                 right.into_vec_sub(ret);
  170.             },
  171.             Three(_, val1, val2, left, middle, right) => {
  172.                 left.into_vec_sub(ret);
  173.                 ret.push(val1);
  174.                 middle.into_vec_sub(ret);
  175.                 ret.push(val2);
  176.                 right.into_vec_sub(ret);
  177.             },
  178.         }
  179.     }
  180.     pub fn find_index(&self, x: &T) -> (usize, bool) {
  181.         use TwoThreeTree::*;
  182.         match *self {
  183.             Tip => (0, false),
  184.             Two(_size, ref v, ref left, ref right) => {
  185.                 match x.cmp(v) {
  186.                     std::cmp::Ordering::Equal => (left.size(), true),
  187.                     std::cmp::Ordering::Less => left.find_index(x),
  188.                     std::cmp::Ordering::Greater => {
  189.                         let (res, found) = right.find_index(x);
  190.                         (res + left.size() + 1, found)
  191.                     },
  192.                 }
  193.             },
  194.             Three(_size, ref v1, ref v2, ref left, ref middle, ref right) => {
  195.                 if x == v1 {
  196.                     return (left.size(), true);
  197.                 }
  198.                 if x == v2 {
  199.                     return (left.size() + middle.size() + 1, true);
  200.                 }
  201.                 if x < v1 {
  202.                     return left.find_index(x);
  203.                 }
  204.                 if x < v2 {
  205.                     let (res, found) = middle.find_index(x);
  206.                     return (left.size() + 1 + res, found);
  207.                 }
  208.                 let (res, found) = right.find_index(x);
  209.                 return (left.size() + middle.size() + 2 + res, found);
  210.             }
  211.         }
  212.     }
  213.     pub fn into_vec(self) -> Vec<T> {
  214.         let mut ret = Vec::with_capacity(self.size());
  215.         self.into_vec_sub(&mut ret);
  216.         ret
  217.     }
  218. }
  219.  
  220. fn depth<T>(t: &TwoThreeTree<T>) -> usize {
  221.     use TwoThreeTree::*;
  222.     match *t {
  223.         Tip => 0,
  224.         Two(_, _, ref left, _) => 1 + depth(left),
  225.         Three(_, _, _, ref left, _, _) => 1 + depth(left),
  226.     }
  227. }
  228.  
  229. fn main() {
  230.     let mut bst = TwoThreeTree::new();
  231.     let mut seed: i64 = 0xdeadc0de;
  232.     let mut next = || {
  233.         seed = seed.wrapping_mul(0x12345678deadc0d1).wrapping_add(0x1551);
  234.         seed
  235.     };
  236.     const N: usize = 1000000;
  237.     for _ in 0 .. 1000 { next(); }
  238.     let mut cur_depth = 0;
  239.     for i in 0 .. N {
  240.         let elem = (next() & 0xffff_ffff) as usize;
  241.         bst = bst.insert(elem);
  242.         let dep = depth(&bst);
  243.         if cur_depth != dep {
  244.             println!("i = {}, depth = {}", i, dep);
  245.             cur_depth = dep;
  246.         }
  247.     }
  248. }
  249.  
Success #stdin #stdout 4.13s 125504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
i = 0, depth = 1
i = 2, depth = 2
i = 8, depth = 3
i = 20, depth = 4
i = 39, depth = 5
i = 110, depth = 6
i = 224, depth = 7
i = 491, depth = 8
i = 1092, depth = 9
i = 2706, depth = 10
i = 5742, depth = 11
i = 13766, depth = 12
i = 31174, depth = 13
i = 77884, depth = 14
i = 165506, depth = 15
i = 373738, depth = 16
i = 942167, depth = 17
https://ideone.com/6DHM21
2-3 tree in Rust
Inserting 10^6 elements in a random 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!