#algorithms for Okasaki’s #FP-persistent red-black #trees: specifically how to delete nodes.
on 02015-11-16the interval tree data structure and #algorithms. #trees
on 02015-11-16Binary-search #algorithms results that shows how using an implicit binary search tree packed into an array can roughly double your binary-search speed over merely sorting, due to cache effects. #trees
on 02015-10-19The adaptive radix tree (#trie) “ART” #paper #pdf #toread #trees
on 02015-10-04Tony Finch’s trie based on #DJB’s crit-bit #trees but consuming less memory by branching on nibbles, with a 16-bit sparsity bitmap. #algorithms
on 02015-10-04an adaptive radix tree (#trie) “ART” in C99 #algorithms #trees
on 02015-10-04Andrews’ Twigg and Byde patent application on #stratified-B-trees. Scumbags. #trees #patents
on 02015-09-09this "Stratified B-trees" paper presents “a fully-versioned B-tree with optimal space and the same lookup time as the [copy-on-write] B-tree”, and also supports fully-versioned updates in o(1) IOs in linear space, by merging sorted arrays of (key, version, value) tuples, followed by “density amplification” by de-merging the arrays if they are not dense enough (<⅓) in some of the versions. Nodes are immutable once written. May also be relevant to Cuerda. #algorithms #trees
on 02015-09-09