# ChaosTree

A zero-dependency Java library of sorted Set and Map implementations, including AVL trees, red-black trees, B-trees and B+ trees, built for cache locality and compliant with JDK 21's SequencedCollection interfaces.

ChaosTree implements Java's NavigableMap and NavigableSet as AVL trees, red-black trees, B-trees and B+ trees, choosing between two engines depending on the workload: an N-ary family (BTree, BPlusTree) for high read throughput and large range scans, packing nodes into pre-allocated arrays for cache locality, and a binary family (AVL, RBT) for fast point queries and everyday storage.

Bulk loading is O(N) through `buildFromSorted` and `importFlatMatrix`, with a tunable fill factor. The library is fully compliant with JDK 21's `SequencedCollection`, `SequencedSet` and `SequencedMap` interfaces, though `addFirst()` and `addLast()` are unsupported and fail fast, since these are strictly sorted structures. It supports serialization and cloning, with O(N) bulk-load restoration on deserialize.

Correctness is checked against more than 214,000 generated Guava Testlib cases for exact `TreeMap`/`TreeSet` semantics, plus property-based fuzzing with Jqwik against `java.util.TreeMap` as a reference. It has no dependencies and is available through Maven or Gradle.

Website: https://chaos-vy.github.io/ChaosTree/