#avl-tree #search #row #database #positional #customized #value

avltriee

Customized version of AVLTree library.Process the same value in the third branch. One data is immovable from one row, and positional relationships such as left, right, and parent are all referenced by row numbers. No search is required for value reference by specifying a row.

53 releases (28 breaking)

0.77.2 Feb 16, 2024
0.76.1 Feb 13, 2024
0.60.0 Dec 27, 2023
0.57.1 Oct 10, 2023
0.27.0 Nov 23, 2022

#245 in Data structures

Download history 28/week @ 2024-06-07 37/week @ 2024-06-14 31/week @ 2024-06-21 20/week @ 2024-06-28 11/week @ 2024-07-05 35/week @ 2024-07-12 39/week @ 2024-07-19 36/week @ 2024-07-26 37/week @ 2024-08-02 35/week @ 2024-08-09 38/week @ 2024-08-16 36/week @ 2024-08-23 42/week @ 2024-08-30 22/week @ 2024-09-06 22/week @ 2024-09-13 26/week @ 2024-09-20

119 downloads per month
Used in 16 crates (3 directly)

MIT/Apache

49KB
1K SLoC

avltriee

Features

A customized version of AVLTree. Process the same value in the third branch. This allows efficient searches even for sets with small cardinality in the distribution of values.

One data is immovable from one row, and positional relationships such as left, right, and parent are all referenced by row numbers. No search is required for value reference by specifying a row.

Example

init

use avltriee::Avltriee;

let mut triee = Avltriee::new();

insert & update

unsafe {
    triee.insert(&100); //or triee.update(1.try_into().unwrap(), &100);
}
unsafe {
    triee.insert(&345); //or triee.update(2.try_into().unwrap(), &345);
}
unsafe {
    triee.insert(&789); //or triee.update(3.try_into().unwrap(), &789);
}
unsafe {
    triee.update(2.try_into().unwrap(), &1234); //update exists row
}

iterator

for i in triee.iter() {
    println!("{}:{}", i, unsafe{ t.value_unchecked(i) });
}
for i in triee.desc_iter() {
    println!("{}:{}", i, unsafe{ t.value_unchecked(i) });
}
for i in t.iter_from(&10) {
    println!("{}:{}", i, unsafe{ t.value_unchecked(i) });
}
for i in t.iter_to(&500) {
    println!("{}:{}", i, unsafe{ t.value_unchecked(i) });
}
for i in t.iter_range(&300,&999) {
    println!("{}:{}", i, unsafe{ t.value_unchecked(i) });
}

delete

triee.delete(1.try_into().unwrap());
let (ord,row) = triee.search(&100);
if ord==Ordering::Equal{
    //found 
}

Dependencies

~1MB
~15K SLoC