Board index » delphi » AVL trees in paskal

AVL trees in paskal

Dear All,

Does anyone know of any web site that contains tutorials about AVL
trees, and has also paskal source code for using them?

Many thanks,
Ron Nely.

 

Re:AVL trees in paskal


{.LW 132}
{***********************************************************************
*                                                                      *
*      AVL.PAS                                                         *
*                                                                      *
*      Implements a structure and routines manipulate the balanced     *
*      AVL tree.                                                       *
*                                                                      *
*      Modifications                                                   *
*      =============                                                   *
*                                                                      *
***********************************************************************}

{.L-}
{$I OPDEFINE.INC}
{.L+}

Unit AVL ;

  Interface
    Uses
      Printer ;

  Const
    Max_Tree_Nodes = 500 ;  { Constant is significant only if an ordered }
                            { array of the AVL tree nodes is desired.    }

  Type
    AVLTreeStr = String[12] ;

    BalanceSet = (Left_Tilt , Neutral , Right_Tilt) ;

    AVLDataRec = Record
                   Key    : AVLTreeStr ;
                   RecOfs : LongInt    ;
                   RecNum : Word       ;
                 End ;

    AVLPtr = ^AVL_Tree_Rec ;

    AVL_Tree_Rec = Record
                     TreeData : AVLDataRec ;
                     Balance  : BalanceSet ;
                     Left  ,
                     Right    : AVLPtr     ;
                   End ;

    TreeRecArray = Array[1..Max_Tree_Nodes] of AVLDataRec ;
{.PA}
    Procedure Insert_AVLTree(Var Root : AVLPtr     ;
                                 X    : AVLDataRec  ) ;

    Function Search_AVLTree(Var Root       : AVLPtr     ;
                                X          : AVLDataRec  ) : Boolean ;

    Function Search(    Root : AVLPtr     ;
                    Var X    : AVLDataRec  ) : Boolean ;

    Procedure AVLSort_To_Array(Var Root  : AVLPtr       ;
                               Var SortX : TreeRecArray ;
                               Var Count : Word          ) ;

    Function Find_AVLNode(Var Root : AVLPtr     ;
                              X    : AVLDataRec  ) : AVLPtr ;

    Procedure Delete_AVLTree(Var Root  : AVLPtr     ;
                                 X     : AVLDataRec ;
                             Var DelOK : Boolean     ) ;

  Implementation
{.PA}
{***********************************************************************
*                                                                      *
*      Rotate_Right                                                    *
*                                                                      *
*      Re-arranges tree nodes by rotating them to the right.           *
*                                                                      *
*      Modifications                                                   *
*      =============                                                   *
*                                                                      *
***********************************************************************}

    Procedure Rotate_Right(Var Root : AVLPtr) ;
      Var
        Ptr2 ,
        Ptr3   : AVLPtr ;

      Begin  { Rotate_Right }
        Ptr2 := Root^.Right ;
        If Ptr2^.Balance = Right_Tilt then
          Begin
            Root^.Right   := Ptr2^.Left ;
            Ptr2^.Left    := Root       ;
            Root^.Balance := Neutral    ;
            Root          := Ptr2       ;
          End
        Else
          Begin
            Ptr3        := Ptr2^.Left  ;
            Ptr2^.Left  := Ptr3^.Right ;
            Ptr3^.Right := Ptr2        ;
            Root^.Right := Ptr3^.Left  ;
            Ptr3^.Left  := Root        ;

            If Ptr3^.Balance = Left_Tilt then
              Ptr2^.Balance := Right_Tilt
            Else
              Ptr2^.Balance := Neutral ;

            If Ptr3^.Balance = Right_Tilt then
              Root^.Balance := Left_Tilt
            Else
              Root^.Balance := Neutral ;

            Root := Ptr3 ;
          End ;

        Root^.Balance := Neutral ;

      End ;  { Rotate_Right }
{.PA}
{***********************************************************************
*                                                                      *
*      Rotate_Left                                                     *
*                                                                      *
*      Re-arranges tree nodes by rotating them to the left.            *
*                                                                      *
*      Modifications                                                   *
*      =============                                                   *
*                                                                      *
***********************************************************************}

    Procedure Rotate_Left(Var Root : AVLPtr) ;
      Var
        Ptr2 ,
        Ptr3   : AVLPtr ;

      Begin  { Rotate_Left }
        Ptr2 := Root^.Left ;
        If Ptr2^.Balance = Left_Tilt then
          Begin
            Root^.Left    := Ptr2^.Right;
            Ptr2^.Right   := Root       ;
            Root^.Balance := Neutral    ;
            Root          := Ptr2       ;
          End
        Else
          Begin
            Ptr3        := Ptr2^.Right ;
            Ptr2^.Right := Ptr3^.Left  ;
            Ptr3^.Left  := Ptr2        ;
            Root^.Left  := Ptr3^.Right ;
            Ptr3^.Right := Root        ;

            If Ptr3^.Balance = Right_Tilt then
              Ptr2^.Balance := Left_Tilt
            Else
              Ptr2^.Balance := Neutral ;

            If Ptr3^.Balance = Left_Tilt then
              Root^.Balance := Right_Tilt
            Else
              Root^.Balance := Neutral ;

            Root := Ptr3 ;
          End ;

        Root^.Balance := Neutral ;

      End ;  { Rotate_Left }
{.PA}
{***********************************************************************
*                                                                      *
*      Insert_AVL                                                      *
*                                                                      *
*      Workhouse routine to perform node insertion in an AVL tree.     *
*                                                                      *
*      Modifications                                                   *
*      =============                                                   *
*                                                                      *
***********************************************************************}

    Procedure Insert_AVL(Var Root       : AVLPtr     ;
                             X          : AVLDataRec ;
                         Var InsertedOK : Boolean     ) ;
      Begin  { Insert_AVL }
        If Root = Nil then
          Begin
            New(Root) ;
            With Root^ do
              Begin
                TreeData := X       ;
                Left     := Nil     ;
                Right    := Nil     ;
                Balance  := Neutral ;
              End ;

            InsertedOK := True ;
          End
        Else
          If X.Key = Root^.TreeData.Key then
            Begin
              InsertedOK := False ;
              Exit ;
            End
          Else
            If X.Key <= Root^.TreeData.Key then
              Begin
                Insert_AVL(Root^.Left , X , InsertedOK) ;
                If InsertedOK then
                  Case Root^.Balance of
                    Left_Tilt  : Begin
                                   Rotate_Left(Root) ;
                                   InsertedOK := False ;
                                 End ;

                    Neutral    : Root^.Balance := Left_Tilt ;

                    Right_Tilt : Begin
                                   Root^.Balance := Neutral ;
                                   InsertedOK    := False   ;
                                 End ;
                  End ; { Case Root^.Balance of }
              End
            Else
              Begin
                Insert_AVL(Root^.Right , X , InsertedOK) ;
                If InsertedOK then
                  Case Root^.Balance of
                    Left_Tilt  : Begin
                                   Root^.Balance := Neutral ;
                                   InsertedOk    := False   ;
                                 End ;

                    Neutral    : Root^.Balance := Right_Tilt ;

                    Right_Tilt : Begin
                                   Rotate_Right(Root) ;
                                   InsertedOK := False ;
                                 End ;
                  End ;  { Case Root^.Balance of }
              End ;

      End ;  { Insert_AVL }
{.PA}
{***********************************************************************
*                                                                      *
*      Insert_AVLTree                                                  *
*                                                                      *
*      Insert a datum into the AVL tree.                               *
*                                                                      *
*      Modifications                                                   *
*      =============                                                   *
*                                                                      *
***********************************************************************}

    Procedure Insert_AVLTree(Var Root : AVLPtr     ;
                                 X    : AVLDataRec  ) ;
      Var
        InsertedOK : Boolean ;

      Begin  { Insert_AVLTree }
        InsertedOK := False ;
        Insert_AVL(Root , X , InsertedOK) ;
      End ;  { Insert_AVLTree }

{***********************************************************************
*                
...

read more »

Re:AVL trees in paskal


On Fri, 15 Jan 1999 05:15:07 -0700, "Bruce Christensen"

Quote
<bru...@oanet.com> wrote:

Many thanks.

Did you do it yourself?

Re:AVL trees in paskal


Can't even remember, but probably.   It is in a first year course
in computing science;

B.C.

Quote
Rn...@yahoo.com wrote in message <36a1e996.5217...@news.netvision.net.il>...
>On Fri, 15 Jan 1999 05:15:07 -0700, "Bruce Christensen"
><bru...@oanet.com> wrote:

>Many thanks.

>Did you do it yourself?

Re:AVL trees in paskal


On Mon, 18 Jan 1999 21:38:47 -0700, "Bruce Christensen"

Quote
<bru...@oanet.com> wrote:

Many thanks anyway, it is a very nice implementation.
Quote
>Can't even remember, but probably.   It is in a first year course
>in computing science;

>B.C.

Other Threads