b_trees/avl/
mod.rs

1//! This module contains the implementation of an AVL tree.
2//!
3//! # Examples
4//!
5//! ```
6//! use avl_tree::AVL;
7//!
8//! let mut tree = AVL::new();
9//!
10//! tree.insert(3);
11//! tree.insert(1);
12//! tree.insert(2);
13//!
14//! assert_eq!(tree.len(), 3);
15//! assert_eq!(tree.height(), 2);
16//!
17//! let mut iter = tree.iter();
18//!
19//! assert_eq!(iter.next(), Some(&1));
20//! assert_eq!(iter.next(), Some(&2));
21//! assert_eq!(iter.next(), Some(&3));
22//! assert_eq!(iter.next(), None);
23//! ```
24
25use std::{collections::LinkedList, fmt::Debug};
26
27use crate::Nearness;
28
29use self::iters::{IntoIncreasing, IntoDecreasing};
30
31use super::Node;
32use iters::{Decreasing, Increasing, Levels, IntoIter, Iter};
33
34mod iters;
35
36/// ## Description
37///
38/// An AVL tree is a self-balancing binary search tree that maintains a height difference of at most 1
39/// between its left and right subtrees. This property ensures that the tree remains balanced,
40/// which in turn guarantees that the time complexities of `insertion`, `deletion`,`lookup` are all `O(log(n))`
41/// Compared to normal binary search trees, AVL trees provide faster lookups and insertions, but
42/// slower deletions. Compared to heaps, AVL trees are more strictly balanced, which makes them
43/// faster for lookups, but slower for insertions and deletions.
44///
45/// ## Time complexities
46///
47/// The following table shows the time complexities of various operations in an AVL tree:
48///
49/// | **Operation** | **Time complexity** |
50/// |---------------|---------------------|
51/// | Insertion     | O(log n)            |
52/// | Deletion      | O(log n)            |
53/// | Lookup        | O(log n)            |
54///
55///
56
57#[derive(Debug, Clone)]
58pub struct AVL<T> {
59    pub(crate) root: Option<Box<Node<T>>>,
60    len: usize,
61}
62
63impl<T> AVL<T> {
64    /// Creates and returns a new AVL tree
65    #[inline]
66    pub fn new() -> Self {
67        Self { root: None, len: 0 }
68    }
69
70    /// Returns the number of nodes in this AVL tree. This operation has a strict time complexity of `O(1)`
71    #[inline]
72    pub fn len(&self) -> usize {
73        self.len
74    }
75
76    #[inline]
77    pub fn height(&self) -> usize {
78        match &self.root {
79            Some(root) => root.height as usize,
80            None => 0,
81        }
82    }
83
84    #[inline]
85    pub fn clear(&mut self) {
86        self.len = 0;
87        self.root = None;
88    }
89
90    #[inline]
91    pub fn levels(&self) -> impl Iterator<Item = impl Iterator<Item = Option<&T>>> {
92        Levels {
93            h_left: self.height(),
94            cur: LinkedList::from_iter(Some(self.root.as_ref())),
95        }
96    }
97
98    #[inline]
99    pub fn iter(&self) -> impl Iterator<Item = &T> {
100        Iter { nodes: LinkedList::from_iter(self.root.as_ref()) }
101    }
102
103    /// Returns an in-order traversal iterator over the elements in the binary tree.
104    /// This ensures the returned values are in an `increasing` order according to their implementation of the `Ord` trait.
105    ///
106    /// Although this implementation does not make the iterator **lazy**, that is, initializing this iterator uses time complexity of O(log(n)), it makes the average time complexity of `next` be amortized O(1) with worst case scenario of O(log(n)) and ratio of average case to worst case is 1: log(n).
107    /// More generally speaking, this implementation performs better than other implementations and also uses no extra space.
108    #[inline]
109    pub fn increasing(&self) -> impl Iterator<Item = &T> {
110        Increasing::new(self.root.as_ref())
111    }
112
113    #[inline]
114    pub fn into_increasing(self) -> impl Iterator<Item = T> {
115        IntoIncreasing::new(self.root)
116    }
117
118    #[inline]
119    pub fn into_decreasing(self) -> impl Iterator<Item = T> {
120        IntoDecreasing::new(self.root)
121    }
122
123    #[inline]
124    pub fn decreasing(&self) -> impl Iterator<Item = &T> {
125        Decreasing::new(self.root.as_ref())
126    }
127
128    #[inline]
129    pub fn is_empty(&self) -> bool {
130        self.len == 0
131    }
132
133}
134
135impl<T: Ord> AVL<T> {
136    #[inline]
137    pub fn insert(&mut self, val: T) {
138        if let Some(root) = &mut self.root {
139            root.insert(val);
140        } else {
141            self.root = Some(Box::new(Node::new(val)))
142        }
143        self.len += 1
144    }
145
146    #[inline]
147    pub fn insert_distinct(&mut self, val: T) -> bool {
148        if let Some(root) = &mut self.root {
149            if root.insert_distinct(val) {
150                self.len += 1;
151                true
152            } else {
153                false
154            }
155        } else {
156            self.root = Some(Box::new(Node::new(val)));
157            self.len += 1;
158            true
159        }
160    }
161
162    #[inline]
163    pub fn delete(&mut self, val: &T) -> bool {
164        let mut con = false;
165        self.root = if let Some(root) = self.root.take() {
166            let (v, val) = root.delete(&val);
167            con = v;
168            val
169        } else {
170            None
171        };
172        if con {
173            self.len -= 1
174        }
175        con
176    }
177
178    #[inline]
179    pub fn union(mut self, mut other: Self) -> Self {
180        if self.len() > other.len() {
181            for val in other {
182                self.insert(val);
183            }
184            self
185        } else {
186            for val in self {
187                other.insert(val);
188            }
189            other
190        }
191    }
192
193    #[inline]
194    pub fn contains(&self, target: &T) -> bool {
195        self.root.as_ref().map(|n| n.contains(target)).unwrap_or(false)
196    }
197
198
199    #[inline]
200    pub fn max(&self) -> Option<&T> {
201        self.root.as_ref().map(|r| r.find_max())
202    }
203
204    /// traverses the binary search tree and returns the minimum value.
205    #[inline]
206    pub fn min(&self) -> Option<&T> {
207        self.root.as_ref().map(|r| r.find_min())
208    }
209
210    #[inline]
211    pub fn nearest_to<'a, F>(&'a self, target: &'a T, by: F) -> Option<&'a T>
212    where
213        F: 'static + Fn(&'a T, &'a T) -> &'a T,
214        T: 'a,
215    {
216        self.root.as_ref().map(|r| r.nearest_to(target, &by))
217    }
218
219    #[inline]
220    pub fn farthest_to<'a, F>(&'a self, target: &'a T, by: F) -> Option<&'a T>
221    where
222        F: 'static + Fn(&'a T, &'a T) -> &'a T,
223        T: 'a,
224    {
225        self.root.as_ref().map(|r| r.farthest_to(target, &by))
226    }
227    
228    pub fn greater_than<'a>(&'a self, lower: &'a T) -> impl Iterator<Item = &'a T> {
229        self.increasing().skip_while(|&v| v <= lower)
230    }
231
232    pub fn less_than<'a>(&'a self, upper: &'a T) -> impl Iterator<Item = &'a T> {
233        self.decreasing().skip_while(|&v| v >= upper)
234    }
235}
236
237impl<T: Ord + Nearness> AVL<T> {
238    #[inline]
239    pub fn nearest<'a>(&'a self, target: &'a T) -> Option<&'a T> {
240        self.root
241            .as_ref()
242            .map(|r| r.nearest_to(target, &move |a, b| T::nearer(a, b, target)))
243    }
244
245    #[inline]
246    pub fn farthest<'a>(&'a self, target: &'a T) -> Option<&'a T> {
247        self.root
248            .as_ref()
249            .map(|r| r.farthest_to(target, &move |a, b| T::farther(a, b, target)))
250    }
251}
252
253impl<T> IntoIterator for AVL<T> {
254    type IntoIter = IntoIter<T>;
255    type Item = T;
256    fn into_iter(self) -> Self::IntoIter {
257        IntoIter {
258            nodes: LinkedList::from_iter(self.root)
259        }
260    }
261}
262
263impl<T: Ord> FromIterator<T> for AVL<T> {
264    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
265        let mut avl = Self::new();
266        for val in iter {
267            avl.insert(val)
268        }
269        avl
270    }
271}
b_trees/avl/mod.rs

b_trees/avl/
mod.rs
