Domena Internetowa Słupsk - Tanio i Profesjonalnie

- | - Domena - DNS - DDNS DNSSEC - Lista domen najwyższego poziomu - Domeny poziomy - Strona internetowa - IP Adres Protokół internetowy - Internet Intranet Ekstranet - Sieci komputerowe - Dostawca usług internetowych - Poczta E-mail - | -
- | - Subdomena - Sklep Internetowy - Serwer - Drzewo - Mnemonik - HTTP HTTPS S-HTTP - Model TCP/IP - DHCP - ARPANET ALOHAnet SIPRNet - BITNET - IETF - Zatruwanie DNS - ISOC - Historia Internetu - Netykieta - | -

Słupsk / Domeny On-line / Drzewo

Drzewo – 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.
Znaczenie tych struktur jest bardzo duże i ze względu na swoje własności drzewa są stosowane praktycznie w każdej dziedzinie informatyki (np. bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja, serwery).

Domeny Internetowe Słupsk

Budowa drzewa
Drzewa składają się z wierzchołków (węzłów) oraz łączących je krawędzi. Jeśli drzewo nie jest puste, tzn. liczba wierzchołków jest większa od zera, jeden z nich jest wyróżniony i nazywany korzeniem drzewa; na rysunku jest oznaczony literą F.
Ciąg krawędzi łączących węzły nazywa się ścieżką. Istnieje dokładnie jedna ścieżka łącząca korzeń z każdym pozostałym wierzchołkiem.
Liczba krawędzi w ścieżce od korzenia do węzła jest nazywana długością – liczba ta określa poziom węzła. Wysokością drzewa jest największy poziom istniejący w drzewie. Np. korzeń znajduje się na 0. poziomie, węzły A, D i I na poziomie 2.; wysokość drzewa to 3.
Wszystkie wierzchołki połączone z danym wierzchołkiem, a leżące na następnym poziomie są nazywane dziećmi tego węzła (np. dziećmi wierzchołka F są B i G, natomiast wierzchołka B: A i D). Wierzchołek może mieć dowolną liczbę dzieci, jeśli nie ma ich wcale nazywany jest liściem. Liśćmi w przykładowym drzewie są A, C, E, H.
Wierzchołek jest rodzicem dla każdego swojego dziecka. Każdy węzeł ma dokładnie jednego rodzica, wyjątkiem jest korzeń drzewa, który nie ma rodzica.
Specjalne znaczenie w informatyce mają drzewa binarne, w których liczba dzieci ograniczona jest do dwóch. Szczególnie popularne są BST i ich różne odmiany, np. drzewa AVL, drzewa czerwono-czarne.
Drzewa które posiadają więcej niż dwoje dzieci są nazywane drzewami wyższych rzędów, np. drzewo trie, drzewo trójkowe, B-drzewo.
Lista może być rozpatrywana jako szczególny przypadek drzewa, gdzie każdy rodzic ma co najwyżej jedno dziecko (drzewo pierwszego rzędu).

Operacja na drzewach
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:
- 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.

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
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.

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

Domeny Internetowe Słupsk

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

Domeny Internetowe Słupsk

- | - NASK - LABORATORIA BIOMETRII NASK - SAFER INTERNET - CERT POLSKA - TASK - ICM - SCI.PL - CHEM.PL - CYFRONET AGH - ISOC POLSKA - KRAJOWY REJESTR DOMEN - | -
- | - ICANN - IANA - INTERNET SOCIETY - WEBBY AWARD - WHO IS - VIRUS TOTAL - | -