Deleting nodes from a 2d binary search tree

Question

I was wondering if someone could provide some helpful insight on deleting nodes from a 2d binary search tree.

I understand there's four cases, the first of which I've completed:

1. Deleting a node with no children (a leaf), simple, just set the pointer to that node to null.
2. Deleting a node with one child on the left node and the right node is null.
3. Deleting a node with one child on the right node and the left node is null.
4. Deleting a node with two children, left and right.

I am not sure how to exactly do 2,3, and 4. I've tried to do it iteratively, however, that doesn't seem to be working. I'm assuming this must be done recursively. Can someone please shed some light on how this would be done exactly. This is in java, shouldn't matter though :)

Answer 1

In a 2D tree, all values are stored in the leaf nodes. The internal nodes just serve as pathways towards locating the leaf node. Specifically, the internal nodes define the half planes within which the underlying data is contained. We deal only with data; we do not modify the structural elements of the data structure itself. So, only case 1 above holds. All the others are irrelevant.