Óòâåðæäåíèå.
a) Äëÿ êàæäîãî ïîñåùåííîãî óçëà v dist[v] ÿâëÿåòñÿ íàèìåíüøåé äëèíîé ïóòè îò èñõîäíîé âåðøèíû source äî óçëà v.
b) Äëÿ êàæäîãî íåïîñåùåííîãî óçëà u dist[u] ÿâëÿåòñÿ íàèìåíüøåé äëèíîé ïóòè îò source äî u.
Äîêàçàòåëüñòâî ïî èíäóêöèè ïî ÷èñëó ïîñåùåííûõ óçëîâ.
1) Áàçà: åñëè ïîñåùåí òîëüêî îäèí óçåë (source), dist äëÿ âñåõ íåïîñåùåííûõ óçëîâ ðàâíà äëèíå ðåáðà, èäóùåãî â íèõ èç source, åñëè òàêîå ðåáðî ñóùåñòâóåò, è áåñêîíå÷íîñòè, åñëè òàêîãî ðåáðà íåò.  ýòîì ñëó÷àå
- âåðíîñòü ïðåäïîëîæåíèÿ a) î÷åâèäíà (ïóòü îò source äî source ðàâåí 0 è ýòî êðàò÷àéøèé ïóòü). - ïðåäïîëîæåíèå b) òàêæå âåðíî, òàê êàê êðàò÷àéøèé ïóòü èç source â êàæäóþ íåïîñåùåííóþ âåðøèíó êàê ðàç è áóäåò ðåáðî, ñâÿçûâàþùåå source è ýòó âåðøèíó, åñëè ýòî ðåáðî ñóùåñòâóåò.  ïðîòèâíîì ñëó÷àå äëèíà êðàò÷àéøåãî ïóòè áåñêîíå÷íîñòü, òî åñòü òîæå ðàâíà dist.
2) Äîïóñòèì, ïðåäïîëîæåíèå âåðíî äëÿ n-1 óçëîâ. Ïî àëãîðèòìó Äåéêñòðû n-ûì ïîñåùåííûì óçëîì áóäåò óçåë u, òàêîé, ÷òî çíà÷åíèå dist[u] – íàèìåíüøåå èç âñåõ íåïîñåùåííûõ óçëîâ. Äîêàæåì, ÷òî dist[u] – äëèíà êðàò÷àéøåãî ïóòè îò source äî u.
Áóäåì äîêàçûâàòü îò îáðàòíîãî.
Ïóñòü ñóùåñòâóåò áîëåå êîðîòêèé ïóòü Q îò source äî u: len(Q) < dist[u]. (1)
Ïóñòü y – ïåðâàÿ íåïîñåùåííàÿ âåðøèíà íà ýòîì ïóòè (âîçìîæíî, ýòî u) è x – âåðøèíà íåïîñðåäñòâåííî ïåðåä y íà ýòîì ïóòè.
Òîãäà len(Qx) + len(x,y) <= len(Q) (2), ãäå Qx – ÷àñòü ïóòè Q îò source äî x, à len(x,y) – äëèíà ðåáðà ìåæäó x è y.
Òàê êàê ïî ïðåäïîëîæåíèþ èíäóêöèè dist[x] – äëèíà êðàò÷àéøåãî ïóòè îò source äî x, òî dist[x] <= len(Qx) (3).
Òàê êàê y – ñìåæíàÿ ñ x (ò.å. ñîåäèíåíà ðåáðîì), òî çíà÷åíèå dist[y] äîëæåí áûòü íàñòðîåíî àëãîðèòìîì: dist[y] <= dist[x] + len(x,y) (4).
Òàê êàê èç âñåõ íåïîñåùåííûõ âåðøèí àëãîðèòì âûáðàë u (âåðøèíà ñ íàèìåíüøèì çíà÷åíèåì dist èç íåïîñåùåííûõ), òî dist[u] <= dist[y] (5).
Òàêèì îáðàçîì, ìû èìååì ñëåäóþùóþ öåïî÷êó íåðàâåíñòâ:
(3) (2) (1) (5) (4)
dist[x] + len(x,y) <= len(Qx) + len(x,y) <= len(Q) < dist[u] <= dist[y] <= dist[x] + len(x,y)
èç êîòîðîé ñëåäóåò, ÷òî:
dist[x] < dist[x],
÷òî îçíà÷àåò, ÷òî ìû ïðèøëè ê ïðîòèâîðå÷èþ.
Çàäà÷à. Ïðåâðàòèòü áèíàðíîå áåðåâî ïîèñêà â óïîðÿäî÷åííûé L1-ñïèñîê (ïðîéòè ïî áèíàðíîìó äåðåâó ïîèñêà â ïîðÿäêå âîçðàñòàíèÿ çíà÷åíèé)
ÑÏ L1-ñïèñêà
5. Ïîñòàâèòü óêàçàòåëü â íà÷àëî ñïèñêà === óêàçàòåëü := Íàéòè ìèíèìàëüíûé ýëåìåíò â ïîääåðåâå
6. Ïåðåäâèíóòü óêàçàòåëü âïåðåä === óêàçàòåëü := Ñëåäóþùèé óçåë <âõ: óêàçàòåëü>
7. Ýëåìåíò çà óêàçàòåëåì === óêàçàòåëü.Çíà÷åíèå ýëåìåíòà
8. Âñòàâèòü ýëåìåíò çà óêàçàòåëåì === ??? äëÿ óïîðÿäî÷åííîãî L1-ñïèñêà — íå èìååò ñìûñëà
9. Óäàëèòü ýëåìåíò çà óêàçàòåëåì === ???
Áèíàðíîå äåðåâî ïîèñêà — òàêîå áèíàðíîå äåðåâî, â êîòîðîì çíà÷åíèå â óçëå áîëüøå, ÷åì çíà÷åíèÿ â åãî ëåâîì ïîääåðåâå è ìåíüøå, ÷åì çíà÷åíèå â åãî ïðàâîì ïîääåðåâå.
 êàæäîì óçëå õðàíèòñÿ ññûëêà íà ëåâûé è ïðàâûé äî÷åðíèé óçëû, à òàêæå ññûëêà íà ðîäèòåëüñêèé óçåë. Ïðè îòñóòñòâèè ó óçëà ïðàâîãî èëè ëåâîãî äî÷åðíåãî óçëà ññûëêè íà íèõ âûðîæäåíû (ðàâíû 0).
Ïîèñê.
Ïðîöåäóðà Íàéòè çíà÷åíèå<âõ: V>
òåêóùèé óçåë := äåðåâî.êîðåíü
öèêë ïîêà òåêóùèé óçåë íå âûðîæäåí
åñëè òåêóùèé óçåë.çíà÷åíèå == V òî
îòâåò := òåêóùèé óçåë
íàéäåíî := äà
âûéòè èç ïðîöåäóðû
èíà÷å
åñëè òåêóùèé óçåë.çíà÷åíèå > V òî
òåêóùèé óçåë := òåêóùèé óçåë.ëåâûé äî÷åðíèé óçåë
èíà÷å
òåêóùèé óçåë := òåêóùèé óçåë.ïðàâûé äî÷åðíèé óçåë
êîíåö åñëè
êîíåö åñëè
êîíåö öèêëà
îòâåò := òåêóùèé óçåë.ðîäèòåëüñêèé óçåë.çíà÷åíèå
íàéäåíî := íåò
Êîíåö ïðîöåäóðû
Äîáàâëåíèå.
Ïðîöåäóðà Äîáàâèòü ýëåìåíò ê äåðåâó <âõ: V: ýëåìåíò, U: óçåë>
! Äîáàâëÿåì ýëåìåíò V êàê äî÷åðíèé óçåë óçëà U
äåðåâî.ñîçäàòü íîâûé óçåë<âûõ: íîâûé óçåë>
íîâûé óçåë.ëåâûé äî÷åðíèé óçåë := 0
íîâûé óçåë.ïðàâûé äî÷åðíèé óçåë := 0
åñëè U.çíà÷åíèå > V òî
U.ëåâûé äî÷åðíèé óçåë := íîâûé óçåë
èíà÷å
U.ïðàâûé äî÷åðíèé óçåë := íîâûé óçåë
êîíåö åñëè
Êîíåö ïðîöåäóðû
Ïîèñê ìèíèìàëüíîãî
Ïðîöåäóðà Íàéòè ìèíèìàëüíûé ýëåìåíò â ïîääåðåâå <âõ: U: óçåë>
! Íàõîäèì ìèíèìàëüíûé ýëåìåíò ïîääåðåâà ñ êîðíåì â U
òåêóùèé óçåë = U
öèêë ïîêà (òåêóùèé óçåë != 0) è (òåêóùèé óçåë.ëåâûé äî÷åðíèé óçåë != 0)
òåêóùèé óçåë := òåêóùèé óçåë.ëåâûé äî÷åðíèé óçåë
êîíåö öèêëà
îòâåò := òåêóùèé óçåë
Êîíåö ïðîöåäóðû
Ïîèñê ìàêñèìàëüíîãî — àíàëîãè÷íî
Ïðîõîä ïî äåðåâó â ïîðÿäêå âîçðàñòàíèÿ çíà÷åíèé
Ïðîöåäóðà Ñëåäóþùèé óçåë<âõ: óçåë>
åñëè óçåë.ïðàâûé äî÷åðíèé óçåë != 0 òî
îòâåò := íàéòè ìèíèìàëüíûé ýëåìåíò<âõ: óçåë> (1)
èíà÷å
åñëè óçåë == óçåë.ðîäèòåëüñêèé óçåë.ëåâûé äî÷åðíèé óçåë òî
îòâåò := óçåë.ðîäèòåëüñêèé óçåë (2)
èíà÷å
öèêë ïîêà óçåë == óçåë.ðîäèòåëüñêèé óçåë.ïðàâûé äî÷åðíèé óçåë âûïîëíÿòü
óçåë := óçåë.ðîäèòåëüñêèé óçåë
êîíåö öèêëà
óòâåðæäåíèå: óçåë — ëåâûé äî÷åðíèé óçåë ñâîåãî ðîäèòåëüñêîãî óçëà
îòâåò := óçåë.ðîäèòåëüñêèé óçåë (3)
êîíåö åñëè
êîíåö åñëè
Êîíåö ïðîöåäóðû
(2) (1) (2) (3) (1) (2) (1)
-2 → 3 → 4 → 6 → 10 → 12 → 17 → 18
