Next: Division of Space by
Up: k-d Trees
Previous: Adding elements to k-d
Contents
Deletion similar to BST but slightly harder.
- Step1
- find node to be deleted.
- Step2
- two cases must be handled :
- No children - replace ptr to node by NULL
- Has children - replace node by minimum node in right subtree. If no right subtree exists, then first move left subtree to become right subtree.
root
2006-04-11