Re: [math-fun] Asymptotically zero memory wasted inside dictionaries

Any advantage over standard B trees?

--Well, at least based on http://en.wikipedia.org/wiki/B-tree the B tree wastes 1-2 pointers worth of memory per data item in non-leaf nodes, and the leaf nodes could be made to contain no pointers. So in the limit of large branching factor B, the leaf nodes dominate the scene with only fraction of order 1/B of the data in non-leaf nodes, and if we make B of order logN, then this is superior to my trees by a sqrt(logN) factor as far as memory waste is concerned. So I think Tom Rokicki is right: B trees are superior. [My trees probably do have some minor advantages though, since you can try to steal any property of some breed of binary balanced trees, such as O(1) pointer changes per op?]