| iMatix home page
| << | < | > | >>
SFL Logo SFL
Version 1.91

 

tree_delete

#include "sfltree.h"
void tree_delete (TREE **root, void *tree)

Synopsis

Deletes a node from a tree. Does not deallocate any memory.

Source Code - (sfltree.c)

{
    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);
}

| << | < | > | >> iMatix Copyright © 1996-98 iMatix