Definici AVL – stromů zformulovali Adelson – Velskii a Landis. AVL – stromy jsou binární vyhledávací stromy, u kterých se výšky podstromů každého vrcholu liší maximálně o 1. Tvůrci této definice také dokázali, že výška AVL – stromu bude maximálně o 45% větší než výška dokonale vyváženého stromu na stejném počtu vrcholů. Z toho plyne, že operace vyhledání vrcholu s daným klíčem se provede v čase O(log n), kde n je počet vrcholů. Protože je vybalancování stromu jednoduché, je i složitost přidání nebo odebrání vrcholu O(log n).
Dá se vypozorovat, že při poruše vyváženosti stromu po přidání (odebrání) vrcholu mohou nastat pouze čtyři různé případy, které se musí individuálně řešit pomocí čtyř různých rotací (LL, LR, RR, RL). Každá z těchto rotací sníží výšku jednoho podstromu o jedna. Pokud se vyváženost poruší přidáním vrcholu, dojde k jedné rotaci a tím se vyváženost obnoví. Pokud se vyváženost poruší odebráním vrcholu, může dojít k více než jedné rotaci (protože rotace obnoví podmínku vyváženosti pro jeden vrchol, ale sníží nějaký podstrom a to může porušit podmínku vyváženosti pro nějaký vrchol na vyšší úrovni).
Empirické testy ukázali, že pokud je každá z n! permutací n klíčů vyskytne se stejnou pravděpodobností, pak bude očekávaná výška stromu asi log n + 0,25. Zároveň se ukázalo, že je potřeba průměrně jedna rotace na každé dva přidané vrcholy. U odebírání vrcholů je průměrně potřeba jedna rotace na 5 odebraných vrcholů.
AVL – stromy se uplatní hlavně v případech, kdy je počet výběrů informace ze stromu mnohem vyšší než počet přidání vrcholů.

Přidávání vrcholu do stromu :

type PPrvek = ^TPrvek;
     TPrvek = record key : integer;
                     l, r : PPrvek;
                     bal : -1..1;
              end;

procedure Ins(var p : PPrvek; var x : TPrvek; var h : boolean);
var q : PPrvek;
begin
     if p = nil then
     begin
          new(p); p^ := x;
          p^.l := nil; p^.r := nil;
          p^.bal := 0;
          h := true;
     end
     else if x.key < p^.key then
     begin
          Ins(p^.l, x, h);
          if h then
             case p^.bal of
               1 : begin p^.bal := 0; h := false end;
               0 : p^.bal := -1;
               -1 : begin if p^.l^.bal = -1 then
                          begin
                               q := p^.l;
                               p^.bal := 0; q^.bal := 0;
                               p^.l := q^.r;
                               q^.r := p;
                               p := q;
                          end
                          else begin
                               q := p^.l^.r;

                               if q^.bal = -1 then
                               begin
                                    p^.l^.bal := 0; p^.bal := 1
                               end else
                               begin
                                    p^.l^.bal := -1; p^. bal := 0
                               end;
                               q^.bal := 0;

                               p^.l^.r := q^.l;
                               q^.l := p^.l;
                               p^.l := q^.r;
                               q^.r := p;
                               p := q;
                          end;
                          h := false;
                    end;
             end;
     end
     else if x.key > p^.key then
     begin
          Ins(p^.r, x, h);
          if h then
             case p^.bal of
               -1 : begin p^.bal := 0; h := false end;
               0 : p^.bal := 1;
               1 : begin if p^.r^.bal = 1 then
                         begin
                              p^.bal := 0; p^.r^.bal := 0;
                              q := p^.r;
                              p^.r := q^.l;
                              q^.l := p;
                              p := q;
                         end
                         else begin
                              q := p^.r^.l;

                              if q^.bal = -1 then
                              begin p^.r^.bal := 0; p^.bal := 1 end
                              else begin p^.r^.bal := -1; p^.bal := 0 end;
                              q^.bal := 0;

                              p^.r^.l := q^.r;
                              q^.r := p^.r;
                              p^.r := q^.l;
                              q^.l := p;
                              p := q;
                         end;
                         h := false;
                   end;
             end;
     end;
end;
 

Literatura : Niklaus Wirth - Algoritmy a štruktúry údajov