SHARE
TWEET

Untitled

a guest Apr 21st, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use std::boxed::Box;
  2. use std::cmp::max;
  3.  
  4. fn main() {
  5.  
  6.     let avl = state((1..=100).collect::<Vec<isize>>());
  7.  
  8.     println!("{:#?}", avl)
  9. }
  10.  
  11. fn state(num: Vec<isize>) -> AVL {
  12.     let mut avl = AVL::new();
  13.     let num = num;
  14.     for key in num.iter() {
  15.         avl.insert(*key);
  16.     }
  17.     avl
  18. }
  19.  
  20. #[derive(Debug, Clone, PartialEq)]
  21. pub struct Node {
  22.     height: isize,
  23.     key: isize,
  24.     left: Option<Box<Node>>,
  25.     right: Option<Box<Node>>,
  26. }
  27.  
  28.  
  29. #[derive(Debug, Clone, PartialEq)]
  30. pub struct AVL {
  31.     root: Option<Box<Node>>,
  32. }
  33.  
  34.  
  35. impl AVL
  36. {
  37.     pub fn new() -> Self
  38.     {
  39.         Self {
  40.             root: None
  41.         }
  42.     }
  43.  
  44.  
  45.     pub fn insert(&mut self, insert_key: isize)
  46.     {
  47.         if let Some(node) = &mut self.root {
  48.             node.insert(insert_key);
  49.             node.modify_height();
  50.         } else {    //  空のとき入れる
  51.             let key = Box::new(Node::new(insert_key));
  52.             self.root = Some(key);
  53.         }
  54.     }
  55.  
  56.     pub fn delete(&mut self, delete_key: isize) -> bool
  57.     {
  58.         if let Some(node) = &mut self.root {
  59.             node.delete(delete_key)
  60.         } else {
  61.             false
  62.         }
  63.     }
  64. }
  65.  
  66. impl Node
  67. {
  68.     fn new(n_key: isize) -> Self
  69.     {
  70.         Self {
  71.             height: 1,
  72.             key: n_key,
  73.             left: None,
  74.             right: None,
  75.         }
  76.     }
  77.  
  78.  
  79.     fn insert(&mut self, insert_key: isize)
  80.     {
  81.         if self.key < insert_key {
  82.             if let Some(node) = &mut self.right {
  83.                 node.insert(insert_key);
  84.                 node.modify_height();
  85.             } else {
  86.                 let key = Box::new(Self::new(insert_key));
  87.                 self.right = Some(key);
  88.                 self.modify_height();
  89.             }
  90.             if self.check_height() { self.rotate_r(); }
  91.         } else if self.key > insert_key { // self.key > insert_key
  92.             if let Some(node) = &mut self.left {
  93.                 node.insert(insert_key);
  94.                 node.modify_height();
  95.             } else {
  96.                 let key = Box::new(Self::new(insert_key));
  97.                 self.left = Some(key);
  98.                 self.modify_height();
  99.             }
  100.             if self.check_height() { self.rotate_l(); }
  101.         } else {
  102. //            Do nothing
  103.         }
  104.         self.modify_height();
  105.     }
  106.  
  107.     fn delete(&mut self, delete_key: isize) -> bool // "Hit"=>true, "Nothing"=>false
  108.     {
  109.         if self.key < delete_key {
  110.             if let Some(node) = &mut self.right {
  111.                 if node.key == delete_key { // Hit!
  112.                     if let Some(node_left) = &mut node.left {
  113.                         let max_key = node_left.delete_max_key();
  114.                         node.delete(max_key);
  115.                         node.key = max_key;
  116.                         if node.check_height() { node.rotate_r(); }
  117.                     } else if let Some(node_right) = &mut node.right {
  118.                         let key = node_right.key;
  119.                         node.delete(key);
  120.                         node.key = key;
  121.                     } else {
  122.                         self.right = None;
  123.                     }
  124.                     self.modify_height();
  125.                     true
  126.                 } else {
  127.                     node.delete(delete_key)
  128.                 }
  129.             } else { false }
  130.         } else if self.key > delete_key { // self.key > insert_key
  131.             if let Some(node) = &mut self.left {
  132.                 if node.key == delete_key { // Hit!
  133.                     if let Some(node_left) = &mut node.left {
  134.                         let max_key = node_left.delete_max_key();
  135.                         node.delete(max_key);
  136.                         node.key = max_key;
  137.                         if node.check_height() { node.rotate_l(); }
  138.                     } else if let Some(node_right) = &mut node.right {
  139.                         let key = node_right.key;
  140.                         node.delete(key);
  141.                         node.key = key;
  142.                     } else {
  143.                         self.left = None;
  144.                     }
  145.                     self.modify_height();
  146.                     true
  147.                 } else {
  148.                     node.delete(delete_key)
  149.                 }
  150.             } else { false }
  151.         } else {
  152.             false
  153.         }
  154.     }
  155. }
  156.  
  157. impl Node {
  158.     fn delete_max_key(&mut self) -> isize //
  159.     {
  160.         if let Some(node_right) = &mut self.right {
  161.             node_right.delete_max_key()
  162.         } else if let Some(node_left) = &mut self.left {
  163.             node_left.delete_max_key()
  164.         } else {
  165.             self.key
  166.         }
  167.     }
  168.  
  169.     fn modify_height(&mut self)
  170.     {
  171.         let (left, right) = {
  172.             let r = if let Some(n) = &self.right { n.height } else { 0 };
  173.             let l = if let Some(n) = &self.left { n.height } else { 0 };
  174.             (l, r)
  175.         };
  176.         self.height = max(left, right) + 1;
  177.     }
  178.  
  179.     fn check_height(&self) -> bool
  180.     {
  181.         let (left, right) = {
  182.             let r = if let Some(n) = &self.right { n.height } else { 0 };
  183.             let l = if let Some(n) = &self.left { n.height } else { 0 };
  184.             (l, r)
  185.         };
  186.         let diff = (left - right).abs();
  187.         diff == 2
  188.     }
  189.  
  190.     fn rotate_l(&mut self)
  191.     {
  192.         let mut shaft_node_key = self.clone();
  193.         let mut l = self.left.clone().unwrap();
  194.         let (left, right) = {
  195.             let rh = if let Some(n) = &l.right { n.height } else { 0 };
  196.             let lh = if let Some(n) = &l.left { n.height } else { 0 };
  197.             (lh, rh)
  198.         };
  199.         if left > right { // l.left > l.right
  200.             if let Some(l_right) = &mut l.right {
  201.                 shaft_node_key.left = Some(l_right.clone());
  202.                 shaft_node_key.modify_height();
  203.                 *l_right = Box::new(shaft_node_key);
  204.             } else {
  205.                 shaft_node_key.left = None;
  206.                 shaft_node_key.modify_height();
  207.                 l.right = Some(Box::new(shaft_node_key));
  208.             }
  209.         } else { // l.left < l.right
  210.             if let Some(l_right) = &mut l.right {
  211.                 shaft_node_key.left = None;
  212.                 l_right.left = Some(Box::new({
  213.                     let mut n = Self::new(l.key);
  214.                     n.modify_height();
  215.                     n
  216.                 }));
  217.                 l_right.right = Some(Box::new({
  218.                     shaft_node_key.modify_height();
  219.                     shaft_node_key
  220.                 }));
  221.                 l_right.modify_height();
  222.                 l = l_right.clone();
  223.             }
  224.         }
  225.         *self = *l;
  226.     }
  227.  
  228.     fn rotate_r(&mut self)
  229.     {
  230.         let mut shaft_node_key = self.clone();
  231.         let mut r = self.right.clone().unwrap();
  232.         let (left, right) = {
  233.             let rh = if let Some(n) = &r.right { n.height } else { 0 };
  234.             let lh = if let Some(n) = &r.left { n.height } else { 0 };
  235.             (lh, rh)
  236.         };
  237.         if left < right { // r.left < r.right
  238.             if let Some(r_left) = &mut r.left {
  239.                 shaft_node_key.right = Some(r_left.clone());
  240.                 shaft_node_key.modify_height();
  241.                 *r_left = Box::new(shaft_node_key);
  242.             } else {
  243.                 shaft_node_key.right = None;
  244.                 shaft_node_key.modify_height();
  245.                 r.left = Some(Box::new(shaft_node_key));
  246.             }
  247.         } else { // r.left > r.right
  248.             if let Some(r_left) = &mut r.left {
  249.                 shaft_node_key.left = None;
  250.                 r_left.right = Some(Box::new({
  251.                     let mut n = Self::new(r.key);
  252.                     n.modify_height();
  253.                     n
  254.                 }));
  255.                 r_left.left = Some(Box::new({
  256.                     shaft_node_key.modify_height();
  257.                     shaft_node_key
  258.                 }));
  259.                 r_left.modify_height();
  260.                 r = r_left.clone();
  261.             }
  262.         }
  263.         *self = *r;
  264.     }
  265. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top