* This routine deletes a node from Tree. The node to be * deleted is specified by the Key for the node and the Data * contents of the node. These two pointers must be identical * to the pointers that were used for the node when it was * originally stored in the tree. A node will be deleted from * the tree only if its key and data pointers are identical * to Key and Data respectively. The
| 262 | * 7/13/89, DSJ, Specify node indirectly by key and data. |
| 263 | */ |
| 264 | void |
| 265 | KDDelete (KDTREE * Tree, FLOAT32 Key[], void *Data) { |
| 266 | int Level; |
| 267 | KDNODE *Current; |
| 268 | KDNODE *Father; |
| 269 | |
| 270 | /* initialize search at root of tree */ |
| 271 | Father = &(Tree->Root); |
| 272 | Current = Father->Left; |
| 273 | Level = NextLevel(Tree, -1); |
| 274 | |
| 275 | /* search tree for node to be deleted */ |
| 276 | while ((Current != NULL) && (!NodeFound (Current, Key, Data))) { |
| 277 | Father = Current; |
| 278 | if (Key[Level] < Current->BranchPoint) |
| 279 | Current = Current->Left; |
| 280 | else |
| 281 | Current = Current->Right; |
| 282 | |
| 283 | Level = NextLevel(Tree, Level); |
| 284 | } |
| 285 | |
| 286 | if (Current != NULL) { /* if node to be deleted was found */ |
| 287 | if (Current == Father->Left) { |
| 288 | Father->Left = NULL; |
| 289 | Father->LeftBranch = Tree->KeyDesc[Level].Min; |
| 290 | } else { |
| 291 | Father->Right = NULL; |
| 292 | Father->RightBranch = Tree->KeyDesc[Level].Max; |
| 293 | } |
| 294 | |
| 295 | InsertNodes(Tree, Current->Left); |
| 296 | InsertNodes(Tree, Current->Right); |
| 297 | FreeSubTree(Current); |
| 298 | } |
| 299 | } /* KDDelete */ |
| 300 | |
| 301 | /** |
| 302 | * This routine searches the K-D tree specified by Tree and |
no test coverage detected