• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Drzewo - informatyka



    Podstrony: [1] 2 [3]
    Przeczytaj także...
    Drzewo przedziałowe (interval tree, range tree, drzewo zakresowe), struktura danych przechowująca punkty, oraz związane z tymi punktami wszystkie możliwe przedziały. Drzewo przedziałowe, jeśli jest skonstruowane tak, aby było zrównoważone, pozwala odpowiadać na zapytania o dowolny przedział w czasie logarytmicznym.B-drzewo – drzewiasta struktura danych, przechowująca klucze w pewnym porządku i powiązane z nimi dane, używana przede wszystkim w systemach baz danych. Popularniejsze w zastosowaniach bazodanowych i systemach plików są B+drzewa, które są szczególnym przypadkiem B-drzew, przechowującym dane tylko w liściach.
    Operacja na drzewach[ | edytuj kod]

    Podstawowe operacje na drzewach to:

  • wyliczenie wszystkich elementów drzewa,
  • wyszukanie konkretnego elementu,
  • dodanie nowego elementu w określonym miejscu drzewa,
  • usunięcie elementu.
  • Pod pojęciem przechodzenia drzewa rozumie się odwiedzanie kolejnych wierzchołków, zgodnie z zależnościami rodzic-dziecko. Jeśli przy przechodzeniu drzewa na wierzchołkach są wykonywane pewne działania, to mówi się wówczas o przechodzeniu:

    OCaml znany pierwotnie jako Objective Caml to wielo-paradagmatowy język programowania oraz implementacja tego języka w postaci zestawu narzędzi i bibliotek.Tekstowy typ danych (ang. String) – typ danych służący do przechowywania ciągu znaków (zmiennych łańcuchowych).
  • preorder - gdy działanie jest wykonywane najpierw na rodzicu, następnie na dzieciach;
  • postorder - gdy działanie jest wykonywane najpierw na wszystkich dzieciach, na końcu na rodzicu.
  • W przypadku drzew binarnych (oraz pewnych innych typów drzew) istnieje jeszcze metoda inorder, gdzie najpierw wykonywane jest działanie na jednym z dzieci, następnie na rodzicu i na końcu na drugim dziecku.

    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.Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.

    Jeśli działaniem byłoby wypisanie liter przechowywanych w węzłach przykładowego drzewa, to przy przechodzeniu drzewa metodą preorder otrzymamy F, B, A, D, C, E, G, I, H, natomiast przy przechodzeniu drzewa metodą postorder: A, C, E, D, B, H, I, G, F.

    Reprezentacja drzew[ | edytuj kod]

    Fizycznie drzewa są reprezentowane za pomocą struktur wiązanych – ogólnie pojedynczy wierzchołek przechowuje dane oraz dowiązania do swoich dzieci. W szczególności jeśli drzewo jest zapisane w tablicy (patrz: kopiec), to dzieci są wskazywane przez konkretne indeksy; jeśli drzewo jest budowane na stercie (w językach C, C++, Pascal i podobnych), wówczas dowiązania są wskaźnikami.

    Kopiec (ang. heap, tłumaczone też jako stóg lub sterta) – w informatyce struktura danych oparta na drzewie, w której wartości potomków węzła są w stałej relacji z wartością rodzica (na przykład wartość rodzica jest nie mniejsza niż wartości jego potomka).Drzewo trie (wym. traj; od ang. retrieval, czyli odczyt) — 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.

    Przykład definicji typu drzewa binarnego, w którym dane występują tylko na liściach (OCaml):

    type 'a Drzewo = Lisc of 'a | Wezel of 'a Drzewo * 'a Drzewo
    

    Przykład definicji typu drzewa binarnego, w którym dane (napisy) występują w każdym węźle (język C):

    struct drzewo {
    	struct drzewo *lewy_syn;
    	struct drzewo *prawy_syn;
    	char *dane;
    };
    
    Lista - struktura danych służąca do reprezentacji zbiorów dynamicznych, w której elementy ułożone są w liniowym porządku. Rozróżniane są dwa podstawowe rodzaje list: lista jednokierunkowa w której z każdego elementu możliwe jest przejście do jego następnika oraz lista dwukierunkowa w której z każdego elementu możliwe jest przejście do jego poprzednika i następnika.Pascal – dawniej jeden z najpopularniejszych języków programowania, uniwersalny, wysokiego poziomu, ogólnego zastosowania, oparty na języku Algol. Został opracowany przez Niklausa Wirtha w 1970 roku. Nazwa języka pochodzi od nazwiska francuskiego fizyka, matematyka i filozofa Blaise Pascala.


    Podstrony: [1] 2 [3]



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    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.
    Drzewo trójkowe (ternary search tree) – struktura danych do wyszukiwania napisów, łącząca szybkość działania drzewa trie, oraz małe użycie pamięci drzew binarnych.
    Drzewo – oznacza w teorii grafów graf, który jest acykliczny i spójny. Mówiąc językiem obrazowym, z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) i tylko jednym sposobem (acykliczność, czyli brak możliwości chodzenia w "kółko").
    Baza danych – zbiór danych zapisanych zgodnie z określonymi regułami. W węższym znaczeniu obejmuje dane cyfrowe gromadzone zgodnie z zasadami przyjętymi dla danego programu komputerowego specjalizowanego do gromadzenia i przetwarzania tych danych. Program taki (często pakiet programów) nazywany jest „systemem zarządzania bazą danych” (ang. database management system, DBMS).
    Grafika komputerowa – dziedzina informatyki zajmująca się wykorzystaniem technik komputerowych do celów wizualizacji artystycznej oraz wizualizacji rzeczywistości. Grafika komputerowa jest obecnie narzędziem powszechnie stosowanym w nauce, technice oraz rozrywce.
    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.
    C – imperatywny, strukturalny język programowania wysokiego poziomu stworzony na początku lat siedemdziesiątych XX w. przez Dennisa Ritchiego do programowania systemów operacyjnych i innych zadań niskiego poziomu.

    Reklama

    Czas generowania strony: 0.008 sek.