B drzewa

flusia
Użytkownik
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

Post autor: flusia »

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
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

B drzewa

Post autor: paladin »

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...
flusia
Użytkownik
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

Post autor: flusia »

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.
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

B drzewa

Post autor: paladin »

Moim zdaniem jest to M. Nie wiem, jak by musiała wyglądać definicja, żeby było inaczej, i raczej byłaby mało sensowna.
ODPOWIEDZ