Invisible <voi### [at] devnull> wrote:
> I wonder if any BST self-balancing algorithms are applicable to BSP?

  AFAIK, no.

  A Kd-tree is basically a binary search tree for dimensions higher than 1.
It's a binary tree, and at each node in the tree you go to the left or the
right subtree depending on which side of the axis (or axial plane in 3
dimensions) the searched point is in relation to the current node. (The axis
or axial plane changes at each level in the tree.)

  Adding a node to a balanced Kd-tree is a difficult operation and, AFAIK,
cannot be optimized in the same way as regular BSTs can. Wikipedia seems
to confirm that: http://en.wikipedia.org/wiki/Kd-tree

  "Balancing a kd-tree requires care. Because kd-trees are sorted in
multiple dimensions, the tree rotation technique cannot be used to
balance them - this may break the invariant."

-- 
                                                          - Warp

Post a reply to this message