28个版本
| 0.0.18 | 2024年2月25日 |
|---|---|
| 0.0.17 | 2024年2月17日 |
| 0.0.11 | 2022年7月26日 |
| 0.0.10 | 2022年5月31日 |
| 0.0.1-a8 | 2021年11月21日 |
#567 in 数据结构
在 2 crates 中使用
705KB
2.5K SLoC
Calcit的持久化结构共享树
2-3树的变体，增强了三叉分支，使用如 finger-tree 等技巧优化。
t.pop_left() 和 t.push_right(..) 在最佳情况下优化为摊销 O(1)，在重新结构化时为 O(log n)
用法
文档 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);
优化
方案设计的中文介绍 https://www.bilibili.com/video/BV1z44y1a7a6/
此库对 push_right 和 pop_left 进行了特殊的优化，使用了来自 finger-tree 的技巧。
随着其大小的增长，它始终在右端的浅分支上进行操作，减少了索引新元素时所需节点的数量，一个随机演示看起来像
另外，故意保持了左侧分支的浅层结构，以便在 pop_left 中更便宜。完全受 finger-tree 启发。
已知问题
- 没有对
pop_right和push_left进行优化。 - 中间的元素可能位于深层分支中，导致性能缓慢。
许可证
MIT