Różnica między drzewami AVL i drzewami splay

Zarówno drzewa splay, jak i Drzewa AVL są drzewami wyszukiwania binarnego z doskonałymi gwarancjami wydajności, ale różnią się one sposobem osiągnięcia tych gwarancji wydajności. W przypadku drzewa AVL kształt drzewa jest zawsze ograniczony tak, że kształt drzewa jest zrównoważony, co oznacza, że wysokość drzewa nigdy nie przekracza O (log n). Ten kształt jest utrzymywany podczas wstawiania i usuwania i nie zmienia się podczas wyszukiwania. Drzewa Splay, z drugiej strony, utrzymanie wydajne przez zmiana kształtu drzewa w odpowiedzi na poszukiwania na nim. W ten sposób często dostępne elementy przesuwają się w górę w kierunku wierzchołka drzewa i mają lepsze czasy wyszukiwania. Kształt drzew splay nie jest ograniczony i różni się w zależności od tego, jakie są wykonywane poszukiwania.

Nie ma w tym żadnej twardej i szybkiej Zasady. Jednak kluczową różnicą między strukturami jest to, że drzewa AVL gwarantują szybkie wyszukiwanie (o (log n)) przy każdej operacji, podczas gdy drzewa splay mogą zagwarantować tylko, że dowolna Sekwencja n operacje trwają co najwyżej O (n log N) czas. Oznacza to, że jeśli potrzebujesz wyszukiwania w czasie rzeczywistym, drzewo AVL prawdopodobnie będzie lepsze. Jednak drzewa splay wydają się być znacznie szybsze średnio, więc jeśli chcesz zminimalizować całkowity czas trwania wyszukiwania drzew, drzewo splay prawdopodobnie będzie lepsze. Dodatkowo drzewa splay bardzo efektywnie wspierają niektóre operacje, takie jak dzielenie i scalanie, podczas gdy odpowiednie operacje drzewa AVL są bardziej zaangażowane i mniej wydajne. Drzewa Splay są bardziej pamięć wydajna niż drzewa AVL, ponieważ nie muszą przechowywać informacji o balansie w węzłach. Jednak drzewa AVL są bardziej przydatne w środowiskach wielowątkowych z dużą ilością wyszukiwań, ponieważ wyszukiwania w drzewie AVL mogą być wykonywane równolegle, podczas gdy nie mogą być wykonywane w drzewach splay. Ponieważ drzewa splay przekształcają się w oparciu o Wyszukiwanie, jeśli potrzebujesz tylko dostępu do małego podzbioru elementów drzewa lub jeśli uzyskasz dostęp do niektórych elementów znacznie więcej niż inne, drzewo splay przewyższy AVL drzewo. Wreszcie, drzewa splay wydają się być łatwiejsze do wdrożenia niż drzewa AVL, ponieważ logika rotacji jest znacznie łatwiejsza.

Zobacz też (2)

Wstawianie, usuwanie i wyszukiwanie drzewa AVL zajmuje O(log n) czas. Drzewa Splay mają te same gwarancje, ale gwarancja jest tylko w sensie amortyzowanym. Każda długa sekwencja operacji zajmie co najwyżej O(n log n) czas, ale poszczególne operacje mogą zająć tyle samo co O (n) czas.