AVL-drevo

Primer neurejenega AVL-drevesa

Primer urejenega AVL-drevesa

AVL-drevo je urejeno dvojiško drevo, ki ima globinsko neuravnoteženost ≤ 1. AVL-drevo se imenuje po ruskih matematikih Georgiju Maksimoviču Adelson-Velskem in Jevgeniju Mihajloviču Landisu, ki sta ga objavila leta 1962.

Operacije

Vstavljanje

Zaporedno vstavljanje elementov 7 3 2 4 1 5 8 9 6

za koren vzamemo prvo število, nato pa po vrsti dodajamo ostala števila na levo(manjša števila od korena) in desno(večja števila od korena) stran:

    7                              3                               3                              3                          3
   /   LevoLeva rotacija          / \   LevoDesna rotacija        / \    DesnoDesna rotacija     / \    DesnoLeva rot.      / \
  3    ---------------->         2   7  ----------------->       2   5   ------------------>    2   5   -------------->    2   7
 /    dodajanja števila 4,1,5   /   /   dodajanje števila 8,9   /   / \                        /   / \                    /   / \
2                              1   4                           1   4   7                      1   4   8                  1   5   8
                                    \                                   \                            / \                    / \   \
                                     5                                   8                          7   9                  4   6   9
                                                                          \                        /
                                                                           9                      6

Uravnovešanje

Enojni zasuk

Enojni levi zasuk

Dvojni zasuk

Dvojni zasuk