Difference between revisions of "Thread:User talk:Rednaxela/kD-Tree/Unit tests for KdTree/reply (5)"
Jump to navigation
Jump to search
(Reply to Unit tests for KdTree) |
|||
| Line 8: | Line 8: | ||
* If I understand what you mean... You should note that the structure of the tree is such that you can't just remove a leaf node, because every node must either be a leaf node or have two child nodes. To prune back the tree after removing items, you'd need to implement a "merge siblings" algorithm. This algorithm would need to first check that the combined size of both would fit comfortably in one node, and if that's the case basically perform the reverse of what "splitLeafNode" does. It'll also need to take into account the possibility that one sibling may not be a leaf node while the other is. | * If I understand what you mean... You should note that the structure of the tree is such that you can't just remove a leaf node, because every node must either be a leaf node or have two child nodes. To prune back the tree after removing items, you'd need to implement a "merge siblings" algorithm. This algorithm would need to first check that the combined size of both would fit comfortably in one node, and if that's the case basically perform the reverse of what "splitLeafNode" does. It'll also need to take into account the possibility that one sibling may not be a leaf node while the other is. | ||
| − | + | Some other notes: | |
* You don't appear to be changing the "size" of the node itself, just the parents, which would be a problem. I also don't know that "ArrayUtil.remove" is what you want there. | * You don't appear to be changing the "size" of the node itself, just the parents, which would be a problem. I also don't know that "ArrayUtil.remove" is what you want there. | ||
Latest revision as of 00:24, 28 May 2012
To answer your questions:
- Actually, technically you don't need to adjust ANY bounds at all. It won't affect the correctness of the result. The only consequence is that the searches may be slightly slower than optimal. If you are adjusting the bounds though, you might as well adjust the parent ones as well, because that's where a large chunk of the (smallish) performance impact would be.
- On one hand adjusting the bounds makes the removal slower, but on the other hand it makes the search a little faster. To really know if it's worth adjusting the bounds, would probably require benchmarking with some code that's making realistic use of the removal.
- To add it nicely to the iterator, I think you'd need to have the iterator keep track of the last point it returned, so it can call a remove on that.
- If I understand what you mean... You should note that the structure of the tree is such that you can't just remove a leaf node, because every node must either be a leaf node or have two child nodes. To prune back the tree after removing items, you'd need to implement a "merge siblings" algorithm. This algorithm would need to first check that the combined size of both would fit comfortably in one node, and if that's the case basically perform the reverse of what "splitLeafNode" does. It'll also need to take into account the possibility that one sibling may not be a leaf node while the other is.
Some other notes:
- You don't appear to be changing the "size" of the node itself, just the parents, which would be a problem. I also don't know that "ArrayUtil.remove" is what you want there.
- Note that the "data" and "points" arrays have extra capacity beyond what's used and that "size" (or "_count" in the case of Ojd's C# variant) tracks the number of elements actually used.
- (I also can't seem to find any documentation of a "ArrayUtil.remove" in either Java or C# so I'm a bit confused)
- The code to adjust the bounds there appears to be incorrect. It looks like what's happening in that code is extending the bounds to contain the removed point... and the bounds already contain that anyway.
