Mixture

[claw at null.net]

On 23/03/97 at 09:40 PM, Furball <K.L.Lo-94 at student.lut.ac.uk> said:

>I read on the usenet about trees and lists.  Currently, I don't have
>time for any research so what's a tree?  I prolly know how to do it
>but don't have a name for it (I guess my way thru coding and I don't
>give my work fancy names).  Prolly the wrong place to ask this
>question...Hmm..

You *really* need to get a basic algorithm book.  Your local library
should have several.  No offense, but a lot of these concepts, like
trees, lists, tables, balanced trees, choice of search/sort
algorithms, hash tables, choice and design of hashing algorithms, skip
lists, queues, FIFOs, LIFOs, etc are pretty basic, and your coding
will be stilted until you get a handle on them.

LIST: A list is a simple fixed order structure of nodes where each
node on the list contains a link to the next node on the list (singley
linked).  A variation hs each node linked to both the next and
previous ndoes in the list.  Advantages of lists enclude easy
insertion and removal of nodes, as well as traversal of the list.  


  (node)->(node)->(node)->(node)...etc

Sample node structure:

  struct t_test {
    struct t_test *prev; // Only present for doubley linked lists.
    struct t_test *next;
    int type;
    char *pname;
    ...other data members...
  } T_TEST;

TREE: Similar to lists, except that each node is connected to multiple
child nodes (usually 2) in a descending "tree" like structure:

                node
               /    \
           node      ...........
          /    \                \
      node      node             \
     /    \    /    \             node
 node   node node  node          /    \
/    \ /   \/    \/    \      node   node  

etc.  

Typically the relationship between a node and its children defines a
sorting order.  Thus all the "left" children may be smaller than all
the "right" children.  This makes searches very rapid and cheap. 
Similarly, sorted insertions are also cheap.

Sample tree node structure:

  struct t_test {
    struct t_test *parent; // Usually not present
    struct t_test *right;
    struct t_test *left;
    int type;
    char *pname;
    ...other data members...
  } T_TEST;

Note: Often the data members for nodes are only valid for leaf nodes
(ie no children (NULL pointers)).  This creates an instantly sorted
tree.  Traversing the leaves in order from left to right results in a
sorted sequence.

>A balance is needed for this kind of creation process so points are
>not assigned in a random fashion and some more petty players keep
>remaking characters hoping for a good roll.  This kind of thing works
>better for muds where 5 mins real time equates to 1 game hour.  Coz
>if skills go up quite quickly then there will be the case of a 12
>year old having more skills than an 80 yr old.

Cheap solution: never report stats.  Its one of the better side
effects of numberless systems.

--
J C Lawrence                               Internet: claw at null.net
----------(*)                              Internet: coder at ibm.net
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...