SEPARATE (AVL_Trees_Generic)
PROCEDURE Insert (T : IN OUT Tree; E : ElementType) IS
------------------------------------------------------------------------
--| Insertion in an AVL Tree
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: January 1996                                     
------------------------------------------------------------------------
BEGIN -- Insert

  IF T = NULL THEN
    T := MakeNode (E);

  ELSIF E < T.Info THEN
    IF T.Left = NULL THEN 
      ConnectLeft(T,E);
    ELSE
      Insert (T.Left, E);
    END IF;

    -- now rotate from this level, if necessary
    IF Height(T.Left) - Height(T.Right) = 2 THEN
      IF E < T.Left.Info THEN
        Rotate_L(T);
      ELSE
        Rotate_RL(T);
      END IF;
    ELSE
      T.Height := Max(Height(T.Left), Height(T.Right)) + 1;
    END IF;

  ELSIF T.Info < E THEN
    IF T.Right = NULL THEN 
      ConnectRight(T,E);
    ELSE
      Insert (T.Right, E);
    END IF;
    
    -- now rotate from this level, if necessary
    IF Height(T.Right) - Height(T.Left) = 2 THEN
      IF T.Right.Info < E THEN
        Rotate_R(T);
      ELSE
        Rotate_LR(T);
      END IF;
    ELSE
      T.Height := Max(Height(T.Left), Height(T.Right)) + 1;
    END IF;

  END IF;

END Insert;