SHARE
TWEET

Untitled

a guest Aug 20th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #![allow(unused)]
  2.  
  3. use std::iter::empty as empty_iter;
  4. use std::iter::once;
  5. use std::mem::{self};
  6. use BST::*;
  7.  
  8. #[derive(Debug)]
  9. enum BST<T> {
  10.     Empty,
  11.     Node {
  12.         value: T,
  13.         left: Box<BST<T>>,
  14.         right: Box<BST<T>>,
  15.     },
  16. }
  17.  
  18. impl<T: PartialOrd> BST<T> {
  19.     // Associated Functions
  20.     fn leaf(value: T) -> Self {
  21.         Node {
  22.             value,
  23.             left: Box::new(Empty),
  24.             right: Box::new(Empty),
  25.         }
  26.     }
  27.  
  28.     // Associated Methods
  29.     fn is_empty(&self) -> bool {
  30.         if let Empty = self {
  31.             true
  32.         } else {
  33.             false
  34.         }
  35.     }
  36.  
  37.     fn insert(&mut self, to_insert: T) {
  38.         match self {
  39.             Empty => *self = BST::leaf(to_insert),
  40.             Node { value, left, right } => {
  41.                 if to_insert < *value {
  42.                     left.insert(to_insert)
  43.                 } else if to_insert > *value {
  44.                     right.insert(to_insert)
  45.                 }
  46.             }
  47.         }
  48.     }
  49.  
  50.     // Tree Traverslas
  51.     fn pre_order_iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
  52.         match self {
  53.             Empty => Box::new(empty_iter()),
  54.             Node { value, left, right } => Box::new(
  55.                 once(value)
  56.                     .chain(left.pre_order_iter())
  57.                     .chain(right.pre_order_iter()),
  58.             ),
  59.         }
  60.     }
  61.  
  62.     fn in_order_iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
  63.         match self {
  64.             Empty => Box::new(empty_iter()),
  65.             Node { value, left, right } => Box::new(
  66.                 left.in_order_iter()
  67.                     .chain(once(value))
  68.                     .chain(right.in_order_iter()),
  69.             ),
  70.         }
  71.     }
  72.  
  73.     fn post_order_iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
  74.         match self {
  75.             Empty => Box::new(empty_iter()),
  76.             Node { value, left, right } => Box::new(
  77.                 left.post_order_iter()
  78.                     .chain(right.post_order_iter())
  79.                     .chain(once(value)),
  80.             ),
  81.         }
  82.     }
  83.  
  84.     // Tree Removal
  85.     fn min_mut(&mut self) -> Option<&mut T> {
  86.         match self {
  87.             Empty => None,
  88.             Node { value, left, .. } => {
  89.                 if left.is_empty() {
  90.                     Some(value)
  91.                 } else {
  92.                     left.min_mut()
  93.                 }
  94.             }
  95.         }
  96.     }
  97.  
  98.     fn remove(&mut self, to_remove: &T) {
  99.         match self {
  100.             Empty => (),
  101.             Node { value, left, right } => {
  102.                 if to_remove < value {
  103.                     left.remove(to_remove);
  104.                 } else if to_remove > value {
  105.                     right.remove(to_remove);
  106.                 } else {
  107.                     match (&**left, &**right) {
  108.                         (Empty, Empty) => *self = Empty,
  109.                         (_, Empty) => *self = mem::replace(&mut **left, Empty),
  110.                         (Empty, _) => *self = mem::replace(&mut **right, Empty),
  111.                         _ => {
  112.                             mem::swap(value, right.min_mut().unwrap());
  113.                             right.remove(to_remove);
  114.                         }
  115.                     }
  116.                 }
  117.             }
  118.         }
  119.     }
  120. }
  121.  
  122. fn main() {
  123.     eprintln!();
  124.  
  125.     let mut bst = BST::leaf(5);
  126.     bst.insert(8);
  127.     bst.insert(2);
  128.     bst.insert(3);
  129.     bst.insert(1);
  130.     bst.insert(6);
  131.     bst.insert(9);
  132.     bst.insert(7);
  133.  
  134.     bst.remove(&5);
  135.  
  136.     dbg!(&bst);
  137.  
  138.     for x in bst.in_order_iter() {
  139.         println!("{}", x);
  140.     }
  141. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top