Skip to content

Structural sharing unbalanced 2-3 tree with tricks like finger-tree.

Notifications You must be signed in to change notification settings

calcit-lang/ternary-tree.rs

This branch is up to date with main.

Folders and files

NameName
Last commit message
Last commit date

Latest commit

efbbf2f · Feb 27, 2024

History

90 Commits
Sep 2, 2023
Apr 28, 2022
Feb 25, 2024
Feb 3, 2024
Feb 25, 2024
Feb 25, 2024
Feb 3, 2024
Nov 6, 2021
Feb 25, 2024
Jul 26, 2022

Repository files navigation

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