Няколко въпроса за задача за програмиране?

[mitko23]

Здравейте колеги, от скоро започнах отново да навлизам в света на програмирането(въпреки че съм го учил в университета, но после въобще не се занимавах с него и всичко съм забравил ) . Та попаднах на едни записки от изпит преди време, от който ме върнаха заради това, че не успях да изпълня две от три условия поставани ми като задача. Ако може някой да удари едно рамо(макар и след толкова време ) Задачата е следната- За да се съхраняват кеш страници ни трябва кеш сървър. Това може да бъде организирано в дървовидна структура като всяко разклонение от структурата отговаря на ids на кешираните страници Предложете прост начин за съхраняване на кеш страниците в дървовидна структура(tree)? Моят отговор беше следния:

getpage(T, urlpage)
{
if T is null:
T.urlpage = urlpage

if T.urlpage > urlpage:
getpage(T.right, urlpage)

else:
getpage(T.left, urlpage)
}

И на тези два въпроса не можах да отговоря преди, а като гледам и сега, ама срам не срам ще питам

1)Какъв би станало (в най-лошия случай) когато четем страница от структурата която съм написал?

2) Има ли начин да се подобри дървовидната структура(tree) посочена от мен като се промени page-storage алгоритма и как би се изразило в java?

PS. Понеже преподавателя едно време много обичаше да превежда въпросите от англ. на български и ставаше голяма мазало в условията ето ги въпрос 1 и 2 на английски
(a) What is the worst-case complexity of reading a page from this tree?
(b) Is there a way of improving the complexity by changing the page-storage algorithm? If so, propose a way to improve the data-structure and implement in any programming language of your choice.

[vlast_vd]

Първо виждам за объркващо този метод да се казва getpage, по-подходящо име би било insertPage. Но това не е от значение, защото не питаш за него.

1. Ако url-ите са вкарани в сортиран вид, това дърво ще се изроди в линеен списък и тогава времевате сложност ще е линейна в най-лошия случай.
2. Да, алгоритъмът за записване на нов url може да бъде подобрен, при което времевата сложност ще падне до логаритмична в най-лошия случай. Можеш да потърсиш повече информация за балансирани дървета https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree.

[mitko23]

Благодаря ти за отговора колега , това за insertPage не съм се сетил както и за Self-balancing binary search tree. Мерси още веднъж , друго си е като те насочи някой с повече опит.