2277150874

Całkowita ilość elementów, jaka będzie w drzewie o podanym stopniu i wysokości daje się łatwo policzyć, jako prosta zależność wykładnicza Drzewa wyższych stopni mają oczywiście więcej gałęzi.

Poza drzewami różniącymi się stopniem istnieją jeszcze inne ich odmiany. Drzewa zlewowe to takie, w których odwrócono kierunek wskaźników (mają wiele korzeni, a tylko jeden liść lub niewiele liści). Odwrotnym rodzajem są drzewa wylewowe (rozpływowe). Drzewa balansowane (AVL - średniej długości, ważone) to przykłady drzew, które "dbają" o swoją minimalną głębokość. Jeszcze innym rodzajem drzew są sterty, przydatne bardzo w pewnych implementacjach sortowania. Istnieją także drzewa czarno-czerwone (bez skojarzeń) oraz zupełnie oryginalne drzewa mutanty, jak np. drzewa zwrotne, drzew a łączone z listami, itp.

GRAFY

Można zbudować strukturę, która będzie miała zamiast określonej ilości wskaźników¹ (jak lista lub drzewo), po prostu listę wskaźników do następnych elementów. Można także założyć, że nie wszystkie z tych wskaźników będą musiały na coś konkretnego pokazywać. Otrzymamy wtedy najbardziej skomplikowaną strukturę z możliwych, w informatyce nazywaną grafem. Ogólnie rzecz biorąc, graf definiuje się jako zbiór elementów oraz zbiór połączeń pomiędzy nimi. Dlatego struktura, dla której możliwa jest implementacja grafu, zawiera po prostu wskaźniki do dwóch list - na których przechowywane są połączenia pomiędzy elementami oraz odpowiednio same elementy. Graf) mogą posiadać rozmaite "kształty". Szczególnymi przypadkami grafów' są np. listy i drzewa. Zależnie od właściwości grafów, określa się je jako zorientowane, niezorientowane, acykliczne, cykliczne, itp. Połączenia pomiędzy elementami nazywa się krawędziami. Krawędź jest ukierunkow⁷ana, jeżeli możliwy jest ruch po niej tylko w jedną stronę, natomiast gdy możliwy jest w obie strony - nie ma określonego kierunku lub łączność jest bezkierunkowa. Zagadnieniami związanymi z tymi przedziwnymi i skomplikowanymi strukturami danych zajmuje się odrębna dziedzina wiedzy matematycznej - teoria grafów.

Strona 7 z 41