Drzewo binarne

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Przykładowe drzewo binarne o rozmiarze 9 i wysokości 3

Drzewo binarne w teorii grafów to drzewo, w którym stopień każdego wierzchołka jest nie większy od 3.

Ukorzenione drzewo binarne to drzewo binarne, w którym wyróżniono jeden z wierzchołków (zwany korzeniem) stopnia najwyżej 2.

W informatyce drzewo binarne to jeden z rodzajów drzewa (struktury danych), w którym liczba synów każdego wierzchołka wynosi nie więcej niż dwa. Wyróżnia się wtedy lewego syna i prawego syna danego wierzchołka.

Drzewo binarne, w którym liczba synów każdego wierzchołka wynosi albo zero albo dwa, nazywane jest drzewem regularnym. Przykładem takich drzew są drzewa Huffmana.

Szczególnymi odmianami drzew binarnych są drzewa BST, drzewa BSP oraz kopce.

Własności[edytuj | edytuj kod]

Liczba n-wierzchołkowych ukorzenionych drzew binarnych wynosi:

b_0=1
b_1=1
b_n=\sum_{j=0}^{n-1}b_jb_{n-1-j}

Istnieje też postać zwarta:

b_n=\frac{1}{n+1}{2n \choose n}

znana jako rekursywna relacja Catalana.

Zobacz też[edytuj | edytuj kod]