Re:Interesting data structures: the BK-tree
by jwatte on Monday April 03, 2017 @09:25PM
(#14028795)
An ordered binary tree still can fail to N if you allow duplicates.
(AFAICT: Most of these trees have a "typical" case search time of some root of N based on dimensionality. The easiest way to visualize this is to consider a walk from the perimeter to a cell in Voroni space, and how many cells that will search.)
(AFAICT: Most of these trees have a "typical" case search time of some root of N based on dimensionality. The easiest way to visualize this is to consider a walk from the perimeter to a cell in Voroni space, and how many cells that will search.)