rust_algorithms/tree/
avl.rs

1//! AVL daraxti — o'zini balanslaydigan BST (Adelson-Velskiy va Landis, 1962).
2
3use std::cmp::Ordering;
4
5#[derive(Debug)]
6struct Node<T> {
7    value: T,
8    height: i32,
9    left: Option<Box<Node<T>>>,
10    right: Option<Box<Node<T>>>,
11}
12
13impl<T> Node<T> {
14    fn new(value: T) -> Box<Self> {
15        Box::new(Self {
16            value,
17            height: 1,
18            left: None,
19            right: None,
20        })
21    }
22}
23
24fn height<T>(node: &Option<Box<Node<T>>>) -> i32 {
25    node.as_ref().map_or(0, |n| n.height)
26}
27
28/// Balans koeffitsienti: chap balandligi − o'ng balandligi.
29fn balance<T>(node: &Node<T>) -> i32 {
30    height(&node.left) - height(&node.right)
31}
32
33fn update_height<T>(node: &mut Node<T>) {
34    node.height = 1 + height(&node.left).max(height(&node.right));
35}
36
37/// AVL daraxti: har bir tugunda chap va o'ng shox balandliklari farqi **≤ 1**.
38///
39/// Shu qat'iy shart tufayli balandlik har doim ~1.44·log₂(n) dan oshmaydi —
40/// ya'ni `insert`, `contains`, `remove` **kafolatlangan O(log n)**.
41///
42/// ## Balansni qanday tiklaydi: 4 ta burilish (rotation)
43///
44/// ```text
45///  1) LL (chapga qiyshaygan)          o'ngga burish
46///        z                                y
47///       /                               /   \
48///      y            ──────────►        x     z
49///     /
50///    x
51///
52///  2) RR (o'ngga qiyshaygan)          chapga burish  (1 ning ko'zgusi)
53///
54///  3) LR: avval chap shoxni chapga burish → LL holatiga keladi → o'ngga burish
55///  4) RL: avval o'ng shoxni o'ngga burish → RR holatiga keladi → chapga burish
56/// ```
57///
58/// Har bir burilish — bir nechta ko'rsatkichni almashtirish, ya'ni **O(1)**.
59/// Qo'shishdan keyin ko'pi bilan **1 ta** balanslash yetadi.
60///
61/// ## BST bilan solishtirish
62///
63/// ```text
64/// 1..10 sonlarini ketma-ket qo'shsak:
65///   BST balandligi = 9   (bir tomonlama zanjir)
66///   AVL balandligi = 3   (balanslangan)
67/// ```
68///
69/// # Misol
70/// ```
71/// use rust_algorithms::tree::AvlTree;
72///
73/// let mut t = AvlTree::new();
74/// for x in 1..=1000 {
75///     t.insert(x); // tartiblangan kirish — BST uchun eng yomon holat
76/// }
77/// assert_eq!(t.len(), 1000);
78/// assert!(t.height() <= 14); // log2(1000) ≈ 10, AVL kafolati ≈ 1.44·log2(n)
79/// assert!(t.contains(&777));
80/// assert_eq!(t.to_sorted_vec().first(), Some(&&1));
81/// ```
82#[derive(Debug)]
83pub struct AvlTree<T: Ord> {
84    root: Option<Box<Node<T>>>,
85    len: usize,
86}
87
88impl<T: Ord> Default for AvlTree<T> {
89    fn default() -> Self {
90        Self::new()
91    }
92}
93
94impl<T: Ord> AvlTree<T> {
95    /// Bo'sh daraxt.
96    pub fn new() -> Self {
97        Self { root: None, len: 0 }
98    }
99
100    /// Qiymat qo'shadi va kerak bo'lsa daraxtni balanslaydi. O(log n).
101    /// Takror qiymat qo'shilmaydi.
102    pub fn insert(&mut self, value: T) -> bool {
103        let (yangi_root, qoshildi) = Self::insert_node(self.root.take(), value);
104        self.root = Some(yangi_root);
105        if qoshildi {
106            self.len += 1;
107        }
108        qoshildi
109    }
110
111    fn insert_node(node: Option<Box<Node<T>>>, value: T) -> (Box<Node<T>>, bool) {
112        let mut node = match node {
113            None => return (Node::new(value), true),
114            Some(n) => n,
115        };
116
117        let qoshildi = match value.cmp(&node.value) {
118            Ordering::Less => {
119                let (chap, q) = Self::insert_node(node.left.take(), value);
120                node.left = Some(chap);
121                q
122            }
123            Ordering::Greater => {
124                let (ong, q) = Self::insert_node(node.right.take(), value);
125                node.right = Some(ong);
126                q
127            }
128            Ordering::Equal => false,
129        };
130
131        if !qoshildi {
132            return (node, false);
133        }
134
135        update_height(&mut node);
136        (Self::rebalance(node), true)
137    }
138
139    /// Tugunni tekshirib, kerak bo'lsa 4 ta holatdan birini qo'llaydi.
140    fn rebalance(mut node: Box<Node<T>>) -> Box<Node<T>> {
141        let b = balance(&node);
142
143        if b > 1 {
144            // chapga qiyshaygan
145            if balance(node.left.as_ref().unwrap()) < 0 {
146                // LR: avval chap shoxni chapga buramiz
147                node.left = Some(Self::rotate_left(node.left.take().unwrap()));
148            }
149            return Self::rotate_right(node);
150        }
151        if b < -1 {
152            // o'ngga qiyshaygan
153            if balance(node.right.as_ref().unwrap()) > 0 {
154                // RL: avval o'ng shoxni o'ngga buramiz
155                node.right = Some(Self::rotate_right(node.right.take().unwrap()));
156            }
157            return Self::rotate_left(node);
158        }
159        node
160    }
161
162    /// O'ngga burish: chap farzand yangi ildizga aylanadi.
163    fn rotate_right(mut z: Box<Node<T>>) -> Box<Node<T>> {
164        let mut y = z
165            .left
166            .take()
167            .expect("o'ngga burishda chap farzand bo'lishi shart");
168        z.left = y.right.take(); // y ning o'ng shoxi z ning chapiga o'tadi
169        update_height(&mut z);
170        y.right = Some(z);
171        update_height(&mut y);
172        y
173    }
174
175    /// Chapga burish: o'ng farzand yangi ildizga aylanadi.
176    fn rotate_left(mut z: Box<Node<T>>) -> Box<Node<T>> {
177        let mut y = z
178            .right
179            .take()
180            .expect("chapga burishda o'ng farzand bo'lishi shart");
181        z.right = y.left.take();
182        update_height(&mut z);
183        y.left = Some(z);
184        update_height(&mut y);
185        y
186    }
187
188    /// Qiymat bormi? O(log n).
189    pub fn contains(&self, value: &T) -> bool {
190        let mut kursor = self.root.as_deref();
191        while let Some(n) = kursor {
192            match value.cmp(&n.value) {
193                Ordering::Less => kursor = n.left.as_deref(),
194                Ordering::Greater => kursor = n.right.as_deref(),
195                Ordering::Equal => return true,
196            }
197        }
198        false
199    }
200
201    /// Tartiblangan ketma-ketlik (inorder).
202    pub fn to_sorted_vec(&self) -> Vec<&T> {
203        let mut out = Vec::with_capacity(self.len);
204        let mut stack: Vec<&Node<T>> = Vec::new();
205        let mut kursor = self.root.as_deref();
206        while kursor.is_some() || !stack.is_empty() {
207            while let Some(n) = kursor {
208                stack.push(n);
209                kursor = n.left.as_deref();
210            }
211            let n = stack.pop().unwrap();
212            out.push(&n.value);
213            kursor = n.right.as_deref();
214        }
215        out
216    }
217
218    /// Tugunlar soni.
219    pub fn len(&self) -> usize {
220        self.len
221    }
222
223    /// Bo'shmi?
224    pub fn is_empty(&self) -> bool {
225        self.len == 0
226    }
227
228    /// Balandlik (tugunlar bo'yicha; bo'sh daraxtda 0).
229    pub fn height(&self) -> i32 {
230        height(&self.root)
231    }
232
233    /// Har bir tugunda AVL sharti bajarilganini tekshiradi (testlar uchun).
234    pub fn is_balanced(&self) -> bool {
235        fn go<T>(node: &Option<Box<Node<T>>>) -> bool {
236            match node {
237                None => true,
238                Some(n) => balance(n).abs() <= 1 && go(&n.left) && go(&n.right),
239            }
240        }
241        go(&self.root)
242    }
243}
244
245impl<T: Ord> FromIterator<T> for AvlTree<T> {
246    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
247        let mut t = Self::new();
248        for x in iter {
249            t.insert(x);
250        }
251        t
252    }
253}
254
255#[cfg(test)]
256mod tests {
257    use super::*;
258    use crate::util::Rng;
259
260    #[test]
261    fn tartiblangan_kirishda_ham_balanslangan() {
262        let t: AvlTree<i32> = (1..=1023).collect();
263        assert!(t.is_balanced());
264        // Balanslangan daraxtda balandlik ~log2(n)
265        assert!(t.height() <= 14, "balandlik = {}", t.height());
266        assert_eq!(t.len(), 1023);
267    }
268
269    #[test]
270    fn tasodifiy_kirishda_balanslangan() {
271        let mut rng = Rng::new(505);
272        let t: AvlTree<i64> = rng.vec(2000, 0, 1_000_000).into_iter().collect();
273        assert!(t.is_balanced());
274        let v = t.to_sorted_vec();
275        assert!(v.windows(2).all(|w| w[0] < w[1]));
276    }
277
278    #[test]
279    fn tortta_burilish_holati() {
280        // LL
281        let t: AvlTree<i32> = [30, 20, 10].into_iter().collect();
282        assert!(t.is_balanced() && t.height() == 2);
283        // RR
284        let t: AvlTree<i32> = [10, 20, 30].into_iter().collect();
285        assert!(t.is_balanced() && t.height() == 2);
286        // LR
287        let t: AvlTree<i32> = [30, 10, 20].into_iter().collect();
288        assert!(t.is_balanced() && t.height() == 2);
289        // RL
290        let t: AvlTree<i32> = [10, 30, 20].into_iter().collect();
291        assert!(t.is_balanced() && t.height() == 2);
292    }
293
294    #[test]
295    fn takror_qoshilmaydi() {
296        let mut t = AvlTree::new();
297        assert!(t.insert(1));
298        assert!(!t.insert(1));
299        assert_eq!(t.len(), 1);
300    }
301
302    #[test]
303    fn bst_bilan_taqqoslash() {
304        use crate::tree::BinarySearchTree;
305        let bst: BinarySearchTree<i32> = (1..=100).collect();
306        let avl: AvlTree<i32> = (1..=100).collect();
307        assert_eq!(bst.height(), 99); // qiyshaygan
308        assert!(avl.height() <= 8); // balanslangan
309    }
310
311    #[test]
312    fn bosh_daraxt() {
313        let t: AvlTree<i32> = AvlTree::new();
314        assert!(t.is_empty());
315        assert_eq!(t.height(), 0);
316        assert!(!t.contains(&1));
317        assert!(t.is_balanced());
318    }
319}
rust_algorithms/tree/avl.rs

rust_algorithms/tree/
avl.rs
