#tree #immutability #ternary #structual-sharing

im_ternary_tree

Structural sharing ternary tree, i.e. immutable data structure

28 releases

0.0.18 Feb 25, 2024
0.0.17 Feb 17, 2024
0.0.11 Jul 26, 2022
0.0.10 May 31, 2022
0.0.1-a8 Nov 21, 2021

#441 in Data structures

33 downloads per month
Used in 2 crates

MIT license

705KB
2.5K SLoC

Persistent structrual sharing tree for Calcit

a variant of 2-3 tree, with enhancements on ternary branching, optimized with tricks like finger-tree.

t.pop_left() and t.push_right(..) is optimized to be amortized O(1) at best cases and O(log n) when restructuring involed.

Tree layout from 0 to 159 watch video or try live demo.

ternary-tree illustrated

Usage

crate

Docs https://docs.rs/im_ternary_tree/ .

use im_ternary_tree::TernaryTreeList;

println!("{}", TernaryTreeList::<usize>::from(&[]));

// assoc
let origin5 = [1, 2, 3, 4, 5];
let data5 = TernaryTreeList::from(&origin5);
let updated = data5.assoc(3, 10);

println!("{}", data5.format_inline());
println!("{}", updated.format_inline());

assert_eq!(updated.unsafe_get(3), 10);

Optimizations

方案设计的中文介绍 https://www.bilibili.com/video/BV1z44y1a7a6/

This library has special optimizations on push_right and pop_left with tricks from finger-tree.

And as its size grows, it's always operating on a shallow branch at right end, wasting fewer nodes for indexing new elements, a random demo looks like:

ternary-tree illustrated

Also the left branches are kept shallow on purpose so it can be cheaper in pop_left. Totally inspired by finger-tree.

Known Issues

  • no optimizations on pop_right and push_left.
  • elements in the middle could be inside deep branches, leading to slow performance.

License

MIT

No runtime deps