#avltree #database

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.

15 unstable releases (3 breaking)

new 0.52.0 Sep 26, 2023
0.50.8 Aug 31, 2023
0.47.1 Jul 14, 2023
0.30.4 Mar 25, 2023
0.27.0 Nov 23, 2022

#178 in Algorithms

Download history 61/week @ 2023-06-07 157/week @ 2023-06-14 237/week @ 2023-06-21 77/week @ 2023-06-28 181/week @ 2023-07-05 219/week @ 2023-07-12 165/week @ 2023-07-19 80/week @ 2023-07-26 61/week @ 2023-08-02 179/week @ 2023-08-09 197/week @ 2023-08-16 336/week @ 2023-08-23 314/week @ 2023-08-30 342/week @ 2023-09-06 184/week @ 2023-09-13 256/week @ 2023-09-20

1,204 downloads per month
Used in 12 crates (3 directly)

MIT/Apache

35KB
959 lines

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;
use avltriee::AvltrieeNode;

let length=100;

let mut buffer: Vec<AvltrieeNode<i64>> = (0..=length)
    .map(|_| AvltrieeNode::new(0, 0, 0))
    .collect();
let mut triee = Avltriee::new(buffer.as_mut_ptr());

insert & update

unsafe {
    triee.update(1, 100); //insert
}
unsafe {
    triee.update(2, 345); //insert
}
unsafe {
    triee.update(3, 789); //insert
}
unsafe {
    triee.update(2, 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(|v|v.cmp(&10)) {
    println!("{}:{}", i, unsafe{ t.value_unchecked(i) });
}
for i in t.iter_to(|v|v.cmp(&500)) {
    println!("{}:{}", i, unsafe{ t.value_unchecked(i) });
}
for i in t.iter_range(|v|v.cmp(&300),|v|v.cmp(&999)) {
    println!("{}:{}", i, unsafe{ t.value_unchecked(i) });
}

delete

triee.delete(1);
let (ord,row) = triee.search(&100);

or 

let (ord,row) = triee.search_nord(|v|v.cmp(&100));

No runtime deps