Różnica między drzewami AVL i drzewami gryzowatości

Question

Uczę się o różnych drzewach, natknąłem się na drzewa AVL i drzewa gry. Chcę wiedzieć,

1. Jaka jest różnica między drzewami AVL a drzewami do rzutów?
2. Na jakiej podstawie wybieramy te warkocze?
3. Co to są pozytywne i negatywne z tych drzew?
4. Jakie są wykonania tych drzew pod względem wielkiej notacji O?

Answer 1

1. Oba drzewa splay i AVL drzewa są binarne drzewo poszukiwań z doskonałymi gwarancji dobrego wykonania, ale różnią się, w jaki sposób osiągnąć te gwarantują, że wydajność. W drzewie AVL kształt drzewa jest cały czas 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 zachowywany przy wstawianiu i usuwaniu i nie zmienia się podczas wyszukiwania. Z drugiej strony, drzewa z drzewkami drzewiastymi zachowują swoją efektywność poprzez przekształcenie drzewa w odpowiedzi na odnośniki.W ten sposób często odwiedzane elementy przesuwają się w górę drzewa i mają lepsze czasy wyszukiwania. Kształt drzewek rozrzutu nie jest ograniczony i zmienia się w zależności od tego, jakie wyszukiwania są wykonywane.

2. Nie ma twardy i szybki przepis na ten temat. Jednak jedną kluczową różnicą między strukturami jest to, że drzewa AVL gwarantują szybkie wyszukiwanie (O (log n)) w każdej operacji, podczas gdy drzewa rozrzutu gwarantują jedynie, że jakakolwiek sekwencja n operacji zajmuje 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 do rzutów są zwykle znacznie szybsze, więc jeśli chcesz zminimalizować całkowity czas wykonywania wyszukiwań drzewa, drzewo odtwarzania może być lepsze. Dodatkowo, drzewa zagajania obsługują niektóre operacje, takie jak dzielenie i scalanie bardzo wydajnie, podczas gdy odpowiednie operacje drzewa AVL są bardziej zaangażowane i mniej wydajne. Drzewa wyników są bardziej wydajne pod względem pamięci niż drzewa AVL, ponieważ nie muszą przechowywać informacji o saldzie w węzłach. Jednak drzewa AVL są bardziej przydatne w środowiskach wielowątkowych z dużą ilością odnośników, ponieważ wyszukiwania w drzewie AVL można wykonywać równolegle, podczas gdy nie mogą one być w drzewach splay. Ponieważ drzewa odtwarzania zmieniają się w oparciu o odnośniki, jeśli potrzebujesz tylko dostępu do niewielkiego podzbioru elementów drzewa, lub gdy uzyskujesz dostęp do niektórych elementów o wiele bardziej niż inne, drzewo wyników będzie przewyższać drzewo AVL. Wreszcie, drzewa do gry są łatwiejsze do wdrożenia niż drzewa AVL, ponieważ logika rotacji jest znacznie łatwiejsza.

3. Patrz (2)

4. Drzewo AVL insercji, delecji i wyszukiwań się O (log n) każda. Drzewa iglaste mają te same gwarancje, ale gwarancja jest tylko w zamortyzowanym sensie. Każda długa sekwencja operacji zajmie co najwyżej czas O (n log n), ale poszczególne operacje mogą zająć tyle czasu, co O (n).

Mam nadzieję, że to pomoże!

Answer 2

1) Jaka jest różnica między drzewami AVL i drzewami gry?

Są one podobne pod względem struktury i operacji, które na nich wywołujemy. Różnica polega na tym, że w drzewach do gry, po każdej operacji, staramy się utrzymać drzewo niemal idealnie wyważone, aby przyszłe operacje wymagały mniej czasu.

2) Na jakiej podstawie wybieramy te warkocze?

Drzewa z odgałęzieniem są zawsze lepsze niż drzewa wyszukiwania binarnego, gdy aplikacja obsługuje wiele danych w drzewie, ale będzie potrzebować dostępu do podzbioru danych bardzo często niż inne. W takim przypadku dane, do których często wchodzisz, będą zbliżać się do korzenia w wyniku rozrzutu. Ponadto dostęp do dowolnego węzła można uzyskać za mniej czasu niż wcześniej.

Jako ogólną zasadę przy wybieraniu tych drzew, jeśli potrzebujesz "Średniego" czasu (n) w okresie operacji drzewa, użyj drzewa splay. Drzewo binarne nie może tego zagwarantować.

3) Jakie są pozytywne i negatywne z tych drzew?

Pozytywne dla obu jest to, że omijasz log (n) w obu tych strukturach danych teoretycznie.

Jak wspomniano, drzewa splay mają średnią log (n) w odniesieniu do wielu operacji. Oznacza to, że być może masz złożoność czasu na operację conajmniej raz w tym zestawie. Ale zostanie to zrekompensowane przy dostępie do częstych przedmiotów.

Ujemną stroną drzewa wyszukiwania binarnego jest to, że musisz mieć zawsze szczęście, aby log (n) był zawsze. Jeśli klucze nie są losowe, drzewo zmniejszy się do listy takiej jak forma z tylko jedną stroną.

4) Jakie są wyniki tych drzew pod względem wielkiej notacji O?

Drzewo rozrzutu Log (n) na Średnia dla grupy operacji drzewa. Drzewo binarne Log (n) tylko wtedy, gdy klucze są losowe.

Wyniki w środowisku wykonawczym są tutaj oczywiste. splay tree runtime profiling Różnicę czasu wykonywania można zobaczyć przy wyszukiwaniu bez rozrzucania i bez niego.