Drzewa dwumianowe
Z Wikipedii
Drzewo dwumianowe (ang. binomial tree) Bk jest drzewem poszukiwań zdefiniowanym rekurencyjnie w sposób następujący:
- drzewo dwumianowe B0 składa się z jednego węzła (korzenia);
- drzewo dwumianowe Bk składa się z dwóch drzew dwumianowych Bk-1 powiązanych tak, że korzeń jednego z nich jest lewym skrajnym potomkiem drugiego.
[edytuj] Własności drzew dwumianowych
- drzewo dwumianowe Bk posiada dokładnie 2k węzłów;
- wysokość drzewa Bk wynosi (k + 1);
- na poziomie i-tym drzewa Bk znajduje się dokładnie węzłów (stąd min. wywodzi się nazwa drzewa);
- stopień korzenia wynosi k, zaś wszystkie pozostałe węzły, jeżeli istnieją, to mają stopień co najwyżej k - 1;
- jeżeli ponumerować potomków korzenia kolejno: k - 1, k - 2, ..., 2, 1, 0 to potomek o numerze i-tym jest drzewem dwumianowym Bi;
- maksymalny stopień węzła w drzewie dwumianowym zawierającym n węzłów wynosi lg n.