Program to create Red-Black Trees 
Author Message
 Program to create Red-Black Trees

I am looking for a Pascal program which creates ``red-black trees''.

The red-black trees are a version of a 2-3-4 node tree which is a true
binary tree (balanced).  It uses red and black links to show whether
the nodes are on the same level as a parent node or not.

I have most of the algorithm down (which is all I need to do) but I
would like to get some code (preferrably in Turbo Pascal) which I
could get to work and trace its operation.

The algorithm I have thus far consists of the following:

     o  Procedure ``insert'' to bring in a new element (character)
        and trace it down the tree and insert it in the proper location

     o  Procedure to ``rotate'' a 4-node (2 consecutive red links) and
        make it a balanced 4-node

     o  Procedure to ``split'' a 4-node and make the two children
        linked to the parent with a black link

   The ``rotate'' occurs when a new node is added at the same level
and it creates the two red links in a row.  
   The ``split'' occurs when a new node is being brought down the tree
and the algorithm encounters a balanced 4-node.

Any suggestions on implementation or comments will be appreciated.

     Thanks in advance      

               Rusty Nelson
               (303) 538-2465
      I am in the process of switching machines, so please respond to
all three of the following e-mail addresses so I have a better chance
of getting your response.
            ...drutx!druks!rgn              
            ...drutx!drumn!rgn              
            ...drutx!druid!rgn              

   Thanks again!!!!!!  8^)



Mon, 19 Apr 1993 18:08:00 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. searching trees (AVL, 2-3-4 and red-black trees)

2. Red Black Tree - delete function

3. AVL and red-black trees

4. need code for red-black binary search tree

5. Red-Black tree in PROLOG

6. Red Black Tree in PROLOG

7. red-black trees in fortran

8. Red - black trees

9. Red-Black-Trees and Fortran 2003 Features

10. Red-Black trees

11. Fortran Powerstation Quickwin graphics - black on black

12. Black mouse on black canvas

 

 
Powered by phpBB® Forum Software