4 papers
A Comparison of Two Dynamic k-d Trees
Russell A. Brown
Two methods have been proposed for building and modifying a dynamic k-d tree. One method stores the dynamic tree as a single k-d tree and rebalances that tree by rebuilding subtree…
A Dynamic, Self-balancing k-d Tree
Russell A. Brown
The original description of the k-d tree recognized that rebalancing techniques, used for building an AVL or red-black tree, are not applicable to a k-d tree, because these techniq…
Review of Three Algorithms That Build k-d Trees
Russell A. Brown
The original description of the k-d tree recognized that rebalancing techniques, such as used to build an AVL tree or a red-black tree, are not applicable to a k-d tree. Hence, in…
Comparative Performance of the AVL Tree and Three Variants of the Red-Black Tree
Russell A. Brown
This article compares the performance of the AVL tree to the performance of the bottom-up, top-down, and left-leaning red-black trees. The bottom-up red-black tree is faster than t…