binary_search_tree/lib.rs
1//! This module contains an implementation of a classic binary search tree
2//! with a large set of methods, including view iterators.
3
4use std::fmt;
5use std::cmp::{ Ordering, PartialEq };
6use std::iter::{ FromIterator, Extend };
7use std::collections::VecDeque;
8
9/// In this crate, binary search trees store only one valuable value, which is also
10/// used as a key, so all elements must have the ```Ord``` trait implementation.
11///
12/// # Examples
13///
14/// ```
15/// extern crate binary_search_tree;
16///
17/// use binary_search_tree::BinarySearchTree;
18///
19/// // Create a new binary search tree and fill it with numbers from 1 to 5:
20/// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
21/// for i in vec![3, 1, 2, 5, 4] {
22/// tree.insert(i);
23/// }
24///
25/// // Get them in sorted order
26/// assert_eq!(tree.sorted_vec(), vec![&1, &2, &3, &4, &5]);
27///
28/// // Let's extract the minimum and maximum.
29/// assert_eq!(tree.extract_min(), Some(1));
30/// assert_eq!(tree.extract_max(), Some(5));
31/// assert_eq!(tree.sorted_vec(), vec![&2, &3, &4]);
32///
33/// // We can also extend the tree with elements from the iterator.
34/// tree.extend((0..6).map(|x| if x%2 == 0 { x } else { -x }));
35/// assert_eq!(tree.len(), 9);
36///
37/// // If the elements must be unique, you should use insert_without_dup().
38/// tree.insert_without_dup(0);
39/// assert_eq!(tree.len(), 9);
40///
41/// // Delete the value 0 from the tree and make sure that the deletion actually occurred.
42/// tree.remove(&0);
43/// assert!(!tree.contains(&0));
44///
45/// // We can clear the tree of any remaining items.
46/// tree.clear();
47///
48/// // The tree should now be empty.
49/// assert!(tree.is_empty());
50/// ```
51
52
53#[derive(Debug)]
54pub struct BinarySearchTree<T: Ord> {
55 root: Tree<T>,
56 pub size: usize,
57}
58
59#[derive(Debug)]
60struct Node<T: Ord> {
61 value: T,
62 left: Tree<T>,
63 right: Tree<T>,
64}
65
66#[derive(Debug)]
67struct Tree<T: Ord>(Option<Box<Node<T>>>);
68
69
70impl<T: Ord> PartialEq for BinarySearchTree<T> {
71 fn eq(&self, other: &BinarySearchTree<T>) -> bool {
72 self.sorted_vec() == other.sorted_vec()
73 }
74}
75
76impl<T: Ord + fmt::Debug> fmt::Display for BinarySearchTree<T> {
77 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
78 write!(f, "{:?}", self.sorted_vec())
79 }
80}
81
82impl<T: Ord> Extend<T> for BinarySearchTree<T> {
83 /// Extend bst with elements from the iterator.
84 ///
85 /// Note: extend doesn't keep track of duplicates, but just uses the whole iterator.
86 ///
87 /// # Examples
88 ///
89 /// ```
90 /// use binary_search_tree::BinarySearchTree;
91 /// use std::iter::Extend;
92 ///
93 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
94 /// tree.extend(vec![7, 1, 0, 4, 5, 3].into_iter());
95 /// assert_eq!(tree.sorted_vec(), [&0, &1, &3, &4, &5, &7]);
96 /// ```
97 fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
98 iter.into_iter().for_each(move |elem| {
99 self.insert(elem);
100 });
101 }
102}
103
104impl<T: Ord> FromIterator<T> for BinarySearchTree<T> {
105 /// Сreating a bst from an iterator.
106 ///
107 /// # Examples
108 ///
109 /// ```
110 /// use binary_search_tree::BinarySearchTree;
111 /// use std::iter::FromIterator;
112 ///
113 /// let tree: BinarySearchTree<i32> = BinarySearchTree::from_iter(
114 /// vec![7, 1, 0, 4, 5, 3].into_iter());
115 /// assert_eq!(tree.sorted_vec(), [&0, &1, &3, &4, &5, &7]);
116 ///
117 /// let tree: BinarySearchTree<i32> = vec![7, 1, 0, 4, 5, 3].into_iter().collect();
118 /// assert_eq!(tree.sorted_vec(), [&0, &1, &3, &4, &5, &7]);
119 /// ```
120 fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
121 let mut tree = BinarySearchTree::new();
122 tree.extend(iter);
123 tree
124 }
125}
126
127impl<T: Ord + Clone> Clone for BinarySearchTree<T> {
128 fn clone(&self) -> BinarySearchTree<T> {
129 let mut new_tree = BinarySearchTree::new();
130
131 for elem in self.sorted_vec().iter() {
132 new_tree.insert((*elem).clone());
133 }
134
135 new_tree
136 }
137}
138
139
140impl<T: Ord> BinarySearchTree<T> {
141 /// Makes a new empty BST.
142 ///
143 /// Does not allocate anything on its own.
144 ///
145 /// # Examples
146 ///
147 /// ```
148 /// use binary_search_tree::BinarySearchTree;
149 ///
150 /// // New bst that will be contains i32
151 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
152 /// ```
153 pub fn new() -> Self {
154 BinarySearchTree { root: Tree(None), size: 0 }
155 }
156
157 /// Сhecking if the tree is empty.
158 ///
159 /// # Examples
160 ///
161 /// ```
162 /// use binary_search_tree::BinarySearchTree;
163 ///
164 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
165 /// assert!(tree.is_empty());
166 ///
167 /// tree.insert(1);
168 /// assert!(!tree.is_empty());
169 /// ```
170 pub fn is_empty(&self) -> bool {
171 self.size == 0
172 }
173
174 /// Returns the number of elements in the tree.
175 ///
176 /// # Examples
177 ///
178 /// ```
179 /// use binary_search_tree::BinarySearchTree;
180 ///
181 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
182 /// assert_eq!(tree.len(), 0);
183 /// tree.insert(1);
184 /// assert_eq!(tree.len(), 1);
185 /// ```
186 pub fn len(&self) -> usize {
187 self.size
188 }
189
190 /// Clears the binary search tree, removing all elements.
191 ///
192 /// # Examples
193 /// ```
194 /// use binary_search_tree::BinarySearchTree;
195 ///
196 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
197 /// tree.insert(1);
198 /// tree.clear();
199 /// assert!(tree.is_empty());
200 /// ```
201 pub fn clear(&mut self) {
202 *self = BinarySearchTree::new();
203 }
204
205 /// Viewing the root element of the tree.
206 ///
207 /// # Examples
208 ///
209 /// ```
210 /// use binary_search_tree::BinarySearchTree;
211 ///
212 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
213 /// assert!(tree.root().is_none()); // is empty
214 ///
215 /// tree.insert(1); tree.insert(0); tree.insert(2);
216 ///
217 /// // the first element inserted becomes the root
218 /// assert_eq!(tree.root(), Some(&1));
219 /// ```
220 pub fn root(&self) -> Option<&T> {
221 self.root.0.as_ref().map(|node| &node.value)
222 }
223
224 /// Inserting a new element.
225 ///
226 /// Returns true if an element with the same value already exists in the tree, false otherwise.
227 ///
228 /// # Examples
229 ///
230 /// ```
231 /// use binary_search_tree::BinarySearchTree;
232 ///
233 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
234 ///
235 /// assert!(!tree.insert(1));
236 /// assert!(!tree.insert(0));
237 /// assert!(!tree.insert(2));
238 /// assert!(tree.insert(1)); // element 1 is already in the tree
239 ///
240 /// assert_eq!(tree.size, 4);
241 ///
242 /// // Elements in sorted order (inorder traversal)
243 /// assert_eq!(tree.sorted_vec(), vec![&0, &1, &1, &2]);
244 /// ```
245 pub fn insert(&mut self, value: T) -> bool {
246 self.size += 1;
247 self.root.insert(value, true)
248 }
249
250 /// Inserting a new unique element.
251 ///
252 /// If an element with the same value is already in the tree, the insertion will not happen.
253 /// Returns true if an element with the same value already exists in the tree, false otherwise.
254 ///
255 /// # Examples
256 ///
257 /// ```
258 /// use binary_search_tree::BinarySearchTree;
259 ///
260 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
261 ///
262 /// assert!(!tree.insert_without_dup(1));
263 /// assert!(!tree.insert_without_dup(0));
264 /// assert!(!tree.insert_without_dup(2));
265 /// assert!(tree.insert_without_dup(1)); // element 1 is already in the tree
266 ///
267 /// assert_eq!(tree.size, 3);
268 ///
269 /// // Elements in sorted order (inorder traversal)
270 /// assert_eq!(tree.sorted_vec(), vec![&0, &1, &2]);
271 /// ```
272 pub fn insert_without_dup(&mut self, value: T) -> bool {
273 let res = self.root.insert(value, false);
274 if !res {
275 self.size += 1;
276 }
277 res
278 }
279
280 /// Checks whether the tree contains an element with the specified value.
281 ///
282 /// # Examples
283 ///
284 /// ```
285 /// use binary_search_tree::BinarySearchTree;
286 ///
287 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
288 /// assert_eq!(tree.contains(&1), false);
289 ///
290 /// tree.insert(1); tree.insert(0); tree.insert(2); tree.insert(1);
291 ///
292 /// // The contains() method accepts a reference to a value
293 /// assert!(tree.contains(&2));
294 /// assert!(tree.contains(&1));
295 /// assert!(!tree.contains(&999));
296 /// ```
297 pub fn contains(&self, target: &T) -> bool {
298 self.root.contains(target)
299 }
300
301 /// The minimum element of the tree.
302 ///
303 /// Returns a reference to the minimum element.
304 ///
305 /// # Examples
306 ///
307 /// ```
308 /// use binary_search_tree::BinarySearchTree;
309 ///
310 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
311 /// assert_eq!(tree.min(), None);
312 ///
313 /// tree.insert(1); tree.insert(0); tree.insert(2); tree.insert(1);
314 /// assert_eq!(tree.min(), Some(&0));
315 pub fn min(&self) -> Option<&T> {
316 self.root.min()
317 }
318
319 /// The maximum element of the tree.
320 ///
321 /// Returns a reference to the maximum element.
322 ///
323 /// # Examples
324 ///
325 /// ```
326 /// use binary_search_tree::BinarySearchTree;
327 ///
328 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
329 /// assert_eq!(tree.max(), None);
330 ///
331 /// tree.insert(1); tree.insert(0); tree.insert(2); tree.insert(1);
332 /// assert_eq!(tree.max(), Some(&2));
333 /// ```
334 pub fn max(&self) -> Option<&T> {
335 self.root.max()
336 }
337
338 /// Inorder successor of the element with the specified value
339 ///
340 /// In Binary Search Tree, inorder successor of an input node can be defined as
341 /// the node with the smallest value greater than the value of the input node.
342 /// In another way, we can say that the successor of element x is the element
343 /// immediately following it in sorted order.
344 ///
345 /// # Examples
346 ///
347 /// ```
348 /// use binary_search_tree::BinarySearchTree;
349 ///
350 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
351 /// tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10);
352 /// tree.insert(18); tree.insert(45); tree.insert(35);
353 ///
354 /// // We have a binary tree with the following structure:
355 /// // 25
356 /// // 15 40
357 /// // 10 18 35 45
358 ///
359 /// assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &25, &35, &40, &45]);
360 ///
361 /// // and successor of 25 will be element 35.
362 /// assert_eq!(tree.successor(&25), Some(&35));
363 ///
364 /// assert_eq!(tree.successor(&40), Some(&45));
365 /// assert!(tree.successor(&45).is_none()); // Element 45 has no successors
366 ///
367 /// // We can also find successors for missing values in the tree
368 /// assert_eq!(tree.successor(&20), Some(&25)); // [..., &18, vv &20 vv, &25, ...]
369 /// ```
370 pub fn successor(&self, val: &T) -> Option<&T> {
371 self.root.successor(val)
372 }
373
374 /// Inorder predecessor of the element with the specified value
375 ///
376 /// In Binary Search Tree, inorder predecessor of an input node can be defined as
377 /// the node with the greatest value smaller than the value of the input node.
378 /// In another way, we can say that the predecessor of element x is the element
379 /// immediately preceding it in sorted order.
380 ///
381 /// # Examples
382 ///
383 /// ```
384 /// use binary_search_tree::BinarySearchTree;
385 ///
386 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
387 /// tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10);
388 /// tree.insert(18); tree.insert(45); tree.insert(35);
389 ///
390 /// // We have a binary tree with the following structure:
391 /// // 25
392 /// // 15 40
393 /// // 10 18 35 45
394 ///
395 /// assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &25, &35, &40, &45]);
396 ///
397 /// // and predecessor of 25 will be element 35.
398 /// assert_eq!(tree.predecessor(&25), Some(&18));
399 ///
400 /// assert_eq!(tree.predecessor(&40), Some(&35));
401 /// assert!(tree.predecessor(&10).is_none()); // Element 10 has no predecessors
402 ///
403 /// // We can also find predecessors for missing values in the tree
404 /// assert_eq!(tree.predecessor(&20), Some(&18)); // [..., &18, vv &20 vv, &25, ...]
405 /// ```
406 pub fn predecessor(&self, val: &T) -> Option<&T> {
407 self.root.predecessor(val)
408 }
409
410 /// Remove and return the minimum element.
411 ///
412 /// This operation is much more efficient than searching for the
413 /// minimum and then deleting it, since only one pass is performed
414 /// and there are no comparisons between elements at all.
415 ///
416 /// # Examples
417 ///
418 /// ```
419 /// use binary_search_tree::BinarySearchTree;
420 ///
421 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
422 /// assert!(tree.extract_min().is_none());
423 ///
424 /// tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10);
425 ///
426 /// assert_eq!(tree.extract_min(), Some(10));
427 /// assert_eq!(tree.extract_min(), Some(15));
428 ///
429 /// assert_eq!(tree.sorted_vec(), vec![&25, &40]);
430 /// ```
431 pub fn extract_min(&mut self) -> Option<T> {
432 let res = self.root.extract_min();
433 if res.is_some() {
434 self.size -= 1;
435 }
436 res
437 }
438
439 /// Remove and return the maximum element.
440 ///
441 /// This operation is much more efficient than searching for the
442 /// maximum and then deleting it, since only one pass is performed
443 /// and there are no comparisons between elements at all.
444 ///
445 /// # Examples
446 ///
447 /// ```
448 /// use binary_search_tree::BinarySearchTree;
449 ///
450 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
451 /// assert!(tree.extract_max().is_none());
452 ///
453 /// tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10);
454 ///
455 /// assert_eq!(tree.extract_max(), Some(40));
456 /// assert_eq!(tree.extract_max(), Some(25));
457 ///
458 /// assert_eq!(tree.sorted_vec(), vec![&10, &15]);
459 /// ```
460 pub fn extract_max(&mut self) -> Option<T> {
461 let res = self.root.extract_max();
462 if res.is_some() {
463 self.size -= 1;
464 }
465 res
466 }
467
468 /// Remove the first occurrence of an element with the target value.
469 ///
470 /// Returns true if deletion occurred and false if target is missing from the tree.
471 ///
472 /// # Examples
473 ///
474 /// ```
475 /// use binary_search_tree::BinarySearchTree;
476 ///
477 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
478 /// tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10);
479 /// tree.insert(18); tree.insert(45); tree.insert(35); tree.insert(18);
480 ///
481 /// assert!(tree.remove(&18));
482 /// assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &25, &35, &40, &45]);
483 /// assert_eq!(tree.size, 7);
484 ///
485 /// tree.remove(&25);
486 /// assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &35, &40, &45]);
487 /// assert_eq!(tree.size, 6);
488 ///
489 /// // If you try to delete a value that is missing from the tree, nothing will change
490 /// assert!(!tree.remove(&99));
491 /// assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &35, &40, &45]);
492 /// assert_eq!(tree.size, 6);
493 /// ```
494 pub fn remove(&mut self, target: &T) -> bool {
495 let res = self.root.remove(target);
496 if res {
497 self.size -= 1;
498 }
499 res
500 }
501
502 /// Vector of references to elements in the tree in non-decreasing order.
503 ///
504 /// # Examples
505 ///
506 /// ```
507 /// use binary_search_tree::BinarySearchTree;
508 ///
509 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
510 /// tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10);
511 /// tree.insert(18); tree.insert(45); tree.insert(35); tree.insert(18);
512 ///
513 /// assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &18, &25, &35, &40, &45]);
514 /// ```
515 pub fn sorted_vec(&self) -> Vec<&T> {
516 self.root.sorted_vec()
517 }
518
519 /// Moving the tree to a sorted vector.
520 ///
521 /// # Examples
522 ///
523 /// ```
524 /// use binary_search_tree::BinarySearchTree;
525 ///
526 /// let tree: BinarySearchTree<i32> = BinarySearchTree::new();
527 ///
528 /// let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
529 /// tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10);
530 ///
531 ///assert_eq!(tree.into_sorted_vec(), vec![10, 15, 25, 40]);
532 /// ```
533 pub fn into_sorted_vec(self) -> Vec<T> {
534 self.root.into_sorted_vec()
535 }
536
537 /// Inorder traverse iterator of binary search tree.
538 ///
539 /// # Examples
540 ///
541 /// ```
542 /// use binary_search_tree::BinarySearchTree;
543 ///
544 /// let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect();
545 /// // Now we have a tree that looks like this:
546 /// // 5
547 /// // 3 7
548 /// // 1 4 6 8
549 ///
550 /// // And we should get the following sequence of its elements: 1, 3, 4, 5, 6, 7, 8
551 /// assert_eq!(tree.inorder().collect::<Vec<&i32>>(), vec![&1, &3, &4, &5, &6, &7, &8]);
552 /// ```
553 pub fn inorder(&self) -> InorderTraversal<T> {
554 InorderTraversal {
555 stack: Vec::new(),
556 current: self.root.0.as_ref(),
557 }
558 }
559
560 /// Reverse order traverse iterator of binary search tree.
561 ///
562 /// This iterator traverses the elements of the tree in descending order.
563 ///
564 /// # Examples
565 ///
566 /// ```
567 /// use binary_search_tree::BinarySearchTree;
568 ///
569 /// let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect();
570 /// // Now we have a tree that looks like this:
571 /// // 5
572 /// // 3 7
573 /// // 1 4 6 8
574 ///
575 /// // And we should get the following sequence of its elements: 8, 7, 6, 5, 4, 3, 1
576 /// assert_eq!(tree.reverse_order().collect::<Vec<&i32>>(), vec![&8, &7, &6, &5, &4, &3, &1]);
577 /// ```
578 pub fn reverse_order(&self) -> ReverseOrderTraversal<T> {
579 ReverseOrderTraversal {
580 stack: Vec::new(),
581 current: self.root.0.as_ref(),
582 }
583 }
584
585 /// Preorder traverse iterator of binary search tree.
586 ///
587 /// # Examples
588 ///
589 /// ```
590 /// use binary_search_tree::BinarySearchTree;
591 ///
592 /// let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect();
593 /// // Now we have a tree that looks like this:
594 /// // 5
595 /// // 3 7
596 /// // 1 4 6 8
597 ///
598 /// // And we should get the following sequence of its elements: 5, 3, 1, 4, 7, 6, 8
599 /// assert_eq!(tree.preorder().collect::<Vec<&i32>>(), vec![&5, &3, &1, &4, &7, &6, &8]);
600 /// ```
601 pub fn preorder(&self) -> PreorderTraversal<T> {
602 PreorderTraversal {
603 stack: vec![self.root.0.as_ref()],
604 current: self.root.0.as_ref(),
605 }
606 }
607
608 /// Postorder traverse iterator of binary search tree.
609 ///
610 /// # Examples
611 ///
612 /// ```
613 /// use binary_search_tree::BinarySearchTree;
614 ///
615 /// let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect();
616 /// // Now we have a tree that looks like this:
617 /// // 5
618 /// // 3 7
619 /// // 1 4 6 8
620 ///
621 /// // And we should get the following sequence of its elements: 1, 4, 3, 6, 8, 7, 5
622 /// assert_eq!(tree.postorder().collect::<Vec<&i32>>(), vec![&1, &4, &3, &6, &8, &7, &5]);
623 /// ```
624 pub fn postorder(&self) -> PostorderTraversal<T> {
625 PostorderTraversal {
626 stack: Vec::new(),
627 current: self.root.0.as_ref(),
628 }
629 }
630
631 /// Level order binary tree traversal.
632 /// # Examples
633 ///
634 /// ```
635 /// use binary_search_tree::BinarySearchTree;
636 ///
637 /// let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect();
638 /// // Now we have a tree that looks like this:
639 /// // 5
640 /// // 3 7
641 /// // 1 4 6 8
642 ///
643 /// // And we should get the following sequence of its elements: 5, 3, 7, 1, 4, 6, 8
644 /// assert_eq!(tree.level_order().collect::<Vec<&i32>>(), vec![&5, &3, &7, &1, &4, &6, &8]);
645 /// ```
646 pub fn level_order(&self) -> LevelOrderTraversal<T> {
647 let mut deque = VecDeque::new();
648 if let Some(root) = self.root.0.as_ref() {
649 deque.push_back(root);
650 }
651 LevelOrderTraversal { deque: deque }
652 }
653}
654
655
656impl<T: Ord> Node<T> {
657 pub fn new(value: T) -> Self {
658 Node {
659 value: value,
660 left: Tree(None),
661 right: Tree(None),
662 }
663 }
664}
665
666
667impl<T: Ord> Tree<T> {
668 /// Inserting a new element in the tree
669 /// Returns true if an element with the same value already exists in the tree
670 pub fn insert(&mut self, value: T, allow_duplicate: bool) -> bool {
671 let mut current = self;
672 let mut is_duplicate = false;
673
674 // Follow from the root to the leaves in search of a place to insert
675 while let Some(ref mut node) = current.0 {
676 match node.value.cmp(&value) {
677 Ordering::Greater => current = &mut node.left,
678 Ordering::Less => current = &mut node.right,
679 Ordering::Equal => {
680 if allow_duplicate {
681 is_duplicate = true;
682 current = &mut node.right;
683 } else {
684 return true;
685 }
686 }
687 }
688 }
689
690 // A suitable position is found, replace None with a new node
691 current.0 = Some(Box::new(Node::new(value)));
692
693 is_duplicate
694 }
695
696 /// Checks whether the tree contains an element with the specified value
697 pub fn contains(&self, target: &T) -> bool {
698 let mut current = self;
699
700 // Follow from the root to the leaves in search of the set value
701 while let Some(ref node) = current.0 {
702 match node.value.cmp(target) {
703 Ordering::Greater => current = &node.left,
704 Ordering::Less => current = &node.right,
705 Ordering::Equal => return true,
706 }
707 }
708
709 false
710 }
711
712 /// The minimum element of the tree
713 pub fn min(&self) -> Option<&T> {
714 if self.0.is_some() {
715
716 let mut current = self.0.as_ref();
717 let mut left = current.unwrap().left.0.as_ref();
718
719 while let Some(node) = left {
720 current = left;
721 left = node.left.0.as_ref();
722 }
723
724 current.map(|node| &node.value)
725
726 } else {
727 None
728 }
729 }
730
731 /// The maximum element of the tree
732 pub fn max(&self) -> Option<&T> {
733 if self.0.is_some() {
734
735 let mut current = self.0.as_ref();
736 let mut right = current.unwrap().right.0.as_ref();
737
738 while let Some(node) = right {
739 current = right;
740 right = node.right.0.as_ref();
741 }
742
743 current.map(|node| &node.value)
744
745 } else {
746 None
747 }
748 }
749
750 /// Inorder successor of the element with the specified value
751 pub fn successor(&self, val: &T) -> Option<&T> {
752 let mut current = self.0.as_ref();
753 let mut successor = None;
754
755 while current.is_some() {
756 let node = current.unwrap();
757
758 if node.value > *val {
759 successor = current;
760 current = node.left.0.as_ref();
761 } else {
762 current = node.right.0.as_ref();
763 }
764 }
765
766 successor.map(|node| &node.value)
767 }
768
769 /// Inorder predecessor of the element with the specified value
770 pub fn predecessor(&self, val: &T) -> Option<&T> {
771 let mut current = self.0.as_ref();
772 let mut predecessor = None;
773
774 while current.is_some() {
775 let node = current.unwrap();
776 if node.value < *val {
777 predecessor = current;
778 current = node.right.0.as_ref();
779 } else {
780 current = node.left.0.as_ref();
781 }
782 }
783
784 predecessor.map(|node| &node.value)
785 }
786
787 /// Remove and return the minimum element
788 pub fn extract_min(&mut self) -> Option<T> {
789 let mut to_return = None;
790
791 if self.0.is_some() {
792 let mut current = self;
793
794 // Finding the last non-empty node in the left branch
795 while current.0.as_ref().unwrap().left.0.is_some() {
796 current = &mut current.0.as_mut().unwrap().left;
797 }
798
799 // The minimum element is replaced by its right child (the right child can be empty)
800 let node = current.0.take().unwrap();
801 to_return = Some(node.value);
802 current.0 = node.right.0;
803 }
804
805 to_return
806 }
807
808 /// Remove and return the maximum element
809 pub fn extract_max(&mut self) -> Option<T> {
810 let mut to_return = None;
811
812 if self.0.is_some() {
813 let mut current = self;
814
815 // Finding the last non-empty node in the right branch
816 while current.0.as_ref().unwrap().right.0.is_some() {
817 current = &mut current.0.as_mut().unwrap().right;
818 }
819
820 // The maximum element is replaced by its left child (the left child can be empty)
821 let node = current.0.take().unwrap();
822 to_return = Some(node.value);
823 current.0 = node.left.0;
824 }
825
826 to_return
827 }
828
829 /// Deleting the first occurrence of an element with the specified value
830 pub fn remove(&mut self, target: &T) -> bool {
831 let mut current: *mut Tree<T> = self;
832
833 unsafe {
834 while let Some(ref mut node) = (*current).0 {
835 match node.value.cmp(target) {
836 Ordering::Greater => {
837 current = &mut node.left;
838 },
839 Ordering::Less => {
840 current = &mut node.right;
841 },
842 Ordering::Equal => {
843 match (node.left.0.as_mut(), node.right.0.as_mut()) {
844 // The node has no childrens, so we'll just make it empty.
845 (None, None) => {
846 (*current).0 = None;
847 },
848 // Replace the node with its left child
849 (Some(_), None) => {
850 (*current).0 = node.left.0.take();
851 },
852 // Replace the node with its left child
853 (None, Some(_)) => {
854 (*current).0 = node.right.0.take();
855 },
856 // The most complexity case: replace the value of the current node with
857 // its successor and then remove the successor's node.
858 // The BST invariant is not violated, which is easy to verify
859 (Some(_), Some(_)) => {
860 (*current).0.as_mut().unwrap().value = node.right.extract_min().unwrap();
861 }
862 }
863
864 return true; // The removal occurred
865 },
866 }
867 }
868 }
869
870 false // The element with the 'target' value was not found
871 }
872
873 // Vector of links to tree elements in sorted order
874 pub fn sorted_vec(&self) -> Vec<&T> {
875 let mut elements = Vec::new();
876
877 if let Some(node) = self.0.as_ref() {
878 elements.extend(node.left.sorted_vec());
879 elements.push(&node.value);
880 elements.extend(node.right.sorted_vec());
881 }
882
883 elements
884 }
885
886 /// Moving the tree into a sorted vector
887 pub fn into_sorted_vec(self) -> Vec<T> {
888 let mut elements = Vec::new();
889
890 if let Some(node) = self.0 {
891 elements.extend(node.left.into_sorted_vec());
892 elements.push(node.value);
893 elements.extend(node.right.into_sorted_vec());
894 }
895
896 elements
897 }
898}
899
900
901pub struct InorderTraversal<'a, T: 'a + Ord> {
902 stack: Vec<Option<&'a Box<Node<T>>>>,
903 current: Option<&'a Box<Node<T>>>,
904}
905
906pub struct ReverseOrderTraversal<'a, T: 'a + Ord> {
907 stack: Vec<Option<&'a Box<Node<T>>>>,
908 current: Option<&'a Box<Node<T>>>,
909}
910
911pub struct PreorderTraversal<'a, T: 'a + Ord> {
912 stack: Vec<Option<&'a Box<Node<T>>>>,
913 current: Option<&'a Box<Node<T>>>,
914}
915
916pub struct PostorderTraversal<'a, T: 'a + Ord> {
917 stack: Vec<Option<&'a Box<Node<T>>>>,
918 current: Option<&'a Box<Node<T>>>,
919}
920
921pub struct LevelOrderTraversal<'a, T: 'a + Ord> {
922 deque: VecDeque<&'a Box<Node<T>>>,
923}
924
925
926impl<'a, T: 'a + Ord> Iterator for InorderTraversal<'a, T> {
927 type Item = &'a T;
928
929 fn next(&mut self) -> Option<&'a T> {
930 loop {
931 if let Some(current) = self.current {
932 self.stack.push(self.current);
933 self.current = current.left.0.as_ref();
934 } else {
935 if let Some(node) = self.stack.pop() {
936 let current = node.unwrap();
937 let elem = ¤t.value;
938 self.current = current.right.0.as_ref();
939 return Some(elem);
940 } else {
941 return None;
942 }
943 }
944 }
945 }
946}
947
948impl<'a, T: 'a + Ord> Iterator for ReverseOrderTraversal<'a, T> {
949 type Item = &'a T;
950
951 fn next(&mut self) -> Option<&'a T> {
952 loop {
953 if let Some(current) = self.current {
954 self.stack.push(self.current);
955 self.current = current.right.0.as_ref();
956 } else {
957 if let Some(node) = self.stack.pop() {
958 let current = node.unwrap();
959 let elem = ¤t.value;
960 self.current = current.left.0.as_ref();
961 return Some(elem);
962 } else {
963 return None;
964 }
965 }
966 }
967 }
968}
969
970impl<'a, T: 'a + Ord> Iterator for PreorderTraversal<'a, T> {
971 type Item = &'a T;
972
973 fn next(&mut self) -> Option<&'a T> {
974 loop {
975 if let Some(current) = self.current {
976 let elem = ¤t.value;
977 self.current = current.left.0.as_ref();
978 self.stack.push(self.current);
979 return Some(elem);
980 } else {
981 if let Some(node) = self.stack.pop() {
982 if let Some(current) = node {
983 self.current = current.right.0.as_ref();
984 if self.current.is_some() {
985 self.stack.push(self.current);
986 }
987 }
988 } else {
989 return None;
990 }
991 }
992 }
993 }
994}
995
996impl<'a, T: 'a + Ord> Iterator for PostorderTraversal<'a, T> {
997 type Item = &'a T;
998
999 fn next(&mut self) -> Option<&'a T> {
1000 loop {
1001 // Go down the left branch and add nodes along with their right chilfren to the stack
1002 while let Some(current) = self.current {
1003 if current.right.0.is_some() {
1004 self.stack.push(current.right.0.as_ref());
1005 }
1006 self.stack.push(self.current);
1007 self.current = current.left.0.as_ref();
1008 }
1009
1010 if self.stack.len() == 0 {
1011 return None;
1012 }
1013
1014 if let Some(root) = self.stack.pop().unwrap() {
1015 // If the popped item has a right child and the
1016 // right child is not processed yet, then make sure
1017 // right child is processed before root
1018 if self.stack.len() > 0 && root.right.0.is_some() &&
1019 self.stack.get(self.stack.len()-1)
1020 .unwrap().unwrap().value == root.right.0.as_ref().unwrap().value {
1021
1022 self.stack.pop(); // Remove right child from stack
1023 self.stack.push(Some(root)); // Push root back to stack
1024
1025 // Changing the current node so that the root's right child is viewed first
1026 self.current = root.right.0.as_ref();
1027
1028 } else {
1029 let elem = &root.value;
1030 self.current = None;
1031 return Some(elem);
1032 }
1033
1034 } else {
1035 return None; // Only empty nodes remain
1036 }
1037 }
1038 }
1039}
1040
1041impl<'a, T: 'a + Ord> Iterator for LevelOrderTraversal<'a, T> {
1042 type Item = &'a T;
1043
1044 fn next(&mut self) -> Option<&'a T> {
1045 if let Some(boxed_node) = self.deque.pop_front() {
1046 if let Some(left) = boxed_node.left.0.as_ref() {
1047 self.deque.push_back(left);
1048 }
1049 if let Some(right) = boxed_node.right.0.as_ref() {
1050 self.deque.push_back(right);
1051 }
1052 Some(&boxed_node.value)
1053 } else {
1054 return None
1055 }
1056 }
1057}
1058
1059#[cfg(test)]
1060mod test;