dsa_rust/hierarchies/
linked_bst.rs

1/*! A safe, linked binary search tree (BST)
2
3# About
4
5# Design
6
7# Example
8*/
9
10use crate::hierarchies::traits::{BinaryTree, Tree};
11
12/** Owned non-null pointer to Node; Functions as a position */
13type Pos<T> = Box<Node<T>>;
14
15/** Represents a proper binary tree if left and right are Some */
16#[derive(Clone, PartialEq)]
17pub struct Node<T: std::cmp::PartialEq> {
18    parent: Option<Pos<T>>,
19    left: Option<Pos<T>>,
20    right: Option<Pos<T>>,
21    data: Option<T>,
22}
23
24/** The BinTree struct contains operations specific to binary trees.
25
26NOTE: Requires the PartialEq trait bounds for binary tree operations */
27pub struct BinTree<T: std::cmp::PartialEq> {
28    root: Box<Node<T>>, // No Option because
29    size: usize,
30}
31impl<T> Default for BinTree<T>
32where
33    T: std::cmp::PartialEq,
34{
35    fn default() -> Self {
36        Self::new()
37    }
38}
39impl<T> BinTree<T>
40where
41    T: std::cmp::PartialEq,
42{
43    /// Creates a new generic binary tree.
44    pub fn new() -> BinTree<T> {
45        let node: Node<T> = Node {
46            parent: None,
47            left: None,
48            right: None,
49            data: None,
50        };
51        BinTree {
52            root: Box::from(node),
53            size: 0,
54        }
55    }
56
57    // /** Sets the root of the tree */
58    //pub fn set_root(&mut self, data: T) {
59    //    self.root.data = Some(data)
60    //}
61
62    /** Adds a left node to a parent */
63    pub fn add_left(&mut self, mut ancestor: Node<T>, node: Pos<T>) {
64        ancestor.left = Some(node);
65    }
66
67    /** Adds a right node to a parent */
68    pub fn add_right(&mut self, mut ancestor: Node<T>, node: Pos<T>) {
69        ancestor.right = Some(node);
70    }
71
72    /// Overwrites the data at a given node (position) */
73    ///
74    /// WARNING: Unimplmented
75    pub fn set(&mut self, _p: Node<T>, _node: T) -> Result<(), String> {
76        Ok(())
77    }
78
79    ///
80    ///
81    /// WARNING: Unimplmented
82    pub fn attach(&mut self, _left: Node<T>, _right: Node<T>) {}
83
84    ///
85    ///
86    /// WARNING: Unimplmented
87    pub fn remove(&mut self, p: Node<T>) {
88        let _ = p;
89    }
90
91    /** Returns the number of nodes in the tree */
92    pub fn size(&self) -> usize {
93        self.size
94    }
95
96    /** Returns true if the tree contains no nodes */
97    pub fn is_empty(&self) -> bool {
98        //if self.size > 0 { false } else { true }
99        self.size == 0
100    }
101
102    /** Returns an immutable reference to the root of the tree */
103    pub fn root(&self) -> Option<&Pos<T>> {
104        Some(&self.root)
105    }
106}
107//impl<T> Tree<Pos<T>, T> for BinTree<T>
108impl<T> Tree<T> for BinTree<T>
109where
110    T: Clone + std::cmp::PartialEq,
111{
112    type Position = Pos<T>;
113
114    /** Returns an immutable reference to the node's data */
115    fn get<'a>(&'a self, node: &'a Self::Position) -> Option<&'a T> {
116        if node.data.is_some() {
117            node.data.as_ref()
118        } else {
119            None
120        }
121    }
122
123    /** Returns an immutable reference to the parent of the given node */
124    fn parent(&self, node: Self::Position) -> Option<Self::Position> {
125        //if self.validate(&node) {
126        //    node.unwrap().parent
127        //} else { None }
128        if node.parent.is_some() {
129            node.parent
130        } else {
131            None
132        }
133    }
134
135    /** Returns the number of children for a given node */
136    fn num_children(&self, node: Self::Position) -> Option<usize> {
137        self.children(node).map(|n| n.len())
138        //if let Some(n) = self.children(node) {
139        //    Some(n.len())
140        //} else {
141        //    None
142        //}
143    }
144
145    /** Returns a collection of the node's children */
146    fn children(&self, node: Self::Position) -> Option<Vec<Self::Position>> {
147        let mut vec = Vec::with_capacity(2);
148        if let Some(l) = node.left {
149            vec.push(l)
150        };
151        if let Some(r) = node.right {
152            vec.push(r)
153        };
154        Some(vec)
155    }
156
157    /** Returns true if the provided node has no children */
158    fn is_leaf(&self, node: Self::Position) -> bool {
159        //if self.num_children(node.clone()).is_some()
160        //    && (*node.clone().unwrap()).left.is_none()
161        //    && (*node.clone().unwrap()).right.is_none() {
162        //    true
163        //} else { false }
164        node.left.is_none() && node.right.is_none()
165    }
166
167    /** Returns true if the node is the root */
168    fn is_root(&self, node: Self::Position) -> bool {
169        node == self.root
170    }
171
172    /** Depth... */
173    fn depth(&self, node: Self::Position) -> Option<usize> {
174        let mut d = 1;
175        let mut cursor = node.clone();
176        while !self.is_root(cursor.clone()) {
177            cursor = self.parent(cursor.clone()).unwrap();
178            d += 1;
179        }
180        Some(d)
181    }
182
183    /** Height... */
184    fn height(&self, node: Self::Position) -> Option<usize> {
185        let mut h = 0;
186        if let Some(c) = self.children(node) {
187            for p in c {
188                h = std::cmp::max(h, 1 + self.height(p).unwrap())
189            }
190            Some(h)
191        } else {
192            None
193        }
194    }
195}
196impl<T> BinaryTree<T> for BinTree<T>
197where
198    T: Clone + std::cmp::PartialEq,
199{
200    type Position = Pos<T>;
201
202    fn left(&self, node: Self::Position) -> Option<Self::Position> {
203        if node.left.is_some() {
204            node.left
205        } else {
206            None
207        }
208    }
209
210    fn right(&self, node: Self::Position) -> Option<Self::Position> {
211        if node.right.is_some() {
212            node.right
213        } else {
214            None
215        }
216    }
217
218    fn sibling(&self, node: Self::Position) -> Option<Self::Position> {
219        //if node.parent.is_some() { // Validate that the argument's parent exists
220        //    let p = node.clone().parent;
221        //    if p.clone().unwrap().left == Some(node) {
222        //        return p.unwrap().right; // If the argument is left, return right
223        //    } else {
224        //        return p.unwrap().left; // If the argument is left, return right
225        //    }
226        //} else { None }
227        if let Some(ref parent) = node.parent {
228            // Checks that node has a parent
229            // Checks if the argument is left, if so, return right and vice versa
230            if parent.left.as_ref() == Some(&node) {
231                parent.right.clone() // Return the right sibling
232            } else {
233                parent.left.clone() // Return the left sibling
234            }
235        } else {
236            None // Return None if the node has no parent
237        }
238    }
239}
dsa_rust/hierarchies/linked_bst.rs

dsa_rust/hierarchies/
linked_bst.rs
