Ignore:
Timestamp:
Feb 7, 2001, 7:30:59 PM (25 years ago)
Author:
umoeller
Message:

misc. changes

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/helpers/tree.c

    r21 r33  
    1717 *      tree sorting/comparison. This implementation is released
    1818 *      under the GPL.
     19 *
     20 *      <B>Introduction</B>
     21 *
     22 *      Binary trees are different from linked lists in that items
     23 *      are not simply linked sequentially, but instead put into
     24 *      a tree-like structure.
     25 *
     26 *      For this, the functions here use the TREE structure. You can
     27 *      easily see that this has the "left" and "right" members,
     28 *      which make up the tree.
     29 *
     30 *      In addition, each tree has a "tree root" item, from which all
     31 *      other tree nodes can be reached by following the "left" and
     32 *      "right" pointers.
     33 *
     34 *      Per definition, in our trees, if you follow the "left" pointer,
     35 *      you will reach an item which is "greater than" the current node.
     36 *      Reversely, following the "right" pointer will lead you to a
     37 *      node which is "less than" the current node.
     38 *
     39 *      The implementation here has the following characteristics:
     40 *
     41 *      -- We have "binary" trees. That is, there are only "left" and
     42 *         "right" pointers.
     43 *
     44 *      -- The tree is always "balanced". The tree gets completely
     45 *         reordered when items are added/removed to ensure that
     46 *         all paths through the tree are approximately the same
     47 *         length. This avoids the "worst case" scenario that some
     48 *         paths grow terribly long while others remain short, which
     49 *         can make searching very inefficient.
     50 *
     51 *      -- The tree nodes are marked as either "red" or "black", which
     52 *         is an algorithm to allow the implementation of 2-3-4 trees
     53 *         using a binary tree only. I don't fully understand how this
     54 *         works, but essentially, "red" nodes represent a 3 or 4 node,
     55 *         while "black" nodes are plain binary nodes.
     56 *
     57 *      As much as I understand about all this, red-black balanced
     58 *      binary trees are the most efficient tree algorithm known to
     59 *      mankind. As long as you are sure that trees are more efficient
     60 *      in your situation than a linked list in the first place (see
     61 *      below for comparisons), use the functions in here.
    1962 *
    2063 *      <B>Using binary trees</B>
    … …  
    3174 *      for a sample.
    3275 *
    33  *      Each TREE node does not only contain data, but also an
    34  *      "id" field. The order of nodes in the tree is determined
    35  *      by calling a node comparison function provided by the caller
    36  *      (which you must write). This takes two "id" values and must
    37  *      return:
    38  *
    39  +           0: id1 == id2
    40  +          -1: id1 < id2
    41  +          +1: id1 > id2
    42  *
    4376 *      Initialize the root of the tree with treeInit(). Then
    4477 *      add nodes to the tree with treeInsertID() and remove nodes
    … …  
    4881 *      root with TREE_NULL.
    4982 *
     83 *      Most functions in here come in two flavors.
     84 *
     85 *      -- You can provide a comparison function and use the "Node"
     86 *         flavors of these functions. This is useful, for example,
     87 *         if you are storing strings. You can then write a short
     88 *         comparison function which does a strcmp() on the data
     89 *         of tree nodes.
     90 *
     91 *         The order of nodes in the tree is determined by calling a
     92 *         node comparison function provided by the caller
     93 *         (which you must write). This takes two TREE pointers and
     94 *         must return:
     95 *
     96 +           0: tree1 == tree2
     97 +          -1: tree1 < tree2
     98 +          +1: tree1 > tree2
     99 *
     100 *      -- The "ID" functions (e.g. treeInsertID) do not require
     101 *         a comparison function, but will use the "id" member of
     102 *         the TREE structure instead. If this flavor is used, an
     103 *         internal comparison function is used for comparing the
     104 *         "id" fields, which are plain ULONGs.
     105 *
     106 *      <B>Trees vs. linked lists</B>
     107 *
    50108 *      Compared to linked lists (as implemented by linklist.c),
    51109 *      trees allow for much faster searching.
    52110 *
    53  *      Assuming a linked list contains N items, then searching the
    54  *      list for an item will take an average of N/2 comparisons
     111 *      Assuming a linked list contains N items, then searching a
     112 *      linked list for an item will take an average of N/2 comparisons
    55113 *      and even N comparisons if the item cannot be found (unless
    56114 *      you keep the list sorted, but linklist.c doesn't do this).
    … …  
    72130 *         nodes because the tree is always sorted.
    73131 *
    74  *      -- You must always supply a comparison function to allow the
    75  *         tree functions to sort the tree.
     132 *      -- If you are not using the "ID" flavors, you must supply a
     133 *         comparison function to allow the tree functions to sort the tree.
    76134 *
    77135 *      -- As opposed to a LISTNODE, the TREE structure (which
    … …  
    134192
    135193/*
     194 * fnCompareIDs:
     195 *
     196 *added V0.9.9 (2000-02-06) [umoeller]
     197 */
     198
     199int fnCompareIDs(unsigned long id1, unsigned long id2)
     200{
     201    if (id1 < id2)
     202        return -1;
     203    if (id1 > id2)
     204        return +1;
     205    return (0);
     206}
     207
     208/*
    136209 *@@ treeInsertID:
    137210 *      inserts a node into an existing tree.
    … …  
    169242 +          treeInsertID(&TreeRoot,
    170243 +                     (TREE*)pTreeItem,
    171  +                     fnCompare,       // your comparison function
    172244 +                     FALSE);
    173245 *
    … …  
    179251 *          returned if a tree item with the specified ID already
    180252 *          exists.
     253 *
     254 *@@changed V0.9.9 (2000-02-06) [umoeller]: removed comparison func
    181255 */
    182256
    183257int treeInsertID(TREE **root,             // in: root of tree
    184258                 TREE *tree,              // in: new tree node
    185                  FNTREE_COMPARE_IDS *comp,      // in: comparison function
    186259                 BOOL fAllowDuplicates)   // in: whether duplicates with the same ID are allowed
    187260{
    … …  
    198271    {
    199272        parent  = current;
    200         last_comp = comp(tree->id, current->id);
     273        last_comp = fnCompareIDs(tree->id, current->id);
    201274        switch (last_comp)
    202275        {
    … …  
    211284    }
    212285
    213     // setup new node
    214     ((TREE *) tree)->parent = parent;
    215     ((TREE *) tree)->left   = TREE_NULL;
    216     ((TREE *) tree)->right  = TREE_NULL;
    217     ((TREE *) tree)->colour = RED;
     286    // set up new node
     287    ((TREE*)tree)->parent = parent;
     288    ((TREE*)tree)->left   = TREE_NULL;
     289    ((TREE*)tree)->right  = TREE_NULL;
     290    ((TREE*)tree)->colour = RED;
    218291
    219292    // insert node in tree
    … …  
    268341    }
    269342
    270     // setup new node
    271     ((TREE *) tree)->parent = parent;
    272     ((TREE *) tree)->left   = TREE_NULL;
    273     ((TREE *) tree)->right  = TREE_NULL;
    274     ((TREE *) tree)->colour = RED;
     343    // set up new node
     344    ((TREE*)tree)->parent = parent;
     345    ((TREE*)tree)->left   = TREE_NULL;
     346    ((TREE*)tree)->right  = TREE_NULL;
     347    ((TREE*)tree)->colour = RED;
    275348
    276349    // insert node in tree
    … …  
    464537        return TREE_INVALID_NODE;
    465538
    466     if (    (((TREE *) tree)->left  == TREE_NULL)
    467          || (((TREE *) tree)->right == TREE_NULL)
     539    if (    (((TREE*)tree)->left  == TREE_NULL)
     540         || (((TREE*)tree)->right == TREE_NULL)
    468541       )
    469542        // descendent has a TREE_NULL node as a child
    … …  
    472545  {
    473546        // find tree successor with a TREE_NULL node as a child
    474         descendent = ((TREE *) tree)->right;
     547        descendent = ((TREE*)tree)->right;
    475548        while (descendent->left != TREE_NULL)
    476549            descendent = descendent->left;
    … …  
    499572
    500573    if (descendent != (TREE *) tree)
    501   {
     574    {
    502575        // Conceptually what we are doing here is moving the data from
    503576        // descendent to tree.  In fact we do this by linking descendent
    504577        // into the structure in the place of tree.
    505         descendent->left   = ((TREE *) tree)->left;
    506         descendent->right  = ((TREE *) tree)->right;
    507         descendent->parent = ((TREE *) tree)->parent;
    508         descendent->colour = ((TREE *) tree)->colour;
     578        descendent->left   = ((TREE*)tree)->left;
     579        descendent->right  = ((TREE*)tree)->right;
     580        descendent->parent = ((TREE*)tree)->parent;
     581        descendent->colour = ((TREE*)tree)->colour;
    509582
    510583        if (descendent->parent)
    511       {
     584        {
    512585            if (tree == descendent->parent->left)
    513586                descendent->parent->left  = descendent;
    514587            else
    515588                descendent->parent->right = descendent;
    516       }
     589        }
    517590        else
    518591            *root = descendent;
    … …  
    618691 *@@ treeFindEQID:
    619692 *      finds a node with ID exactly matching that provided.
    620  *      To find a tree node, your comparison function must
    621  *      compare the tree node IDs.
    622693 */
    623694
    624695void* treeFindEQID(TREE **root,
    625                    unsigned long id,
    626                    FNTREE_COMPARE_IDS *comp)
     696                   unsigned long id)
    627697{
    628698    TREE
    … …  
    632702    found = NULL;
    633703    while (current != TREE_NULL)
    634         switch (comp(current->id, id))
     704        switch (fnCompareIDs(current->id, id))
    635705        {
    636706            case -1: current = current->right; break;
    … …  
    651721
    652722void* treeFindGEID(TREE **root,
    653                    unsigned long idFind,
    654                    FNTREE_COMPARE_IDS *comp)
     723                   unsigned long idFind)
    655724{
    656725    TREE
    … …  
    660729    found = NULL;
    661730    while (current != TREE_NULL)
    662         switch (comp(current->id, idFind))
     731        switch (fnCompareIDs(current->id, idFind))
    663732        {
    664733            case -1: current = current->right; break;
    … …  
    873942    {
    874943        process(tree, pUser);
    875         treeTraverse (((TREE *) tree)->left,  process, pUser, method);
    876         treeTraverse (((TREE *) tree)->right, process, pUser, method);
     944        treeTraverse (((TREE*)tree)->left,  process, pUser, method);
     945        treeTraverse (((TREE*)tree)->right, process, pUser, method);
    877946    }
    878947    else if (method == 2)
    879948    {
    880         treeTraverse (((TREE *) tree)->left,  process, pUser, method);
    881         treeTraverse (((TREE *) tree)->right, process, pUser, method);
     949        treeTraverse (((TREE*)tree)->left,  process, pUser, method);
     950        treeTraverse (((TREE*)tree)->right, process, pUser, method);
    882951        process(tree, pUser);
    883952    }
    884953    else
    885954    {
    886         treeTraverse (((TREE *) tree)->left,  process, pUser, method);
     955        treeTraverse (((TREE*)tree)->left,  process, pUser, method);
    887956        process(tree, pUser);
    888         treeTraverse (((TREE *) tree)->right, process, pUser, method);
     957        treeTraverse (((TREE*)tree)->right, process, pUser, method);
    889958    }
    890959}
Note: See TracChangeset for help on using the changeset viewer.