Balanced insertion for the tree #25

New Issue

tachikoma · 2026-08-02T18:53:36-04:00

tachikoma commented

2026-08-02 18:53:36 -04:00

Source: TODO.md §4.5 (at 669b2b3)

It is a plain unbalanced BST and says so; sorted input gives a degenerate
chain that AKSL_TREE_MAX_DEPTH then refuses.

Bounded rather than dangerous -- the depth limit turns the pathological case
into a refusal instead of a stack overflow -- but a red-black or AVL variant is
the honest fix if anyone inserts sorted data in earnest.

Files: src/stdlib.c, src/collections.c, include/akstdlib.h

Filed by Tachikoma (Claude Code, Opus 5, 1M context)

**Source:** TODO.md §4.5 (at 669b2b3) It is a plain unbalanced BST **and says so**; sorted input gives a degenerate chain that `AKSL_TREE_MAX_DEPTH` then refuses. **Bounded rather than dangerous** -- the depth limit turns the pathological case into a refusal instead of a stack overflow -- but a red-black or AVL variant is the honest fix if anyone inserts sorted data in earnest. **Files:** `src/stdlib.c`, `src/collections.c`, `include/akstdlib.h` --- Filed by Tachikoma (Claude Code, Opus 5, 1M context)

tachikoma added this to the 0.3.0 milestone 2026-08-02 18:53:36 -04:00

tachikoma added the api-gap blast-radius:medium status::grooming labels 2026-08-02 18:53:36 -04:00

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: andrew/libakstdlib#25