Witam
Powiedzmy że mam takie B drzewo:
I teraz biorę sobie klucz "N" i szukam jego poprzednika, w normalnym drzewie byłoby to "M", ale w B drzewach nie pamiętam wskaźnika do rodzica, czy w takim razie możliwe jest znalezienie poprzednika "N", czy też jest on po prostu równy NIL?
Pozdrawiam i liczę na pomoc
flusia
B drzewa
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
B drzewa
Zależy, co rozumiesz przez "poprzednik". Zwykle "poprzednik N" oznacza "największy klucz mniejszy niż N". To, co jest pamiętane w drzewie, a także czy da się takiego poprzednika łatwo znaleźć, nie ma dla definicji znaczenia.
A szukać go trzeba trochę sprytniej: zaczynasz od korzenia (M) i wiesz, że ewentualny poprzednik N, gdyby był jakiś lepszy niż M, musi leżeć na prawo od M. Wchodzisz w prawe poddrzewo M (na węzeł P) i wiesz, że poprzedniki N muszą leżeć w skrajnie lewym poddrzewie P. Czyli sprawdzasz to drzewo...
A szukać go trzeba trochę sprytniej: zaczynasz od korzenia (M) i wiesz, że ewentualny poprzednik N, gdyby był jakiś lepszy niż M, musi leżeć na prawo od M. Wchodzisz w prawe poddrzewo M (na węzeł P) i wiesz, że poprzedniki N muszą leżeć w skrajnie lewym poddrzewie P. Czyli sprawdzasz to drzewo...
-
- Użytkownik
- Posty: 31
- Rejestracja: 22 lis 2007, o 18:31
- Płeć: Mężczyzna
- Lokalizacja: Lubin/Wrocław
- Podziękował: 2 razy
- Pomógł: 1 raz
B drzewa
To znaczy głownie chodzi mi o zadanie w "Cormenie", czyli znalezienie algorytmu na wyznaczanie poprzednika w B drzewie, więc głównie chodziło mi o to czy według definicji podanej przez Cormena jest możliwe określenie poprzednika, bo nic o tym nie było, a znalazłem w sieci ten algorytm napisany przez jakiegoś wykładowcę i tam było że poprzednikiem N jest NIL. Zarys sposobu na powiedzenie że jest to M wymyśliłem także chodzi mi tylko o to jak to jest według definicji.