preorder {|y| yield y} if @left != nil
@right.preorder {|y| yield y} if @right != nil
end
def postorder()
@left.postorder {|y| yield y} if @left != nil
@right.postorder {|y| yield y} if @right != nil
yield @data
end
end
items = [50, 20, 80, 10, 30, 70, 90, 5, 14,
28, 41, 66, 75, 88, 96]
tree = Tree.new
items.each {|x| tree.insert(x)}
Rozdział 9. • ZAAWANSOWANE STRUKTURY DANYCH
363
tree.inorder {|x| print x, " "}
print "\n"
tree.preorder {|x| print x, " "}
print "\n"
tree.postorder {|x| print x, " "}
print "\n"
# Dane wyjściowe:
# 5 10 14 20 28 30 41 50 66 70 75 80 88 90 96
# 50 20 10 5 14 30 28 41 80 70 66 75 90 88 96
# 5 14 10 28 41 30 20 66 75 70 88 96 90 80 50 print "\n"
9.3.3. STOSOWANIE DRZEWA BINARNEGO
W ROLI TABLICY WYSZUKIWANIA
Przypuśćmy, że dysponujemy posortowanym drzewem. Posortowane struktury drze-wiaste tradycyjnie sprawdzają się w roli tablic wyszukiwania; przykładowo, odnalezie-nie określonego węzła w posortowanym drzewie zrównoważonym reprezentującym milion elementów wymaga (w najgorszym przypadku) zaledwie dwudziestu operacji porównania (głębokość takiego drzewa jest równa logarytmowi o podstawie równej 2 z liczby węzłów). Aby prezentowane rozwiązanie w jak największym stopniu ilu-strowało rzeczywiste zastosowania, zakładamy, że dane składowane w poszczególnych węzłach nie mają postaci pojedynczych wartości, tylko kluczy wskazujących na powiązane ze sobą dane.
W większości (jeśli nie we wszystkich sytuacjach) tablice mieszające lub tabele ze-wnętrznych baz danych lepiej sprawdzają się w tej roli. Mimo to warto przeanalizo-wać przedstawiony poniżej przykład kodu źródłowego:
class Tree
# Zakładamy, że dysponujemy definicjami
# z wcześniejszych przykładów…
def search(x)
if self.data == x
return self
elsif x < self.data
return left ? left.search(x) : nil
else
return right ? right.search(x) : nil
end
end
end
keys = [50, 20, 80, 10, 30, 70, 90, 5, 14,
28, 41, 66, 75, 88, 96]
364
RUBY. TAO PROGRAMOWANIA W 400 PRZYKŁADACH
tree = Tree.new
keys.each {|x| tree.insert(x)}
s1 = tree.search(75) # Zwraca referencję do węzła zawierającego
# wartość 75…
s2 = tree.search(100) # Zwraca wartość nil (żądanego węzła nie odnaleziono).
9.3.4. KONWERSJA DRZEWA NA ŁAŃCUCH LUB TABLICĘ
Te same zabiegi, które umożliwiają efektywne przeszukiwanie drzewa, możemy z powodzeniem wykorzystywać do konwertowania tego rodzaju struktur na łańcuchy i tablice. Tym razem przeszukujemy drzewo w porządku inorder, chociaż równie dobrze moglibyśmy zastosować inną technikę:
class Tree
# Zakładamy, że dysponujemy definicjami
# z wcześniejszych przykładów…
def to_s
"[" +
if left then left.to_s + "," else "" end +
data.inspect +
if right then "," + right.to_s else "" end + "]"
end
def to_a
temp = []
temp += left.to_a if left
temp << data
temp += right.to_a if right
temp
end
end
items = %w[bongo grimace monoid jewel plover nexus synergy]
tree = Tree.new
items.each {|x| tree.insert x}
str = tree.to_a * ","
# Zmienna str zawiera teraz łańcuch "bongo,grimace,jewel,monoid,nexus,plover,synergy".
arr = tree.to_a
# Zmienna arr zawiera teraz tablicę:
# ["bongo",["grimace",[["jewel"],"monoid",[["nexus"],"plover",
# ["synergy"]]]]]
Rozdział 9. • ZAAWANSOWANE STRUKTURY DANYCH
365
Warto zwrócić uwagę na fakt, że tablica wynikowa jest zagnieżdżona w stopniu odpowiadającym głębokości drzewa, na podstawie którego została wygenerowana. Możemy oczywiście użyć metody flatten do przekształcenia tej tablicy w strukturę niezagnież-
dżoną (płaską).
9.4. PRACA Z GRAFAMI
Graf jest kolekcją węzłów, które mogą być ze sobą połączone w dowolny sposób. (Spe-cyficznym przykładem grafu jest drzewo). Nie będziemy się zagłębiali w szczegółowe analizy zagadnień związanych z grafami, ponieważ przedstawienie niezbędnej teorii i terminologii zajęłoby nam mnóstwo czasu. Zanim jednak przystąpimy do prezentacji konkretnych przykładów, poświęcimy chwilę na ogólne rozważania na temat szeroko rozumianej informatyki i pewnych obszarów ze świata matematyki.
Okazuje się, że grafy mają wiele praktycznych zastosowań. Wyobraźmy sobie na przykład tradycyjny atlas samochodowy z drogami łączącymi miasta i miejscowości lub diagram obwodów elektrycznych. Najlepszą formą reprezentowania obu tych struktur jest właśnie graf. Teoria grafów doskonale nadaje się także do reprezentowania sieci komputerowych, niezależnie od tego, czy są to proste sieci LAN, duże struktury obejmujące wiele systemów, czy cały internet złożony z milionów węzłów.
Mówiąc o grafach, zwykle mamy na myśli grafy nieskierowane (ang. undirected graphs).
Najprościej mówiąc, graf nieskierowany to taki, w którym linie łączące poszczególne węzły nie są zakończone grotami (nie mają postaci strzałek); a dwa węzły mogą być albo połączone, albo nie. Inną formą grafu jest graf skierowany (ang. directed graph, digraph), który może zawierać „ulice jednokierunkowe”. W grafie skierowanym fakt połączenia węzła x z węzłem y nie oznacza, że istnieje połączenie w przeciwnym kierunku. Węzły bywają określane mianem wierzchołków (ang. vertexes). I wreszcie istnieje pojęcie grafu ważonego (ang. weighted graph), w którym poszczególne połączenia (krawędzie) mają przypisane wagi reprezentujące np. „odległości” dzielące połączone węzły. Na tym możemy zakończyć nasze wprowadzenie w świat grafów — Czytelnicy zainteresowani pogłębieniem swojej wiedzy mogą skorzystać z niezliczonych publikacji zarówno z dziedziny informatyki, jak i matematyki.
W języku Ruby (podobnie jak w większości języków programowania) graf może być reprezentowany na wiele różnych sposobów — w tym w formie prawdziwej sieci wzajemnie powiązanych obiektów lub macierzy zawierającej dane o krawędziach danego grafu. W dalszej części tego podrozdziału przeanalizujemy obie te reprezentacje i zapoznamy się z kilkoma praktycznymi przykładami przetwarzania grafów.
366
RUBY. TAO PROGRAMOWANIA W 400 PRZYKŁADACH
9.4.1. IMPLEMENTACJA GRAFU W FORMIE MACIERZY
SĄSIEDZTWA
W niniejszym punkcie przeanalizujemy przykład zbudowany na bazie dwóch wcze-
śniejszych przykładów. Kod zawarty w listingu 9.3 implementuje reprezentację grafu nieskierowanego w formie tzw. macierzy sąsiedztwa (ang. adjacent matrix). W prezentowanej implementacji wykorzystano klasę ZArray (punkt 8.1.26 zatytułowany „Okre-