Binary tree search in PL1 
Author Message
 Binary tree search in PL1

I need help to implement an efficient 'binary search tree' in PL1.

I read millions of records from tape and build a binary tree, but this is
not efficient.
A more efficient solution would be a balanced binary tree, maybe a
red-black tree.
If anyone have suggestion for implementations of red-black tree in PL1 i
would be
happy ! (procedures for search, insert, delete and rotations would be nice
:-) )

Greeting
Lars Linnemann

Here is some of the code:
declare of tree:
DCL  1  NODE      BASED,    /* binary tree */
     2  RIGHT              POINTER,                                
     2  LEFT                POINTER,                                
     2  KEY                 FIXED(9),                                
     2  DATE_USED    FIXED(9),                                
     2  OCCURS         FIXED BIN(31);              

Mail loop:            
READ FILE (DA305I) SET  (PTRSTAM);
DO WHILE (^EOF);
   CALL INSERT(DATE_NEW, KEY_NEW, ROOT);
   READ FILE (DA305I) SET  (PTRSTAM);
END;

The insert procedure:
INSERT:                                                          
PROC(DATE_NEW,KEY_NEW,P)  RECURSIVE;                                    
   DCL  DATE_NEW    FIXED(9); /* DATE KEY IS USED */                
   DCL  KEY_NEW      FIXED(9); /* KEY     */                
   DCL  P                    POINTER;  /* NODE POINTER            */      

   IF P = NULL THEN /* ALLOCATE NEW NODE */                    
      DO;                                                          
         ALLOC NODE SET(P);                                                

         IF ROOT = NULL THEN ROOT = P;                              
         P->RIGHT, P->LEFT = NULL;                                
         P->KEY   = KEY_NEW;                                      
         P->DATE_USED = DATE_NEW;                                      
         P->ACCOURS   = 1;                                          
      END;                                                          
   ELSE                                                            
     IF P->KEY = KEY_NEW THEN  /* DUPLICATE KEY */
        DO;                                                        
           P->OCCURS = P->OCCURS + 1;   /* COUNT NUMBER OF TIMES KEY IS
USED */                
           IF P->DATE_USED < DATE_NEW THEN            
              P->DATE_USED = DATE_NEW;                  
        END;                                            
     ELSE                                              
       IF P->KEY < KEY_NEW THEN   /* INSERT RIGHT   */  
         DO;                                            
            CALL INSERT(DATE_NEW,KEY_NEW,P->RIGHT);    
         END;                                          
       ELSE                       /* INSERT LEFT */  
         DO;                                            
            CALL INSERT(DATE_NEW,KEY_NEW,P->LEFT);      
         END;                                          
END INSERT;                                            



Sun, 13 Oct 2002 03:00:00 GMT  
 Binary tree search in PL1

Quote:

> I need help to implement an efficient 'binary search tree' in PL1.

> I read millions of records from tape and build a binary tree, but this is
> not efficient.
> A more efficient solution would be a balanced binary tree, maybe a
> red-black tree.
> If anyone have suggestion for implementations of red-black tree in PL1 i
> would be
> happy ! (procedures for search, insert, delete and rotations would be nice
> :-) )

There is a set of procedures in my book "Introduction to PL/I, Algorithms,
and Structured Programming" ISBN 0-9596384-9-0, for inserting, balancing,
deleting, etc elements in red-black binary trees.
Quote:

> Greeting
> Lars Linnemann

> Here is some of the code:
> declare of tree:
> DCL  1  NODE      BASED,    /* binary tree */
>      2  RIGHT              POINTER,
>      2  LEFT                POINTER,
>      2  KEY                 FIXED(9),
>      2  DATE_USED    FIXED(9),
>      2  OCCURS         FIXED BIN(31);

> Mail loop:
> READ FILE (DA305I) SET  (PTRSTAM);
> DO WHILE (^EOF);
>    CALL INSERT(DATE_NEW, KEY_NEW, ROOT);
>    READ FILE (DA305I) SET  (PTRSTAM);
> END;

> The insert procedure:
> INSERT:
> PROC(DATE_NEW,KEY_NEW,P)  RECURSIVE;
>    DCL  DATE_NEW    FIXED(9); /* DATE KEY IS USED */
>    DCL  KEY_NEW      FIXED(9); /* KEY     */
>    DCL  P                    POINTER;  /* NODE POINTER            */

>    IF P = NULL THEN /* ALLOCATE NEW NODE */
>       DO;
>          ALLOC NODE SET(P);

>          IF ROOT = NULL THEN ROOT = P;
>          P->RIGHT, P->LEFT = NULL;
>          P->KEY   = KEY_NEW;
>          P->DATE_USED = DATE_NEW;
>          P->ACCOURS   = 1;
>       END;
>    ELSE
>      IF P->KEY = KEY_NEW THEN  /* DUPLICATE KEY */
>         DO;
>            P->OCCURS = P->OCCURS + 1;   /* COUNT NUMBER OF TIMES KEY IS
> USED */
>            IF P->DATE_USED < DATE_NEW THEN
>               P->DATE_USED = DATE_NEW;
>         END;
>      ELSE
>        IF P->KEY < KEY_NEW THEN   /* INSERT RIGHT   */
>          DO;
>             CALL INSERT(DATE_NEW,KEY_NEW,P->RIGHT);
>          END;
>        ELSE                       /* INSERT LEFT */
>          DO;
>             CALL INSERT(DATE_NEW,KEY_NEW,P->LEFT);
>          END;
> END INSERT;



Mon, 14 Oct 2002 03:00:00 GMT  
 Binary tree search in PL1
Thanks,
I tried to find the book in my local bookshop (in Denmark), and there is a
long wait for delivery (at least 5 - 6 weeks).
And I think it was the same with Amazon.com, (about 5 - 6 weeks).
And it is now that I need the program.

But I think I will buy the book anyway.

Quote:

> There is a set of procedures in my book "Introduction to PL/I,
Algorithms,
> and Structured Programming" ISBN 0-9596384-9-0, for inserting, balancing,
> deleting, etc elements in red-black binary trees.



Mon, 14 Oct 2002 03:00:00 GMT  
 Binary tree search in PL1

Quote:

> Thanks,
> I tried to find the book in my local bookshop (in Denmark), and there is a
> long wait for delivery (at least 5 - 6 weeks).
> And I think it was the same with Amazon.com, (about 5 - 6 weeks).
> And it is now that I need the program.

We can ship the book direct, in which case delivery is
about 2 weeks.
Quote:

> But I think I will buy the book anyway.

> > There is a set of procedures in my book "Introduction to PL/I,
> Algorithms,
> > and Structured Programming" ISBN 0-9596384-9-0, for inserting, balancing,
> > deleting, etc elements in red-black binary trees.



Mon, 14 Oct 2002 03:00:00 GMT  
 Binary tree search in PL1
How much?,
I ordered from amazon a month ago - still waiting
Subtotal:                       $    59.80
Shipping & Handling:            $    35.95
                                ----------
Purchase Total:                 $    95.75
?
----------------------------------------



Quote:


> > Thanks,
> > I tried to find the book in my local bookshop (in Denmark), and
there is a
> > long wait for delivery (at least 5 - 6 weeks).
> > And I think it was the same with Amazon.com, (about 5 - 6 weeks).
> > And it is now that I need the program.

> We can ship the book direct, in which case delivery is
> about 2 weeks.

> > But I think I will buy the book anyway.

> > > There is a set of procedures in my book "Introduction to PL/I,
> > Algorithms,
> > > and Structured Programming" ISBN 0-9596384-9-0, for inserting,
balancing,
> > > deleting, etc elements in red-black binary trees.

Sent via Deja.com http://www.deja.com/
Before you buy.


Mon, 14 Oct 2002 03:00:00 GMT  
 Binary tree search in PL1

      |How much?,
      |I ordered from amazon a month ago - still waiting
      |Subtotal:                       $    59.80
      |Shipping & Handling:            $    35.95
      |                                ----------
      |Purchase Total:                 $    95.75
_____________________________________

$36 for shipping and handling ?!?!?!?

Is it hand delieved by the author ?    Or wrapped with real money ?

Is this usual for Amazon.com ?

Gerard S.



Mon, 14 Oct 2002 03:00:00 GMT  
 Binary tree search in PL1
and all the time the euro is slipping in value against the dollar
- - - -


Quote:

>       |How much?,
>       |I ordered from amazon a month ago - still waiting
>       |Subtotal:                       $    59.80
>       |Shipping & Handling:            $    35.95
>       |                                ----------
>       |Purchase Total:                 $    95.75
> _____________________________________

> $36 for shipping and handling ?!?!?!?

> Is it hand delieved by the author ?    Or wrapped with real money ?

> Is this usual for Amazon.com ?

> Gerard S.

Sent via Deja.com http://www.deja.com/
Before you buy.


Tue, 15 Oct 2002 03:00:00 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Self-Adjusting Binary Search Trees (Splay Trees)

2. Self-Adjusting Binary Search Trees (Splay Trees)

3. Binary Search Trees

4. Binary Search Trees

5. binary search tree

6. BST (yes, that's binary search tree)

7. Breadth first print procedure for binary search trees

8. need code for red-black binary search tree

9. Pls Help! Need binary search tree module

10. binary search tree

11. Binary Search Trees

12. binary search tree

 

 
Powered by phpBB® Forum Software