6.1 屈我峯議協吶嚥來嵎
6.1.1 屈我峯議児云古廷
1?屈我峯
屈我峯?Binary Tree?頁倖嗤尫圷殆議鹿栽?乎鹿栽賜宀葎腎、賜宀喇匯倖各葎功(root)議圷殆式曾倖音屢住議、瓜蛍艶各葎恣徨峯才嘔徨峯議屈我峯怏撹。輝鹿栽葎腎扮?各乎屈我峯葎腎屈我峯。壓屈我峯嶄?匯倖圷殆匆各恬匯倖潤泣。
屈我峯頁嗤會議?軸飛繍凪恣、嘔徨峯救宜?祥撹葎総匯臣音揖議屈我峯。軸聞峯嶄潤泣峪嗤匯臣徨峯?匆勣曝蛍万頁恣徨峯珊頁嘔徨峯。咀緩屈我峯醤嗤励嶽児云侘蓑?泌夕6.1 侭幣。
2?屈我峯議屢購古廷
?1?潤泣議業。潤泣侭啜嗤議徨峯議倖方各葎乎潤泣議業。
?2?匐潤泣。業葎0 議潤泣各葎匐潤泣?賜宀各葎嶮極潤泣。
?3?蛍乢潤泣。業音葎0 議潤泣各葎蛍屶潤泣?賜宀各葎掲嶮極潤泣。匯臣峯議潤泣茅匐潤泣翌?凪噫議脅頁蛍屶潤泣。
?4?恣頃徨、嘔頃徨、褒牌。峯嶄匯倖潤泣議徨峯議功潤泣各葎宸倖潤泣議頃徨。宸倖潤泣各葎万頃徨潤泣議褒牌。醤嗤揖匯倖褒牌議頃徨潤泣札各葎儘宮。
?5?揃抄、揃抄海業。泌惚匯臣峯議匯堪潤泣n1,n2,…,nk 嗤泌和購狼?潤泣ni 頁ni+1議幻潤泣?1≤i<k?,祥委n1,n2,…,nk 各葎匯訳喇n1 崛nk 議揃抄。宸訳揃抄議海業頁k-1。
?6?怕枠、徨柾。壓峯嶄?泌惚嗤匯訳揃抄貫潤泣M 欺潤泣N?椎担M 祥各葎N議怕枠?遇N 各葎M 議徨柾。
?7?潤泣議蚊方。号協峯議功潤泣議蚊方葎1?凪噫潤泣議蚊方吉噐万議褒牌潤泣議蚊方紗1。
?8?峯議侮業。峯嶄侭嗤潤泣議恷寄蚊方各葎峯議侮業。
?9?峯議業。峯嶄光潤泣業議恷寄峙各葎乎峯議業。
?10?諾屈我峯。
壓匯臣屈我峯嶄?泌惚侭嗤蛍屶潤泣脅贋壓恣徨峯才嘔徨峯?旺拝侭嗤匐徨潤泣脅壓揖匯蚊貧?宸劔議匯臣屈我峯各恬諾屈我峯。泌夕6.2 侭幣??a?夕祥頁匯臣諾屈我峯??b?夕夸音頁諾屈我峯?咀葎?埋隼凪侭嗤潤泣勣担頁根嗤恣嘔徨峯議蛍屶潤泣?勣担頁匐徨潤泣?徽喇噐凪匐徨隆壓揖匯蚊貧?絞音頁諾屈我峯。 ?11?頼畠屈我峯。
匯臣侮業葎k 議嗤n 倖潤泣議屈我峯?斤峯嶄議潤泣梓貫貧崛和、貫恣欺嘔議乏會序佩園催?泌惚園催葎i?1≤i≤n?議潤泣嚥諾屈我峯嶄園催葎i 議潤泣壓屈我峯嶄議了崔屢揖?夸宸臣屈我峯各葎頼畠屈我峯。頼畠屈我峯議蒙泣頁?匐徨潤泣峪嬬竃孖壓恷和蚊才肝和蚊?拝恷和蚊議匐徨潤泣鹿嶄壓峯議恣何。?堡撮r賛誕繡驊翳澍惷30拝賛値衄?驊翳?ii?衄?驊翳焞官慂蚤繡驊翳滇H舁?6.3 侭幣?a?葎匯臣頼畠屈我峯??b?才夕6.2?b?脅音頁頼畠屈我峯。
6.1.2 屈我峯議麼勣來嵎
來嵎1 匯臣掲腎屈我峯議及i 蚊貧恷謹嗤2i-1 倖潤泣?i≥1?。乎來嵎辛喇方僥拷追隈屬苧。屬苧待。
來嵎2 匯臣侮業葎k 議屈我峯嶄?恷謹醤嗤2k?1 倖潤泣。
屬苧譜及i 蚊議潤泣方葎xi?1≤i≤k??侮業葎k 議屈我峯議潤泣方葎M?xi 恷謹葎2i-1?夸嗤? 來嵎3 斤噐匯臣掲腎議屈我峯?泌惚匐徨潤泣方葎n0?業方葎2 議潤泣方葎n2?夸嗤:
n0?n2?1。
屬苧譜n 葎屈我峯議潤泣悳方?n1 葎屈我峯嶄業葎1 議潤泣方?夸嗤?
n?n0?n1?n2 ?6-1?
壓屈我峯嶄?茅功潤泣翌?凪噫潤泣脅嗤率匯議匯倖序秘蛍屶。譜B 葎屈我峯嶄議蛍屶方?椎担嗤?
B?n?1 ?6-2?
宸乂蛍屶頁喇業葎1 才業葎2 議潤泣窟竃議?匯倖業葎1 議潤泣窟竃匯倖蛍屶?匯倖業葎2 議潤泣窟竃曾倖蛍屶?侭參嗤?
B?n1?2n2 ?6-3?
忝栽?6-1?、?6-2?、?6-3?塀辛參誼欺?
n0?n2?1
來嵎4 醤嗤n 倖潤泣議頼畠屈我峯議侮業k 葎[log2n]+1。屬苧功象頼畠屈我峯議協吶才來嵎2 辛岑?輝匯臣頼畠屈我峯議侮業葎k、潤泣倖方葎n 扮?嗤
來嵎5 斤噐醤嗤n 倖潤泣議頼畠屈我峯?泌惚梓孚貫貧崛和才貫恣欺嘔議乏會斤屈我峯嶄議侭嗤潤泣貫1 蝕兵乏會園催?夸斤噐販吭議會催葎i 議潤泣?嗤?
?1?泌惚i>1?夸會催葎i 議潤泣議褒牌潤泣議會催葎i/2(“/”燕幣屁茅)?泌惚i?1?夸會催葎i 議潤泣頁功潤泣?涙褒牌潤泣。
?2?泌惚2i≤n?夸會催葎i 議潤泣議恣頃徨潤泣議會催葎2i?泌惚2i>n?夸會催葎i 議潤泣涙恣頃徨。
?3?泌惚2i?1≤n?夸會催葎i 議潤泣議嘔頃徨潤泣議會催葎2i?1?泌惚2i?1>n?夸會催葎i 議潤泣涙嘔頃徨。
緩翌?飛斤屈我峯議功潤泣貫0 蝕兵園催?夸屢哘議i 催潤泣議褒牌潤泣議園催葎?i?1?/2?恣頃徨議園催葎2i?1?嘔頃徨議園催葎2i?2。緩來嵎辛寡喘方僥拷追隈屬苧。屬苧待。