data_structures_lib/
trees.rs1use 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#[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 pub fn new() -> Self {
20 Self { root: None, len: 0 }
21 }
22
23 pub fn len(&self) -> usize {
25 self.len
26 }
27
28 pub fn is_empty(&self) -> bool {
30 self.len == 0
31 }
32
33 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 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 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 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#[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 pub fn new() -> Self {
152 Self { root: None, len: 0 }
153 }
154
155 pub fn len(&self) -> usize {
157 self.len
158 }
159
160 pub fn is_empty(&self) -> bool {
162 self.len == 0
163 }
164
165 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 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 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 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 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}