algorytm wyszukiwania następnika w BST

1 procedure drzewo następnik(x);
2 begin
3 if x.prawy syn 6= NIL then
4 return drzewo minimum(x.prawy syn);
5 end if;
6 y := x.rodzic;
7 while y != NIL and x = y.prawy syn do
8 x := y;
9 y := y.rodzic;
10 end while;
11 return y;
12 end.

(http://sun.aei.polsl.pl/~sdeor/students/aa/drzewo_nastepnik.pdf)
W tej pierwszej części kodu (do 5 linii) wiem co się dzieje, natomiast dalej to juz nie bardzo...

1. po co ten warunek y.prawy_syn = x?
2. x=y - po co co x przypisywać jego rodzica?
3. sensu 9 linii kodu kompletnie nie rozumiem
4. no i dlaczego to wszystko odbywa się w pętli while?

Następnik elementu x w drzewie to albo:

• minimum z prawej gałęzi jeżeli ta prawa gałąź istnieje (linijki 3 - 5),
• najniższy przodek którego lewa gałąź zawiera element x (linijki 6 - 11),

W pętli while idziemy do góry drzewa, a y jest rodzicem x, przerywamy gdy x jest lewym dzieckiem y i zwracamy to y, zgodnie z tym co napisałem powyżej.

dlaczego przerywamy jeśli x jest lewym dzieckiem y?

Ponieważ w tym momencie, nowy x, a co za tym podany do funkcji, należy do lewej gałęzi y, a więc y jest później w porządku ustalonym przez drzewo.

Ten algorytm jest prościutki. Narysuj sobie drzewo na kartce i wykonaj sobie ten algorytm kilka razy z rzędu to zobaczysz jak działa.

ale dlaczego ta pętla while czyli wyszukiwanie następnika niżej w drzewie wykonuje się zawsze?
narysowałem sobie drzewo w którym następnik dla pewnego elementu x został znaleziony przez funkcje drzewo_minimum, po co więc przeszukuje jeszcze przodków?

nie wykonuje się zawsze, tylko wtedy, gdy tego poddrzewa tam nie ma, jak poddrzewo jest to jest return i przodków już nie przeszukuje;p

żeby nie zakładać nowego tematu mam jeszcze inny problem związany z drzewkiem, chodzi o wstawianie nowego elementu: http://sun.aei.polsl.pl/~sdeor/students/aa/drzewo_wstaw.pdf

7 linijka kodu - co to jest x.klucz i e.klucz, jakie mają wartości?

Klucz to pole w węźle. Więcej info tutaj:
http://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84