Struct BinarySearchTree 

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

Binary Search Tree — BST qoidasi: chapdagi hamma qiymat tugundan kichik, o’ngdagi hamma qiymat tugundan katta.

         50
       /    \
     30      70
    /  \       \
  20    40      80      inorder → 20 30 40 50 70 80  (tartiblangan!)

Amal	O’rtacha	Eng yomon
insert / contains / remove	O(log n)	O(n)

Eng yomon holat qachon? Tartiblangan ma’lumotni ketma-ket qo’shsangiz, daraxt bir tomonga cho’zilib, oddiy bog’langan ro’yxatga aylanadi:

 1 → 2 → 3 → 4 → 5      (balandlik n, qidiruv O(n))

Shu muammoning yechimi — o’zini balanslaydigan daraxtlar: AvlTree, Red-Black tree (Rustdagi BTreeMap esa B-daraxt).

Misol

use rust_algorithms::tree::BinarySearchTree;

let mut t = BinarySearchTree::new();
for x in [50, 30, 70, 20, 40, 80] {
    t.insert(x);
}

assert!(t.contains(&40));
assert!(!t.contains(&45));
assert_eq!(t.min(), Some(&20));
assert_eq!(t.max(), Some(&80));
assert_eq!(t.to_sorted_vec(), vec![&20, &30, &40, &50, &70, &80]);

assert!(t.remove(&30));
assert_eq!(t.to_sorted_vec(), vec![&20, &40, &50, &70, &80]);

Implementations

impl<T: Ord> BinarySearchTree<T>

pub fn new() -> Self

Bo’sh daraxt.

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

Qiymat qo’shadi. Takroriy qiymat qo’shilmaydi (false qaytadi).

Iterativ — chuqur daraxtlarda ham stack to’lmaydi.

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

Qiymat bormi? — ildizdan boshlab “kichik → chap, katta → o’ng”.

pub fn min(&self) -> Option<&T>

Eng kichik qiymat — eng chapdagi tugun.

pub fn max(&self) -> Option<&T>

Eng katta qiymat — eng o’ngdagi tugun.

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

Qiymatni o’chiradi. Topilsa true.

Uchta holat:

1. Barg — shunchaki o’chiramiz;
2. Bitta farzand — farzandni o’z o’rniga qo’yamiz;
3. Ikkita farzand — o’ng shoxdagi eng kichik qiymatni (inorder successor) o’rniga ko’chiramiz va uni o’ng shoxdan o’chiramiz. BST qoidasi buzilmaydi.

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

Inorder aylanish — tartiblangan ketma-ketlik. O(n).

pub fn len(&self) -> usize

Tugunlar soni.

pub fn is_empty(&self) -> bool

Bo’shmi?

pub fn height(&self) -> usize

Balandlik (qirralar bo’yicha). Bo’sh daraxtda 0.

Trait Implementations

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

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

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

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

Creates a value from an iterator.