[R.....y]

#programowanie #naukaprogramowania #matematyka

jaki jest sens drzew binarnych które się automatycznie balansują?
Przy klasycznych red-black binary tree, masz prosty algorytm do przeszukania drzewa.
Jak to wyglączy przy drzewach które kierują się narpierw tym żeby gałęzie były podobnej wysokości?
Masz krótkie ścieżki których nie ma jak przeszukiwać, czy może trzymasz zapisane w drugiej strukturze drogi do wybranego elementu?

[93michu93]

@RedveKoronny: no jak masz jakieś avl czy inne jakiekolwiek zbalansowane drzewo to wysokość maksymalna będzie log n, bez balansowania możesz w najgorszym wypadku mieć nawet wysokość n. potem przy szukaniu masz O(log n) do O(n). Studia już dawno kończyłem ale logicznie wydaje się, że przy szukaniu elementu w zbalansowanym będzie dużo szybciej. Insert będzie pewnie wolniejszy bo trzeba balansowac

[R.....y]

@93michu93: rozważmy takie drzewa. Oba drzewa posiadają dokładnie te same elementy.
W drzewie po lewej chcąc znaleść element 1,5 potrzebuję 4 kroków, gdzie w drzewie po lewej tylko 2, więc faktycznie jest szybciej. Problemem jest dowiedzenie się, gdzie powinienem go właściwie szukać.

W drzewie po lewej mam prosty algorytm rekurencyjny, jeśli 1,5 jest większy od wartości elementu w nodzie w którym jestem, szukaj go po prawej, a jak nie to po

[Picasso7]

@RedveKoronny: coś chyba źle zrotowałeś to drzewo, po rotacji nadal powinne zostać zachowane własności, że po lewej mniejsze po prawej większe wartości

[M.....k]

@RedveKoronny: w drzewie AVL jest taka sama logika jak z ułożeniem elementów jak w innych drzewach, a takie drzewo jak z prawej nie mogłoby powstać. Zakładając że wrzuciłbyś do drzewa 3,4,6 każdy kolejny idzie do prawego poddrzewa a po wyważeniu 4 byłaby nowym korzeniem.

[R.....y]

@Picasso7: @MlodyWilk: to widzę że widziałem #!$%@? przykłady zbalansowanych drzew xD Teraz wszystko jasne, dzięki

[M.....k]

@RedveKoronny: https://visualgo.net/en/bst zmień na górze na avl i dodaj jakieś węzły albo stwórz nowe drzewo to zobaczysz jak to działa

[Picasso7]

@RedveKoronny: i oczywiście im więcej wartości tym lepiej to działa, powiedzmy dla 10000 wartości, w jakimś słabym przypadku drzewo może mieć głębokość 1000, w najgorszym 10000, a po zbalansowaniu to około 13-14

[Krolik]

@RedveKoronny: na współczesnych sprzętach drzewa binarne nie mają praktycznie żadnego sensu, podobnie jak listy podwójnie łączone. I nie ma znaczenia czy AVL czy red-black czy jeszcze jakieś inne.

[R.....y]

@Krolik: czemu?

[Krolik]

@RedveKoronny: Bo są nieefektywne - i to zarówno pod względem wydajności wyszukiwania jak i zajętości pamięci.

[R.....y]

@Krolik: to czego zamiast tego sie uzywa?

[Krolik]

@RedveKoronny: B drzewa, B+ drzewa i inne struktury drzewiaste posiadające w jednym bloku N kluczy, gdzie N znacznie większe od 2, zwykle N w okolicach 16 - 128. (wskazówka: B w B-drzewie nie jest od "binary").

[R.....y]

@Krolik: już wiem, próbowałem pomóc trochę znajomemu z B drzewem, i na początku popełniłem ten błąd ( ͡° ͜ʖ ͡°)

[Krolik]

@RedveKoronny: problem z drzewami binarnymi jest taki, że one minimalizują nie to co trzeba - tj. minimalizują liczbę operacji porównania, a porównania są akurat bardzo tanie. Natomiast skok do innego węzła poprzez wskaźnik jest operacją relatywnie bardzo drogą, tzn. w czasie gdy CPU ściągnie nowy węzeł do cache L1 to mógłby zrobić dziesiątki a nawet setki porównań kluczy.

No i kolejna kwestia, że w jednym węźle drzewa binarnego masz jeden klucz

[poprostulogin]

@RedveKoronny: red-black tree są drzewami zbalansowanymi. /shrug. zbalansowane mają dokładnie te same własności co zwykłe drzewa binarne (zachowują porządek), ale dodatkowo mają gwarancje, że operacje słownikowe będą logarytmiczne w każdym przypadku, a nie tylko w optymistycznym.