Witam,
Czy ktoś z forumowiczów orientuje się które z drzew (AVL czy BST) jest szybsze przy wyszukiwaniu danych?
0
0
Oby dwa typy drzew są przesukiwane z tą samą prędkością. Jedyna(aczkolwiek znaczna) różnica pomiędzy BST a AVL jest taka że AVL dba sam o to by ścieżki poszukiwań były jak najkrótsze. Jeżeli więc masz dane rosnące 1..n to dodając je do pustego drzewa BST zawsze element n+1 zostanie dodany z prawej strony elementu n co sprowadza się do listy jednokierunkowej(jej przeszukiwanie jest czasochłonne). Natomiast gdy ten sam ciąg jest dodawany do pustego AVL'a to po dodaniu elementu n dzrzewo jest zruwnowarzone czyli najdłuższa ścierzka jest conjawyżej o jeden dłuższa(założenie do klasycznego AVL'a). Należy pamiętać że niestety takie rónowarzenie jest równierz czasochłonne więc jeżeli dużo dodajesz i usuwasz a mało wyszukujesz to chyba lepsze będzie BST a jak odwrotnie to AVL. Jeżeli dużo dodajesz, usuwasz i wyszukujesz to AVL ale zmodyfikowany np. wagi nie do 2 ale 3..5.