fork download
  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
stdin
Standard input is empty
stdout
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