Struct AvlTree 

pub struct AvlTree<T: Ord> { /* private fields */ }

AVL daraxti: har bir tugunda chap va o’ng shox balandliklari farqi ≤ 1.

Shu qat’iy shart tufayli balandlik har doim ~1.44·log₂(n) dan oshmaydi — ya’ni insert, contains, remove kafolatlangan O(log n).

Balansni qanday tiklaydi: 4 ta burilish (rotation)

 1) LL (chapga qiyshaygan)          o'ngga burish
       z                                y
      /                               /   \
     y            ──────────►        x     z
    /
   x

 2) RR (o'ngga qiyshaygan)          chapga burish  (1 ning ko'zgusi)

 3) LR: avval chap shoxni chapga burish → LL holatiga keladi → o'ngga burish
 4) RL: avval o'ng shoxni o'ngga burish → RR holatiga keladi → chapga burish

Har bir burilish — bir nechta ko’rsatkichni almashtirish, ya’ni O(1). Qo’shishdan keyin ko’pi bilan 1 ta balanslash yetadi.

BST bilan solishtirish

1..10 sonlarini ketma-ket qo'shsak:
  BST balandligi = 9   (bir tomonlama zanjir)
  AVL balandligi = 3   (balanslangan)

Misol

use rust_algorithms::tree::AvlTree;

let mut t = AvlTree::new();
for x in 1..=1000 {
    t.insert(x); // tartiblangan kirish — BST uchun eng yomon holat
}
assert_eq!(t.len(), 1000);
assert!(t.height() <= 14); // log2(1000) ≈ 10, AVL kafolati ≈ 1.44·log2(n)
assert!(t.contains(&777));
assert_eq!(t.to_sorted_vec().first(), Some(&&1));

Implementations

impl<T: Ord> AvlTree<T>

pub fn new() -> Self

Bo’sh daraxt.

pub fn insert(&mut self, value: T) -> bool

Qiymat qo’shadi va kerak bo’lsa daraxtni balanslaydi. O(log n). Takror qiymat qo’shilmaydi.

pub fn contains(&self, value: &T) -> bool

Qiymat bormi? O(log n).

pub fn to_sorted_vec(&self) -> Vec<&T>

Tartiblangan ketma-ketlik (inorder).

pub fn len(&self) -> usize

Tugunlar soni.

pub fn is_empty(&self) -> bool

Bo’shmi?

pub fn height(&self) -> i32

Balandlik (tugunlar bo’yicha; bo’sh daraxtda 0).

pub fn is_balanced(&self) -> bool

Har bir tugunda AVL sharti bajarilganini tekshiradi (testlar uchun).

Trait Implementations

impl<T: Debug + Ord> Debug for AvlTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Ord> Default for AvlTree<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Ord> FromIterator<T> for AvlTree<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.