Skip to main content

data_structures_lib/
trees.rs

1use crate::Error;
2
3#[derive(Debug)]
4struct BstNode<T: Ord + Clone> {
5    value: T,
6    left: Option<Box<BstNode<T>>>,
7    right: Option<Box<BstNode<T>>>,
8}
9
10/// A binary search tree.
11#[derive(Debug)]
12pub struct BinarySearchTree<T: Ord + Clone> {
13    root: Option<Box<BstNode<T>>>,
14    len: usize,
15}
16
17impl<T: Ord + Clone> BinarySearchTree<T> {
18    /// Creates a new BinarySearchTree.
19    pub fn new() -> Self {
20        Self { root: None, len: 0 }
21    }
22
23    /// Returns the number of elements.
24    pub fn len(&self) -> usize {
25        self.len
26    }
27
28    /// Returns true if the tree is empty.
29    pub fn is_empty(&self) -> bool {
30        self.len == 0
31    }
32
33    /// Inserts a value, ignoring duplicates.
34    pub fn insert(&mut self, value: T) {
35        if self.search(&value) {
36            return;
37        }
38        self.root = Some(Self::insert_node(self.root.take(), value));
39        self.len += 1;
40    }
41
42    fn insert_node(node: Option<Box<BstNode<T>>>, value: T) -> Box<BstNode<T>> {
43        match node {
44            None => Box::new(BstNode {
45                value,
46                left: None,
47                right: None,
48            }),
49            Some(mut n) => {
50                if value < n.value {
51                    n.left = Some(Self::insert_node(n.left.take(), value));
52                } else if value > n.value {
53                    n.right = Some(Self::insert_node(n.right.take(), value));
54                }
55                n
56            }
57        }
58    }
59
60    /// Deletes a value.
61    pub fn delete(&mut self, value: &T) -> Result<(), Error> {
62        if !self.search(value) {
63            return Err(Error::NotFound);
64        }
65        self.root = Self::delete_node(self.root.take(), value);
66        self.len -= 1;
67        Ok(())
68    }
69
70    fn delete_node(node: Option<Box<BstNode<T>>>, value: &T) -> Option<Box<BstNode<T>>> {
71        let mut n = node?;
72        if value < &n.value {
73            n.left = Self::delete_node(n.left.take(), value);
74        } else if value > &n.value {
75            n.right = Self::delete_node(n.right.take(), value);
76        } else {
77            if n.left.is_none() {
78                return n.right;
79            }
80            if n.right.is_none() {
81                return n.left;
82            }
83            let successor = Self::min_node(n.right.as_ref().unwrap()).value.clone();
84            n.value = successor;
85            n.right = Self::delete_node(n.right.take(), &n.value);
86        }
87        Some(n)
88    }
89
90    fn min_node(node: &BstNode<T>) -> &BstNode<T> {
91        match &node.left {
92            Some(left) => Self::min_node(left),
93            None => node,
94        }
95    }
96
97    /// Returns true if the value exists.
98    pub fn search(&self, value: &T) -> bool {
99        let mut current = &self.root;
100        while let Some(n) = current {
101            if value == &n.value {
102                return true;
103            } else if value < &n.value {
104                current = &n.left;
105            } else {
106                current = &n.right;
107            }
108        }
109        false
110    }
111
112    /// Returns the values in in-order sorted order.
113    pub fn in_order(&self) -> Vec<T> {
114        let mut result = Vec::with_capacity(self.len);
115        Self::in_order_node(&self.root, &mut result);
116        result
117    }
118
119    fn in_order_node(node: &Option<Box<BstNode<T>>>, result: &mut Vec<T>) {
120        if let Some(n) = node {
121            Self::in_order_node(&n.left, result);
122            result.push(n.value.clone());
123            Self::in_order_node(&n.right, result);
124        }
125    }
126}
127
128impl<T: Ord + Clone> Default for BinarySearchTree<T> {
129    fn default() -> Self {
130        Self::new()
131    }
132}
133
134#[derive(Debug)]
135struct AvlNode<T: Ord + Clone> {
136    value: T,
137    left: Option<Box<AvlNode<T>>>,
138    right: Option<Box<AvlNode<T>>>,
139    height: i32,
140}
141
142/// A self-balancing AVL tree.
143#[derive(Debug)]
144pub struct AvlTree<T: Ord + Clone> {
145    root: Option<Box<AvlNode<T>>>,
146    len: usize,
147}
148
149impl<T: Ord + Clone> AvlTree<T> {
150    /// Creates a new AvlTree.
151    pub fn new() -> Self {
152        Self { root: None, len: 0 }
153    }
154
155    /// Returns the number of elements.
156    pub fn len(&self) -> usize {
157        self.len
158    }
159
160    /// Returns true if the tree is empty.
161    pub fn is_empty(&self) -> bool {
162        self.len == 0
163    }
164
165    /// Returns the height of the tree.
166    pub fn height(&self) -> i32 {
167        Self::height_node(&self.root)
168    }
169
170    fn height_node(node: &Option<Box<AvlNode<T>>>) -> i32 {
171        match node {
172            None => 0,
173            Some(n) => n.height,
174        }
175    }
176
177    fn update_height(n: &mut AvlNode<T>) {
178        n.height = 1
179            + std::cmp::max(
180                Self::height_node(&n.left),
181                Self::height_node(&n.right),
182            );
183    }
184
185    fn balance_factor(n: &AvlNode<T>) -> i32 {
186        Self::height_node(&n.left) - Self::height_node(&n.right)
187    }
188
189    fn right_rotate(mut y: Box<AvlNode<T>>) -> Box<AvlNode<T>> {
190        let mut x = y.left.take().unwrap();
191        let t2 = x.right.take();
192        x.right = Some(y);
193        x.right.as_mut().unwrap().left = t2;
194        Self::update_height(x.right.as_mut().unwrap());
195        Self::update_height(&mut x);
196        x
197    }
198
199    fn left_rotate(mut x: Box<AvlNode<T>>) -> Box<AvlNode<T>> {
200        let mut y = x.right.take().unwrap();
201        let t2 = y.left.take();
202        y.left = Some(x);
203        y.left.as_mut().unwrap().right = t2;
204        Self::update_height(y.left.as_mut().unwrap());
205        Self::update_height(&mut y);
206        y
207    }
208
209    /// Inserts a value, ignoring duplicates.
210    pub fn insert(&mut self, value: T) {
211        if self.search(&value) {
212            return;
213        }
214        self.root = Some(Self::insert_node(self.root.take(), value));
215        self.len += 1;
216    }
217
218    fn insert_node(node: Option<Box<AvlNode<T>>>, value: T) -> Box<AvlNode<T>> {
219        match node {
220            None => Box::new(AvlNode {
221                value,
222                left: None,
223                right: None,
224                height: 1,
225            }),
226            Some(mut n) => {
227                if value < n.value {
228                    n.left = Some(Self::insert_node(n.left.take(), value.clone()));
229                } else if value > n.value {
230                    n.right = Some(Self::insert_node(n.right.take(), value.clone()));
231                } else {
232                    return n;
233                }
234                Self::update_height(&mut n);
235                let balance = Self::balance_factor(&n);
236
237                if balance > 1 && value < n.left.as_ref().unwrap().value {
238                    return Self::right_rotate(n);
239                }
240                if balance < -1 && value > n.right.as_ref().unwrap().value {
241                    return Self::left_rotate(n);
242                }
243                if balance > 1 && value > n.left.as_ref().unwrap().value {
244                    n.left = Some(Self::left_rotate(n.left.take().unwrap()));
245                    return Self::right_rotate(n);
246                }
247                if balance < -1 && value < n.right.as_ref().unwrap().value {
248                    n.right = Some(Self::right_rotate(n.right.take().unwrap()));
249                    return Self::left_rotate(n);
250                }
251                n
252            }
253        }
254    }
255
256    /// Deletes a value.
257    pub fn delete(&mut self, value: &T) -> Result<(), Error> {
258        if !self.search(value) {
259            return Err(Error::NotFound);
260        }
261        self.root = Self::delete_node(self.root.take(), value);
262        self.len -= 1;
263        Ok(())
264    }
265
266    fn delete_node(node: Option<Box<AvlNode<T>>>, value: &T) -> Option<Box<AvlNode<T>>> {
267        let mut n = node?;
268        if value < &n.value {
269            n.left = Self::delete_node(n.left.take(), value);
270        } else if value > &n.value {
271            n.right = Self::delete_node(n.right.take(), value);
272        } else {
273            if n.left.is_none() || n.right.is_none() {
274                let temp = if n.left.is_some() { n.left } else { n.right };
275                return temp;
276            }
277            let successor = Self::min_value_node(n.right.as_ref().unwrap()).value.clone();
278            n.value = successor;
279            n.right = Self::delete_node(n.right.take(), &n.value);
280        }
281
282        Self::update_height(&mut n);
283        let balance = Self::balance_factor(&n);
284
285        if balance > 1 && Self::balance_factor(n.left.as_ref().unwrap()) >= 0 {
286            return Some(Self::right_rotate(n));
287        }
288        if balance > 1 && Self::balance_factor(n.left.as_ref().unwrap()) < 0 {
289            n.left = Some(Self::left_rotate(n.left.take().unwrap()));
290            return Some(Self::right_rotate(n));
291        }
292        if balance < -1 && Self::balance_factor(n.right.as_ref().unwrap()) <= 0 {
293            return Some(Self::left_rotate(n));
294        }
295        if balance < -1 && Self::balance_factor(n.right.as_ref().unwrap()) > 0 {
296            n.right = Some(Self::right_rotate(n.right.take().unwrap()));
297            return Some(Self::left_rotate(n));
298        }
299        Some(n)
300    }
301
302    fn min_value_node(node: &AvlNode<T>) -> &AvlNode<T> {
303        match &node.left {
304            Some(left) => Self::min_value_node(left),
305            None => node,
306        }
307    }
308
309    /// Returns true if the value exists.
310    pub fn search(&self, value: &T) -> bool {
311        let mut current = &self.root;
312        while let Some(n) = current {
313            if value == &n.value {
314                return true;
315            } else if value < &n.value {
316                current = &n.left;
317            } else {
318                current = &n.right;
319            }
320        }
321        false
322    }
323
324    /// Returns the values in in-order sorted order.
325    pub fn in_order(&self) -> Vec<T> {
326        let mut result = Vec::with_capacity(self.len);
327        Self::in_order_node(&self.root, &mut result);
328        result
329    }
330
331    fn in_order_node(node: &Option<Box<AvlNode<T>>>, result: &mut Vec<T>) {
332        if let Some(n) = node {
333            Self::in_order_node(&n.left, result);
334            result.push(n.value.clone());
335            Self::in_order_node(&n.right, result);
336        }
337    }
338}
339
340impl<T: Ord + Clone> Default for AvlTree<T> {
341    fn default() -> Self {
342        Self::new()
343    }
344}