| iMatix home page | << | < | > | >> |
![]() Version 1.91 |
#include "sfltree.h" void tree_delete (TREE **root, void *tree)
Deletes a node from a tree. Does not deallocate any memory.
{ TREE *youngest, *elder; TREE_COLOUR colour; if ((!tree) || (tree == TREE_NULL)) return; if ((((TREE *) tree)-> left == TREE_NULL) || (((TREE *) tree)-> right == TREE_NULL)) /* elder has a TREE_NULL node as a child */ elder = tree; else { /* find tree successor with a TREE_NULL node as a child */ elder = ((TREE *) tree)-> right; while (elder-> left != TREE_NULL) elder = elder-> left; } /* youngest is elder's only child */ if (elder-> left != TREE_NULL) youngest = elder-> left; else youngest = elder-> right; /* remove elder from the parent chain */ youngest-> parent = elder-> parent; if (elder-> parent) if (elder == elder-> parent-> left) elder-> parent-> left = youngest; else elder-> parent-> right = youngest; else *root = youngest; colour = elder-> colour; if (elder != tree) { /* JS 1997/11/18: This is from the original code. I have changed it because our implementation knows nothing about the data, and should handle varying size nodes within a single tree, provided the part of the data used for comparison remains the same. Plus just moving the data around will mess up any other pointers to it. tree-> Data = elder-> Data; */ elder-> left = ((TREE *) tree)-> left; elder-> right = ((TREE *) tree)-> right; elder-> parent = ((TREE *) tree)-> parent; elder-> colour = ((TREE *) tree)-> colour; if (((TREE *) tree)-> parent) if (tree == ((TREE *) tree)-> parent-> left) ((TREE *) tree)-> parent-> left = elder; else ((TREE *) tree)-> parent-> right = elder; else *root = elder; } if (colour == BLACK) delete_fixup (root, youngest); }
| << | < | > | >> |
![]() |