Repository files navigation

This library implements a variant of a 2-3 tree with ternary branching, also known as a ternary search tree. It is further enhanced with finger-tree-inspired optimizations.

Thepop_left() andpush_right() operations are optimized to be amortizedO(1) in the best cases andO(log n) when restructuring is involved.

For a visual explanation of the tree's layout (from 0 to 159), you can watch thisvideo or try thelive demo.

API documentation is available ondocs.rs.

use im_ternary_tree::TernaryTreeList;println!("{}",TernaryTreeList::<usize>::from(&[]));// Create a new list with an updated value at a specific indexlet 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);

A more detailed, Chinese-language explanation of the design is available in thisvideo.

This library features special optimizations forpush_right andpop_left, inspired by the design offinger trees.

As the size of the tree grows, operations are focused on a shallow branch at the right end. This minimizes the number of nodes that need to be indexed for new elements. A random demonstration of this can be seen below:

The left branches are also intentionally kept shallow, which reduces the cost ofpop_left operations.

Benchmarks comparingTernaryTreeList withstd::vec::Vec andstd::collections::VecDeque show a clear performance profile. As an immutable data structure,TernaryTreeList has some overhead compared to its mutable counterparts but offers significant advantages in specific scenarios.

• push_right /drop_right (Appending/Popping from the tail):

  • Vec andVecDeque are significantly faster, as they are mutable and optimized for O(1) amortized operations at the tail.
  • TernaryTreeList is slower due to the nature of immutable structures, which require creating new tree nodes.

• push_left /drop_left (Prepending/Popping from the head):

  • TernaryTreeList isdramatically faster thanVec.Vec::insert(0, ...) is an O(n) operation, whileTernaryTreeList's finger-tree-inspired optimizations make head operations much more efficient.
  • VecDeque is still the fastest, as it is a mutable data structure specifically designed for O(1) head and tail operations.

Conclusion:

• UseTernaryTreeList when:
  • You need animmutable (persistent) list.
  • You requireefficient push and pop operations on both ends of the list, and the performance of a mutable deque is not required.
• UseVec orVecDeque when:
  • Mutability is acceptable.
  • You need the absolute best performance for purely mutable operations.

• pop_right lacks some optimizations.
• Elements in the middle of the tree may be deeply nested, resulting in slower performance for accessing or modifying them.

This project is licensed under the MIT License.