Jakie są zastosowania drzew binarnych?
Odpowiedzi:
Spieranie się o wydajność drzew binarnych jest bez znaczenia - nie są one strukturą danych, ale rodziną struktur danych, wszystkie o różnych charakterystykach wydajności. Chociaż prawdą jest, że niezrównoważone drzewa binarne wykonują wyszukiwanie znacznie gorzej niż drzewa binarne samowyważące, istnieje wiele drzew binarnych (takich jak próby binarne), dla których „równoważenie” nie ma znaczenia.
Zastosowania drzew binarnych
- Drzewo wyszukiwania binarnego - Używany w wielu aplikacjach wyszukiwania, w których dane ciągle wchodzą / wychodzą, takich jak obiekty
mapisetw bibliotekach wielu języków. - Partycja przestrzeni binarnej - używana w prawie każdej grze wideo 3D w celu określenia, które obiekty należy renderować.
- Binary Tries - Używany w prawie każdym routerze o dużej przepustowości do przechowywania tabel routerów.
- Hash Trees - używany w programach p2p i specjalistycznych podpisach obrazów, w których hash musi zostać zweryfikowany, ale cały plik nie jest dostępny.
- Sterty - Stosowane przy wdrażaniu wydajnych kolejek priorytetowych, które z kolei są wykorzystywane do planowania procesów w wielu systemach operacyjnych, jakości usług w routerach i A * (algorytm ustalania ścieżki wykorzystywany w aplikacjach AI, w tym w robotyce i grach wideo) . Używany również w sortowaniu stosów.
- Drzewo kodowania Huffmana ( Chip Uni ) - stosowane w algorytmach kompresji, takich jak te stosowane w formatach plików .jpeg i .mp3.
- Drzewa GGM - używane w aplikacjach kryptograficznych do generowania drzewa liczb pseudolosowych.
- Drzewo składniowe - zbudowane przez kompilatory i (domyślnie) kalkulatory do analizowania wyrażeń.
- Treap - Randomizowana struktura danych wykorzystywana w sieciach bezprzewodowych i przydziale pamięci.
- T-drzewo - chociaż większość baz danych używa jakiejś formy B-drzewa do przechowywania danych na dysku, bazy danych, które przechowują wszystkie (większość) swoich danych w pamięci, często używają do tego T-drzew.
Powodem, dla którego drzewa binarne są używane częściej niż drzewa n-ary, jest to, że drzewa n-ary są bardziej złożone, ale zwykle nie zapewniają żadnej rzeczywistej przewagi prędkości.
W (zrównoważonym) drzewie binarnym z mwęzłami przejście z jednego poziomu na następny wymaga jednego porównania, a istnieją log_2(m)poziomy, w sumie log_2(m)porównań.
Natomiast drzewo n-ary będzie wymagało log_2(n)porównań (za pomocą wyszukiwania binarnego), aby przejść do następnego poziomu. Ponieważ istnieją log_n(m)poziomy całkowite, wyszukiwanie będzie wymagało log_2(n)*log_n(m)= log_2(m)sumarycznych porównań. Tak więc, chociaż drzewa n-ary są bardziej złożone, nie zapewniają żadnej przewagi pod względem koniecznych całkowitych porównań.
(Jednak drzewa n-ary są nadal przydatne w niszowych sytuacjach. Przykładami, które przychodzą mi na myśl, są drzewa czworokątne i inne drzewa dzielące przestrzeń, w których dzielenie przestrzeni za pomocą tylko dwóch węzłów na poziom uczyniłoby logikę niepotrzebnie złożoną; oraz B-drzewa używane w wielu bazach danych, gdzie czynnikiem ograniczającym nie jest to, ile porównań wykonuje się na każdym poziomie, ale ile węzłów można załadować jednocześnie z dysku twardego)
Kiedy większość ludzi mówi o drzewach binarnych, częściej nie myśli o drzewach wyszukiwania binarnego , więc omówię to najpierw.
Niezrównoważone drzewo wyszukiwania binarnego jest w rzeczywistości przydatne niewiele więcej niż edukowanie studentów na temat struktur danych. Wynika to z faktu, że jeśli dane nie są przesyłane w stosunkowo losowej kolejności, drzewo może łatwo przerodzić się w najgorszy przypadek, jakim jest lista połączona, ponieważ proste drzewa binarne nie są zrównoważone.
Dobry przykład: kiedyś musiałem naprawić oprogramowanie, które ładowało swoje dane do drzewa binarnego w celu manipulacji i wyszukiwania. Zapisał dane w posortowanej formie:
Alice
Bob
Chloe
David
Edwina
Frank
tak, że po ponownym przeczytaniu skończyło się na następującym drzewie:
Alice
/ \
= Bob
/ \
= Chloe
/ \
= David
/ \
= Edwina
/ \
= Frank
/ \
= =
która jest zdegenerowaną formą. Jeśli zaczniesz szukać Franka w tym drzewie, będziesz musiał przeszukać wszystkie sześć węzłów, zanim go znajdziesz.
Drzewa binarne stają się naprawdę przydatne do wyszukiwania, gdy się je równoważy. Obejmuje to obracanie podgrzewa przez ich węzeł główny, tak aby różnica wysokości między dowolnymi dwoma podgrzewa była mniejsza lub równa 1. Dodanie tych nazw powyżej jednego do zrównoważonego drzewa dałoby następującą sekwencję:
1. Alice
/ \
= =
2. Alice
/ \
= Bob
/ \
= =
3. Bob
_/ \_
Alice Chloe
/ \ / \
= = = =
4. Bob
_/ \_
Alice Chloe
/ \ / \
= = = David
/ \
= =
5. Bob
____/ \____
Alice David
/ \ / \
= = Chloe Edwina
/ \ / \
= = = =
6. Chloe
___/ \___
Bob Edwina
/ \ / \
Alice = David Frank
/ \ / \ / \
= = = = = =
Możesz zobaczyć całe pod-drzewa obracające się w lewo (w krokach 3 i 6) podczas dodawania wpisów, co daje zrównoważone drzewo binarne, w którym wyszukiwanie w najgorszym przypadku jest O(log N)raczej niż O(N), które daje zwyrodniała postać. W żadnym momencie najwyższa wartość NULL ( =) nie różni się od najniższej o więcej niż jeden poziom. I, w ostatecznym drzewa powyżej, można znaleźć tylko przez Franka patrząc na trzech węzłów ( Chloe, Edwinai wreszcie Frank).
Oczywiście mogą stać się jeszcze bardziej przydatne, gdy uczynisz je zrównoważonymi drzewami wielokierunkowymi zamiast podwójnego warkocza. Oznacza to, że każdy węzeł zawiera więcej niż jeden element (technicznie, zawiera N elementów i N + 1 wskaźników, przy czym drzewo binarne jest specjalnym przypadkiem drzewa jednokierunkowego z 1 pozycją i 2 wskaźnikami).
Z trójstronnym drzewem otrzymujesz:
Alice Bob Chloe
/ | | \
= = = David Edwina Frank
/ | | \
= = = =
Jest to zwykle używane do utrzymywania kluczy do indeksu przedmiotów. Napisałem oprogramowanie bazy danych zoptymalizowane dla sprzętu, w którym węzeł ma dokładnie rozmiar bloku dysku (powiedzmy 512 bajtów), a ty umieścisz tyle kluczy, ile możesz w jednym węźle. Te wskaźniki w tym przypadku rzeczywiście były rekordowe liczby w pliku bezpośredniego dostępu stałej długości rekord z osobnym pliku indeksu (liczba więc zapis Xmożna znaleźć po prostu stara się X * record_length).
Na przykład, jeśli wskaźniki mają 4 bajty, a rozmiar klucza to 10, liczba kluczy w węźle 512-bajtowym wynosi 36. To 36 kluczy (360 bajtów) i 37 wskaźników (148 bajtów), co daje łącznie 508 bajtów z 4 bajty zmarnowane na węzeł.
Zastosowanie kluczy wielodrożnych wprowadza złożoność wyszukiwania dwufazowego (wyszukiwanie wielostronne w celu znalezienia właściwego węzła w połączeniu z małym wyszukiwaniem sekwencyjnym (lub liniowym binarnym) w celu znalezienia właściwego klucza w węźle), ale zaletą robienie mniej dyskowych operacji we / wy niż to nadrabia.
Nie widzę powodu, aby robić to ze względu na strukturę w pamięci, lepiej byłoby trzymać się zrównoważonego drzewa binarnego i uprościć kod.
Należy również pamiętać, że zalety O(log N)over O(N)nie pojawiają się, gdy zestawy danych są małe. Jeśli używasz drzewa wielokierunkowego do przechowywania piętnastu osób w książce adresowej, prawdopodobnie jest to przesada. Korzyści pojawiają się, gdy przechowujesz coś takiego jak każde zamówienie od stu tysięcy klientów w ciągu ostatnich dziesięciu lat.
Istotą notacji big-O jest wskazanie, co się dzieje, gdy Nzbliża się nieskończoność. Niektóre osoby mogą się nie zgadzać, ale nawet w porządku jest stosowanie sortowania bąbelkowego, jeśli masz pewność, że zestawy danych pozostaną poniżej określonego rozmiaru, o ile nic innego nie będzie łatwo dostępne :-)
Jeśli chodzi o inne zastosowania drzew binarnych, istnieje wiele takich, jak:
- Sterty binarne, w których wyższe klucze są wyższe lub równe niższym niż na lewo od (lub poniżej lub równe i prawe);
- Drzewa haszyszowe, podobne do tabel skrótów;
- Abstrakcyjne drzewa składniowe do kompilacji języków komputerowych;
- Drzewa Huffmana do kompresji danych;
- Drzewa routingu dla ruchu sieciowego.
Biorąc pod uwagę, ile wyjaśnień wygenerowałem dla drzew wyszukiwania, nie chcę wchodzić w wiele szczegółów na temat innych, ale powinno to wystarczyć do ich zbadania, jeśli chcesz.
Drzewo binarne to struktura danych drzewa, w której każdy węzeł ma co najwyżej dwa węzły potomne, zwykle rozróżniane jako „lewe” i „prawe”. Węzły z dziećmi są węzłami nadrzędnymi, a węzły podrzędne mogą zawierać odniesienia do swoich rodziców. Poza drzewem często znajduje się odniesienie do węzła „root” (przodka wszystkich węzłów), jeśli istnieje. Do dowolnego węzła w strukturze danych można dotrzeć, zaczynając od węzła głównego i powtarzając wielokrotnie odwołania do lewego lub prawego dziecka. W drzewie binarnym stopień każdego węzła wynosi maksymalnie dwa.
Drzewa binarne są przydatne, ponieważ jak widać na zdjęciu, jeśli chcesz znaleźć dowolny węzeł w drzewie, wystarczy spojrzeć maksymalnie 6 razy. Na przykład, jeśli chcesz wyszukać węzeł 24, zacznij od katalogu głównego.
- Katalog główny ma wartość 31, która jest większa niż 24, więc idziesz do lewego węzła.
- Lewy węzeł ma wartość 15, która jest mniejsza niż 24, więc idziesz do prawego węzła.
- Prawy węzeł ma wartość 23, czyli mniej niż 24, więc idziesz do prawego węzła.
- Prawy węzeł ma wartość 27, która jest większa niż 24, więc idziesz do lewego węzła.
- Lewy węzeł ma wartość 25, która jest większa niż 24, więc idziesz do lewego węzła.
- Węzeł ma wartość 24, która jest kluczem, którego szukamy.
To wyszukiwanie jest zilustrowane poniżej:
Możesz zobaczyć, że możesz wykluczyć połowę węzłów całego drzewa przy pierwszym przejściu. i połowa lewego poddrzewa na drugim. To sprawia, że wyszukiwanie jest bardzo skuteczne. Gdyby to zrobiono na 4 miliardach elementów, trzeba by przeszukać maksymalnie 32 razy. Dlatego im więcej elementów jest zawartych w drzewie, tym bardziej wydajne może być wyszukiwanie.
Usunięcia mogą stać się złożone. Jeśli węzeł ma 0 lub 1 element potomny, wystarczy przesunąć niektóre wskaźniki, aby wykluczyć ten, który ma zostać usunięty. Nie można jednak łatwo usunąć węzła z 2 dziećmi. Więc skracamy. Powiedzmy, że chcieliśmy usunąć węzeł 19.
Ponieważ próba ustalenia, gdzie należy przesunąć lewy i prawy wskaźnik, nie jest łatwa, znajdujemy taki, który może go zastąpić. Idziemy do lewego sub-drzewa i idziemy tak daleko, jak to możliwe. To daje nam następną największą wartość węzła, który chcemy usunąć.
Teraz kopiujemy całą zawartość 18, z wyjątkiem lewego i prawego wskaźnika i usuwamy oryginalny 18 węzeł.
Aby utworzyć te obrazy, zaimplementowałem drzewo AVL, drzewo samobalansujące, aby w dowolnym momencie drzewo miało co najwyżej jeden poziom różnicy między węzłami liści (węzłami bez dzieci). Zapobiega to przekrzywianiu drzewa i zachowuje maksymalny O(log n)czas wyszukiwania, a koszty wstawiania i usuwania wymagają nieco więcej czasu.
Oto przykład pokazujący, w jaki sposób moje drzewo AVL zachowało się tak kompaktowe i zrównoważone, jak to możliwe.
W posortowanej tablicy wyszukiwania nadal trwałyby O(log(n)), podobnie jak drzewo, ale losowe wstawianie i usuwanie wymagałoby O (n) zamiast drzewa O(log(n)). Niektóre pojemniki STL wykorzystują te cechy wydajności na swoją korzyść, więc czasy wkładania i wyjmowania trwają maksymalnie O(log n), co jest bardzo szybkie. Niektóre z tych pojemników są map, multimap, set, i multiset.
Przykładowy kod drzewa AVL można znaleźć na stronie http://ideone.com/MheW8
Główną aplikacją są drzewa wyszukiwania binarnego . Są to struktury danych, w których wyszukiwanie, wstawianie i usuwanie są bardzo szybkie (o log(n)operacjach)
- Drzewa binarne są używane w kodowaniu Huffmana , które są używane jako kod kompresji.
- Drzewa binarne są używane w drzewach wyszukiwania binarnego , które są przydatne do przechowywania danych bez większej ilości miejsca.
Jednym ciekawym przykładem drzewa binarnego, o którym nie wspomniano, jest rekurencyjnie ocenione wyrażenie matematyczne. Jest to praktycznie bezużyteczne z praktycznego punktu widzenia, ale jest to ciekawy sposób na myślenie o takich wyrażeniach.
Zasadniczo każdy węzeł drzewa ma wartość, która jest sama w sobie lub jest oceniana rekurencyjnie przez działanie na wartościach jego potomków.
Na przykład wyrażenie (1+3)*2może być wyrażone jako:
*
/ \
+ 2
/ \
1 3
Aby ocenić wyrażenie, pytamy o wartość rodzica. Ten węzeł z kolei otrzymuje swoje wartości od swoich potomków, operatora plus i węzła, który po prostu zawiera „2”. Z kolei operator plus pobiera swoje wartości od dzieci o wartościach „1” i „3” i dodaje je, zwracając 4 do węzła mnożenia, który zwraca 8.
To użycie drzewa binarnego przypomina w pewnym sensie odwrotną notację polską, ponieważ kolejność wykonywania operacji jest identyczna. Należy również zauważyć, że niekoniecznie musi to być drzewo binarne, po prostu najczęściej używane operatory są binarne. Na najbardziej podstawowym poziomie drzewo binarne jest w rzeczywistości bardzo prostym, czysto funkcjonalnym językiem programowania.
Nie sądzę, aby można było użyć „czystych” drzew binarnych. (z wyjątkiem celów edukacyjnych) Zrównoważone drzewa binarne, takie jak drzewa czerwono-czarne lub drzewa AVL są znacznie bardziej przydatne, ponieważ gwarantują operacje O (logn). Normalne drzewa binarne mogą być listą (lub prawie listą) i nie są tak naprawdę przydatne w aplikacjach wykorzystujących dużo danych.
Zrównoważone drzewa są często używane do wdrażania map lub zestawów. Mogą być również używane do sortowania w O (nlogn), nawet jeśli istnieją lepsze sposoby na to.
Można także wyszukiwać / wstawiać / usuwać tabele skrótów , które zwykle mają lepszą wydajność niż binarne drzewa wyszukiwania (zrównoważone lub nie).
Aplikacja, w której przydatne byłyby (zrównoważone) drzewa wyszukiwania binarnego, byłaby potrzebna do wyszukiwania / wstawiania / usuwania i sortowania. Sortowanie może być na miejscu (prawie ignorując przestrzeń stosu potrzebną do rekurencji), biorąc pod uwagę gotowe drzewo zbalansowane. Nadal byłby to O (nlogn), ale z mniejszym stałym współczynnikiem i niepotrzebnej dodatkowej przestrzeni (z wyjątkiem nowej tablicy, zakładając, że dane muszą być umieszczone w tablicy). Z drugiej strony nie można sortować tabel mieszania (przynajmniej nie bezpośrednio).
Może są również przydatne w niektórych wyrafinowanych algorytmach do robienia czegoś, ale nic mi nie przychodzi do głowy. Jeśli znajdę więcej, zmodyfikuję swój post.
Inne drzewa, takie jak fe B +, są szeroko stosowane w bazach danych
Jedną z najczęstszych aplikacji jest wydajne przechowywanie danych w posortowanej formie w celu szybkiego dostępu i wyszukiwania przechowywanych elementów. Na przykład std::maplubstd::set w standardowej bibliotece C ++.
Drzewo binarne jako struktura danych jest przydatne w różnych implementacjach parserów wyrażeń i solverach wyrażeń.
Może być również wykorzystywany do rozwiązywania niektórych problemów z bazą danych, na przykład indeksowania.
Zasadniczo drzewo binarne jest ogólną koncepcją konkretnej struktury danych opartej na drzewie, a różne konkretne typy drzew binarnych można konstruować z różnymi właściwościami.
W C ++ STL i wielu innych standardowych bibliotekach w innych językach, takich jak Java i C #. Drzewa wyszukiwania binarnego służą do implementacji zestawu i mapy.
Jedną z najważniejszych aplikacji drzew binarnych są zrównoważone drzewa wyszukiwania binarnego, takie jak:
Te typy drzew mają właściwość polegającą na tym, że różnica wysokości lewego poddrzewa i prawego poddrzewa jest niewielka, wykonując operacje takie jak obracanie za każdym razem, gdy węzeł jest wstawiany lub usuwany.
Z tego powodu całkowita wysokość drzewa pozostaje w kolejności log n, a operacje takie jak wyszukiwanie, wstawianie i usuwanie węzłów są wykonywane w czasie O (log n). STL C ++ implementuje również te drzewa w postaci zestawów i map.
Na współczesnym sprzęcie drzewo binarne jest prawie zawsze nieoptymalne ze względu na złe zachowanie pamięci podręcznej i miejsca. Dotyczy to także (pół) zrównoważonych wariantów. Jeśli je znajdziesz, to tam, gdzie wydajność się nie liczy (lub jest zdominowana przez funkcję porównywania), lub bardziej prawdopodobne z przyczyn historycznych lub ignorancji.
Kompilator, który używa drzewa binarnego do reprezentacji AST, może używać znanych algorytmów do parsowania drzewa, takich jak postorder, inorder. Programista nie musi wymyślać własnego algorytmu. Ponieważ drzewo binarne dla pliku źródłowego jest wyższe niż drzewo n-ary, jego budowa zajmuje więcej czasu. Weźmy tę produkcję: selstmnt: = "if" "(" expr ")" stmnt "ELSE" stmnt W drzewie binarnym będzie miało 3 poziomy węzłów, ale drzewo n-ary będzie miało 1 poziom (chids)
Właśnie dlatego systemy operacyjne oparte na Uniksie są wolne.