Drzewo (informatyka)
Z Wikipedii
W informatyce drzewa są strukturami danych reprezentującymi drzewa matematyczne. W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.), toteż głównie do tego celu są stosowane. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. Znaczenie tych struktury 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).
Drzewa składają się z wierzchołków (węzłów) oraz łączących je krawędzi. 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 D są G i H, wierzchołka H: J, K oraz L). Wierzchołek może mieć dowolną liczbę dzieci, jeśli nie ma ich wcale nazywany jest liściem; na rysunku liście zaznaczone są kolorem niebieskim.
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.
W drzewie istnieje dokładnie jedna ścieżka pomiędzy węzłem a korzeniem; przez ścieżkę rozumie się ciąg krawędzi, na rys. przykładowa ścieżka do węzła J jest zaznaczona na czerwono. Liczba krawędzi w ścieżce jest nazywana długością (lub głębokością) – liczba o jeden większa określa poziom węzła. Z kolei wysokość drzewa to największy poziom istniejący w drzewie (przykładowe drzewo ma wysokość 4).
Specjalne znaczenie w informatyce mają drzewa binarne (liczba dzieci ograniczona do dwóch) i ich różne odmiany, np. drzewa AVL, drzewa czerwono-czarne, BST; drzewa które posiadają więcej niż dwoje dzieci są nazywane drzewami wyższych rzędów.
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 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 ABEFCDGIHJKL, natomiast przy przechodzeniu drzewa metodą postorder: EFBCIGJKLHDA.
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ą wskazywani 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, w którym dane występują tylko na liściach (ocaml):
type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree
Przykład definicji typu drzewa, w którym dane (napisy) występują na każdym węźle (C):
struct tree {
struct tree *left;
struct tree *right;
char *dane;
};
Przykładowy program w języku Pascal. Buduje drzewo BST i je przekształca w drzewo wyważone.
program drzewo;
uses crt;
type
wsk=^wezel;
wezel=record
d:integer;
l:wsk;
r:wsk;
end;
var n,i,x:integer;
p:wsk;
poz:byte;
procedure do_drzewa(var p:wsk; x:integer);
var q:wsk;
begin
if p=nil then
begin
new(p);
p^.d:=x;
p^.l:=nil;
p^.r:=nil;
end
else
begin
if x<p^.d then if p^.l=nil then
begin
new(q);
q^.d:=x;
q^.l:=nil;
q^.r:=nil;
p^.l:=q;
end else
do_drzewa(p^.l,x)
else
if p^.r=nil then
begin
new(q);
q^.d:=x;
q^.l:=nil;
q^.r:=nil;
p^.r:=q;
end else
do_drzewa(p^.r,x);
end;
end;
function licz(p:wsk):integer;
var k:integer;
begin
if p<>nil then
begin
k:=1;
if p^.l<>nil then k:=k+licz(p^.l);
if p^.r<>nil then k:=k+licz(p^.r);
licz:=k;
end else licz:=0;
end;
procedure pokaz(p:wsk);
begin
writeln(p^.d);
if p^.l<>nil then pokaz(p^.l);
if p^.r<>nil then pokaz(p^.r);
end;
procedure wywaz(var p:wsk; b:integer);
var a:integer; q,w:wsk;
begin
b:=b-1;
a:=licz(p^.l);
b:=b-a;
while abs(a-b)>1 do
begin
if a>b then
begin
if p^.l^.r<>nil then
begin
q:=p^.l;
repeat
w:=q;
q:=q^.r;
until q^.r=nil;
q^.r:=p;
q^.l:=p^.l;
w^.r:=nil;
p^.l:=nil;
p:=q;
end
else
begin
p^.l^.r:=p;
q:=p^.l;
p^.l:=nil;
p:=q;
end;
a:=a-1;
b:=b+1;
end
else
begin
if p^.r^.l<>nil then
begin
q:=p^.r;
repeat
w:=q;
q:=q^.l;
until q^.l=nil;
q^.l:=p;
q^.r:=p^.r;
w^.l:=nil;
p^.r:=nil;
p:=q;
end
else
begin
p^.r^.l:=p;
q:=p^.r;
p^.r:=nil;
p:=q;
end;
a:=a+1;
b:=b-1;
end;
end;
if p^.l<>nil then wywaz(p^.l,a);
if p^.r<>nil then wywaz(p^.r,b);
end;
begin
p:=nil;
clrscr;
writeln;
write('Ile elementow? ');
readln(n);
for i:=1 to n do begin write('Element numer ',i,': '); readln(x);
do_drzewa(p,x); end;
writeln;
writeln('Nie wywazone:');
pokaz(p);
n:=licz(p);
writeln('Elementow jest ',n);
wywaz(p,n);
writeln;
writeln('Wywazone:');
pokaz(p);
readln;
end.
