rust_black_trees/
tree.rs

1use super::node::Node;
2use super::node::*;
3
4pub trait BaseTree<T> {
5    type MNode: Node<T>;
6    fn get(&self, val: usize) -> &Self::MNode;
7    fn get_mut(&self, val: usize) -> &mut Self::MNode;
8
9    fn delete_node(&mut self, index: usize);
10    fn create_node(&mut self, val: T) -> usize;
11
12    fn rebalance_ins(&mut self, n: usize);
13    fn rebalance_del(&mut self, n: usize, child: usize);
14
15    fn delete_replace(&mut self, n: usize) -> usize;
16    fn replace_node(&mut self, to_delete: usize, to_attach: Option<usize>);
17
18    fn attach_child(&self, p: usize, c: usize, side: Side);
19
20    fn get_root(&self) -> Option<usize>;
21    fn set_root(&mut self, new_root: Option<usize>);
22
23    fn get_size(&self) -> usize;
24    fn crement_size(&mut self, val: isize);
25}
26
27pub trait Tree<T: std::fmt::Debug>: BaseTree<T> {
28    fn new() -> Self;
29
30    fn is_empty(&self) -> bool {
31        return self.get_root().is_none()
32    }
33
34    fn contains(&self, val: &T) -> bool {
35        let n = self.find(val);
36        self.get(n).is(val)
37    }
38
39    fn insert(&mut self, val: T) {
40        if let Some(_root) = self.get_root() {
41            let n = self.find(&val);
42            let node = self.get(n);
43            if node.is(&val) {
44                // value already in tree
45                self.crement_size(-1);
46            } else {
47                let side = if node.lesser(&val) {
48                    Side::Right
49                } else {
50                    Side::Left
51                };
52                let node = self.create_node(val);
53                self.attach_child(n, node, side);
54                self.rebalance_ins(node);
55            }
56        } else {
57            let r = Some(self.create_node(val));
58            self.set_root(r);
59        }
60        self.crement_size(1);
61    }
62
63    fn delete(&mut self, val: T) -> bool {
64        if !self.contains(&val) {
65            false
66        } else {
67            let n = self.find(&val);
68            let del = self.delete_replace(n);
69            self.rebalance_del(del, n);
70            self.delete_node(del);
71            self.crement_size(-1);
72            true
73        }
74    }
75
76    fn rotate(&mut self, side: Side, n: usize) {
77        let p = self.get(n).get_parent().expect("P rotate");
78
79        if let Some(c) = self.get(n).get_child(side) {
80            self.attach_child(p, c, !side);
81        } else {
82            match !side {
83                Side::Left => self.get_mut(p).set_child_opt(None, Side::Left),
84                Side::Right => self.get_mut(p).set_child_opt(None, Side::Right),
85            }
86        }
87        if let Some(g) = self.get(p).get_parent() {
88            self.get_mut(n).set_parent(Some(g));
89            let pside = if self.get(p).is_child(Side::Left) {
90                Side::Left
91            } else {
92                Side::Right
93            };
94            self.attach_child(g, n, pside);
95        } else {
96            self.set_root(Some(n));
97            self.get_mut(n).set_parent(None);
98        }
99        self.attach_child(n, p, side);
100    }
101
102    fn find(&self, val: &T) -> usize {
103        let mut n = self.get_root().expect("n find");
104        loop {
105            let node = self.get(n);
106            if node.lesser(val) && node.get_child(Side::Right).is_some() {
107                n = node.get_child(Side::Right).expect("find n right child");
108            } else if node.greater(val) && node.get_child(Side::Left).is_some() {
109                n = node.get_child(Side::Left).expect("find n left child");
110            } else {
111                return n;
112            }
113        }
114    }
115
116    fn get_height(&self) -> usize {
117        if let Some(root) = self.get_root() {
118            self.get(root).get_height()
119        } else {
120            0
121        }
122    }
123
124    fn get_leaf_count(&self) -> usize {
125        if let Some(root) = self.get_root() {
126            self.get(root).get_leaf_count()
127        } else {
128            0
129        }
130    }
131
132    fn to_string(&self) -> String {
133        if let Some(root) = self.get_root() {
134            self.get(root).to_string()
135        } else {
136            String::from("(Empty tree)")
137        }
138    }
139
140    fn to_pretty_string(&self) -> String {
141        if let Some(root) = self.get_root() {
142            self.get(root).to_pretty_string(1)
143        } else {
144            String::from("(Empty tree)")
145        }
146    }
147}
rust_black_trees/tree.rs

rust_black_trees/
tree.rs
