rust_algorithms/tree/
bst.rs

1//! Binary Search Tree (BST) — tartiblangan qidiruv daraxti.
2
3#[derive(Debug)]
4struct Node<T> {
5    value: T,
6    left: Option<Box<Node<T>>>,
7    right: Option<Box<Node<T>>>,
8}
9
10/// Binary Search Tree — **BST qoidasi**: chapdagi hamma qiymat tugundan kichik,
11/// o'ngdagi hamma qiymat tugundan katta.
12///
13/// ```text
14///          50
15///        /    \
16///      30      70
17///     /  \       \
18///   20    40      80      inorder → 20 30 40 50 70 80  (tartiblangan!)
19/// ```
20///
21/// | Amal | O'rtacha | Eng yomon |
22/// |---|---|---|
23/// | `insert` / `contains` / `remove` | O(log n) | **O(n)** |
24///
25/// **Eng yomon holat qachon?** Tartiblangan ma'lumotni ketma-ket qo'shsangiz,
26/// daraxt bir tomonga cho'zilib, oddiy bog'langan ro'yxatga aylanadi:
27///
28/// ```text
29///  1 → 2 → 3 → 4 → 5      (balandlik n, qidiruv O(n))
30/// ```
31///
32/// Shu muammoning yechimi — o'zini balanslaydigan daraxtlar:
33/// [`AvlTree`](super::AvlTree), Red-Black tree (Rustdagi `BTreeMap` esa B-daraxt).
34///
35/// # Misol
36/// ```
37/// use rust_algorithms::tree::BinarySearchTree;
38///
39/// let mut t = BinarySearchTree::new();
40/// for x in [50, 30, 70, 20, 40, 80] {
41///     t.insert(x);
42/// }
43///
44/// assert!(t.contains(&40));
45/// assert!(!t.contains(&45));
46/// assert_eq!(t.min(), Some(&20));
47/// assert_eq!(t.max(), Some(&80));
48/// assert_eq!(t.to_sorted_vec(), vec![&20, &30, &40, &50, &70, &80]);
49///
50/// assert!(t.remove(&30));
51/// assert_eq!(t.to_sorted_vec(), vec![&20, &40, &50, &70, &80]);
52/// ```
53#[derive(Debug)]
54pub struct BinarySearchTree<T: Ord> {
55    root: Option<Box<Node<T>>>,
56    len: usize,
57}
58
59impl<T: Ord> Default for BinarySearchTree<T> {
60    fn default() -> Self {
61        Self::new()
62    }
63}
64
65impl<T: Ord> BinarySearchTree<T> {
66    /// Bo'sh daraxt.
67    pub fn new() -> Self {
68        Self { root: None, len: 0 }
69    }
70
71    /// Qiymat qo'shadi. Takroriy qiymat qo'shilmaydi (`false` qaytadi).
72    ///
73    /// Iterativ — chuqur daraxtlarda ham stack to'lmaydi.
74    pub fn insert(&mut self, value: T) -> bool {
75        let mut kursor = &mut self.root;
76        while let Some(node) = kursor {
77            match value.cmp(&node.value) {
78                std::cmp::Ordering::Less => kursor = &mut node.left,
79                std::cmp::Ordering::Greater => kursor = &mut node.right,
80                std::cmp::Ordering::Equal => return false, // takror
81            }
82        }
83        *kursor = Some(Box::new(Node {
84            value,
85            left: None,
86            right: None,
87        }));
88        self.len += 1;
89        true
90    }
91
92    /// Qiymat bormi? — ildizdan boshlab "kichik → chap, katta → o'ng".
93    pub fn contains(&self, value: &T) -> bool {
94        let mut kursor = self.root.as_deref();
95        while let Some(node) = kursor {
96            match value.cmp(&node.value) {
97                std::cmp::Ordering::Less => kursor = node.left.as_deref(),
98                std::cmp::Ordering::Greater => kursor = node.right.as_deref(),
99                std::cmp::Ordering::Equal => return true,
100            }
101        }
102        false
103    }
104
105    /// Eng kichik qiymat — eng chapdagi tugun.
106    pub fn min(&self) -> Option<&T> {
107        let mut node = self.root.as_deref()?;
108        while let Some(l) = node.left.as_deref() {
109            node = l;
110        }
111        Some(&node.value)
112    }
113
114    /// Eng katta qiymat — eng o'ngdagi tugun.
115    pub fn max(&self) -> Option<&T> {
116        let mut node = self.root.as_deref()?;
117        while let Some(r) = node.right.as_deref() {
118            node = r;
119        }
120        Some(&node.value)
121    }
122
123    /// Qiymatni o'chiradi. Topilsa `true`.
124    ///
125    /// **Uchta holat:**
126    /// 1. **Barg** — shunchaki o'chiramiz;
127    /// 2. **Bitta farzand** — farzandni o'z o'rniga qo'yamiz;
128    /// 3. **Ikkita farzand** — o'ng shoxdagi **eng kichik** qiymatni (inorder successor)
129    ///    o'rniga ko'chiramiz va uni o'ng shoxdan o'chiramiz. BST qoidasi buzilmaydi.
130    pub fn remove(&mut self, value: &T) -> bool {
131        let ochirildi = Self::remove_node(&mut self.root, value);
132        if ochirildi {
133            self.len -= 1;
134        }
135        ochirildi
136    }
137
138    fn remove_node(node: &mut Option<Box<Node<T>>>, value: &T) -> bool {
139        let tartib = match node.as_ref() {
140            None => return false,
141            Some(n) => value.cmp(&n.value),
142        };
143        match tartib {
144            std::cmp::Ordering::Less => Self::remove_node(&mut node.as_mut().unwrap().left, value),
145            std::cmp::Ordering::Greater => {
146                Self::remove_node(&mut node.as_mut().unwrap().right, value)
147            }
148            std::cmp::Ordering::Equal => {
149                let orin = {
150                    let n = node.as_mut().unwrap();
151                    match (n.left.take(), n.right.take()) {
152                        (None, None) => None,
153                        (Some(l), None) => Some(l),
154                        (None, Some(r)) => Some(r),
155                        (Some(l), Some(r)) => {
156                            let mut ong = Some(r);
157                            let ozod = Self::extract_min(&mut ong).unwrap();
158                            Some(Box::new(Node {
159                                value: ozod,
160                                left: Some(l),
161                                right: ong,
162                            }))
163                        }
164                    }
165                };
166                *node = orin;
167                true
168            }
169        }
170    }
171
172    /// Shoxdagi eng kichik qiymatni olib chiqadi (tugunni o'chirib).
173    fn extract_min(node: &mut Option<Box<Node<T>>>) -> Option<T> {
174        node.as_ref()?;
175        if node.as_ref().unwrap().left.is_some() {
176            Self::extract_min(&mut node.as_mut().unwrap().left)
177        } else {
178            let n = node.take().unwrap();
179            *node = n.right;
180            Some(n.value)
181        }
182    }
183
184    /// Inorder aylanish — **tartiblangan** ketma-ketlik. O(n).
185    pub fn to_sorted_vec(&self) -> Vec<&T> {
186        let mut out = Vec::with_capacity(self.len);
187        let mut stack: Vec<&Node<T>> = Vec::new();
188        let mut kursor = self.root.as_deref();
189        while kursor.is_some() || !stack.is_empty() {
190            while let Some(n) = kursor {
191                stack.push(n);
192                kursor = n.left.as_deref();
193            }
194            let n = stack.pop().unwrap();
195            out.push(&n.value);
196            kursor = n.right.as_deref();
197        }
198        out
199    }
200
201    /// Tugunlar soni.
202    pub fn len(&self) -> usize {
203        self.len
204    }
205
206    /// Bo'shmi?
207    pub fn is_empty(&self) -> bool {
208        self.len == 0
209    }
210
211    /// Balandlik (qirralar bo'yicha). Bo'sh daraxtda 0.
212    pub fn height(&self) -> usize {
213        fn go<T>(node: &Option<Box<Node<T>>>) -> usize {
214            match node {
215                None => 0,
216                Some(n) if n.left.is_none() && n.right.is_none() => 0,
217                Some(n) => 1 + go(&n.left).max(go(&n.right)),
218            }
219        }
220        go(&self.root)
221    }
222}
223
224impl<T: Ord> FromIterator<T> for BinarySearchTree<T> {
225    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
226        let mut t = Self::new();
227        for x in iter {
228            t.insert(x);
229        }
230        t
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use super::*;
237    use crate::util::Rng;
238
239    #[test]
240    fn qoshish_va_qidirish() {
241        let mut t = BinarySearchTree::new();
242        assert!(t.insert(5));
243        assert!(!t.insert(5)); // takror
244        assert_eq!(t.len(), 1);
245        assert!(t.contains(&5));
246        assert!(!t.contains(&6));
247    }
248
249    #[test]
250    fn inorder_tartiblangan() {
251        let mut rng = Rng::new(303);
252        let sonlar = rng.vec(500, 0, 10_000);
253        let t: BinarySearchTree<i64> = sonlar.iter().cloned().collect();
254
255        let mut kutilgan = sonlar.clone();
256        kutilgan.sort_unstable();
257        kutilgan.dedup();
258
259        let natija: Vec<i64> = t.to_sorted_vec().into_iter().cloned().collect();
260        assert_eq!(natija, kutilgan);
261        assert_eq!(t.len(), kutilgan.len());
262    }
263
264    #[test]
265    fn min_max() {
266        let t: BinarySearchTree<i32> = [50, 30, 70, 20, 80].into_iter().collect();
267        assert_eq!(t.min(), Some(&20));
268        assert_eq!(t.max(), Some(&80));
269
270        let bosh: BinarySearchTree<i32> = BinarySearchTree::new();
271        assert_eq!(bosh.min(), None);
272        assert_eq!(bosh.max(), None);
273    }
274
275    #[test]
276    fn ochirishning_uch_holati() {
277        let mut t: BinarySearchTree<i32> = [50, 30, 70, 20, 40, 60, 80, 65].into_iter().collect();
278
279        assert!(t.remove(&20)); // 1) barg
280        assert!(!t.contains(&20));
281
282        assert!(t.remove(&60)); // 2) bitta farzand (65)
283        assert!(!t.contains(&60));
284        assert!(t.contains(&65));
285
286        assert!(t.remove(&50)); // 3) ikkita farzand (ildiz)
287        assert!(!t.contains(&50));
288
289        let qolgan: Vec<i32> = t.to_sorted_vec().into_iter().cloned().collect();
290        assert_eq!(qolgan, vec![30, 40, 65, 70, 80]);
291        assert_eq!(t.len(), 5);
292
293        assert!(!t.remove(&999));
294    }
295
296    #[test]
297    fn hammasini_ochirish() {
298        let mut rng = Rng::new(404);
299        let sonlar: Vec<i64> = {
300            let mut v = rng.vec(200, 0, 500);
301            v.sort_unstable();
302            v.dedup();
303            rng.shuffle(&mut v);
304            v
305        };
306        let mut t: BinarySearchTree<i64> = sonlar.iter().cloned().collect();
307        for x in &sonlar {
308            assert!(t.remove(x), "{x} o'chmadi");
309        }
310        assert!(t.is_empty());
311        assert_eq!(t.to_sorted_vec().len(), 0);
312    }
313
314    #[test]
315    fn tartiblangan_kirish_qiyshiq_daraxt_beradi() {
316        let t: BinarySearchTree<i32> = (1..=10).collect();
317        assert_eq!(t.height(), 9); // bog'langan ro'yxatga aylandi!
318    }
319}
rust_algorithms/tree/bst.rs

rust_algorithms/tree/
bst.rs
