• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Drzewo trie

    Przeczytaj także...
    Drzewo – w informatyce to struktura danych reprezentująca drzewo matematyczne. W naturalny sposób reprezentuje hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.) jest więc stosowane głównie do tego celu. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych.Drzewo AVL, nazywane również drzewem dopuszczalnym – zrównoważone binarne drzewo poszukiwań (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Nazwa AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskiego oraz Landisa (właściwie: Gieorgij Adelson-Wielskij i Jewgienij Łandis), którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962.
    Wieloznacznik, symbol maski, znak globalny, metaznak, symbol wieloznaczny – nazwa symbolu stosowanego w informatyce w procedurach wyszukiwania ciągów znaków w dokumentach tekstowych i w zbiorach informacji o charakterze tekstowym. Wieloznaczniki używane są do konstruowania wzorców wyszukania (tzw. masek), w których symbol wieloznaczny zastępuje jeden lub więcej znaków pisarskich (tj. nie tylko litery i cyfry, ale także inne znaki występujące w tekstach – interpunkcyjne, matematyczne itp.).
    Drzewo typu trie dla kluczy: „A”, „to”, „tea”, „ted”, „ten”, „i”, „in” oraz „inn”.

    Drzewo trie (wym. tri od ang. retrieval – odczyt; lub traj by odróżnić od tree) – drzewo poszukiwań przechowujące w węzłach fragmenty kluczy („zwykłe” drzewa poszukiwań – np. BST, AVL – przechowują w węzłach całe klucze). To pozwala przyspieszyć wyszukiwanie, gdy koszt porównania całego klucza jest duży.

    Binarne drzewo poszukiwań (ang. Binary Search Tree (BST)) – dynamiczna struktura danych będąca drzewem binarnym, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach nie większych niż klucz węzła a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła. Węzły, oprócz klucza, przechowują wskaźniki na swojego lewego i prawego syna oraz na swojego ojca. Dla pełnego drzewa BST o n węzłach pesymistyczny koszt każdej z podstawowych operacji wynosi O(log n). Złożoność obliczeniowa jest tak niska, ponieważ operacje wykonywane są wzdłuż drzewa. Z tego samego powodu w skrajnym przypadku, gdy drzewo składa się z jednej gałęzi koszt ten wzrasta do O(n). W literaturze często też podaje się koszt wykonania operacji w uzależnieniu od wysokości drzewa h - wynosi on O(h). Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości posortowanych niemalejąco.TeX (wymowa IPA: /tɛx/ jak gr.) – komputerowy system profesjonalnego składu drukarskiego, obejmujący zarówno specjalny język, jak i kompilator przygotowujący pliki w formatach wymaganych przez urządzenia graficzne (drukarki, naświetlarki).

    Przechowując fragmenty kluczy, drzewa trie są najlepiej przystosowane do kluczy reprezentowanych jako ciąg elementów skończonego alfabetu. Przez to są stosowane do sprawdzania poprawności pisowni i dzielenia wyrazów.

    Działania jakie można zrealizować za pomocą drzew trie:

  • sprawdzenie, czy słowo jest w drzewie (w czasie gdzie długość słowa);
  • znalezienie najdłuższego prefiksu słowa występującego w drzewie (w czasie gdzie długość prefiksu);
  • wyszukanie wszystkich słów o podanym prefiksie.
  • W słowach mogą występować również lokalne znaki wieloznaczne, co nie komplikuje znacząco wyszukiwania.

    RAM (ang. Random Access Memory – pamięć o dostępie swobodnym) – podstawowy rodzaj pamięci cyfrowej. Choć nazwa sugeruje, że oznacza to każdą pamięć o bezpośrednim dostępie do dowolnej komórki pamięci (w przeciwieństwie do pamięci o dostępie sekwencyjnym, np. rejestrów przesuwnych), ze względów historycznych określa ona tylko te rodzaje pamięci o bezpośrednim dostępie, w których możliwy jest wielokrotny i łatwy zapis, a wyklucza pamięci ROM (tylko do odczytu) i EEPROM których zapis trwa znacznie dłużej niż odczyt, pomimo iż w ich przypadku również występuje swobodny dostęp do zawartości.Liść – węzeł (element) drzewa, który nie posiada potomków. Często liśćmi są węzły najbardziej oddalone od korzenia. Rozpatrując drzewiastą strukturę danych jako graf drzewiasty można powiedzieć, że liście to wierzchołki o stopniu 1, które nie są korzeniem (wyjątkiem jest tu drzewo złożone tylko z korzenia, wówczas jest on także liściem). Węzeł niebędący liściem nazywany jest węzłem wewnętrznym.

    Do reprezentacji drzew trie w pamięci RAM stosuje się drzewa łączone, gdzie każdy węzeł zawiera znak klucza, a liść zawiera odnośnik do danych, drzewa indeksowane, gdzie każda gałąź to tablica zawierająca cały alfabet z odnośnikami do danych i następnych gałęzi. W programie TeX82 użyto spakowane drzewa trie, które łączyły czas wyszukiwania drzew indeksowanych z małym zużyciem pamięci drzew łączonych. Ze względu na trudność dodawania elementów do tej reprezentacji, do ich tworzenia zastosowano drzewa łączone.

    Skompresowane drzewo trie (również: drzewo Patricia, drzewo pozycyjne) – w informatyce struktura danych przechowująca zbiór ciągów.

    Modyfikacją drzew trie są drzewa Patricia, w których węzły mające tylko jednego syna są usuwane, a drzewo odpowiednio modyfikowane. Dzięki temu skracane są ścieżki w drzewie, co przekłada się na mniejszą liczbę koniecznych porównań.

    Bibliografia[ | edytuj kod]

  • Adam Drozdek, Donald L. Simon, Struktury danych w języku C, Warszawa, WNT, s. 279–302, 1996, ​ISBN 83-204-1981-6​.
  • Franklin Mark Liang, Word Hyphen-a-tion by Com-put-er, Departament of Computer Science, Stanford University, Report No. STAN-CS-83-977.
  • Linki zewnętrzne[ | edytuj kod]

  • Wizualizacja drzewa trie




  • Reklama

    Czas generowania strony: 0.011 sek.