Ahoj,
dělám implementaci semestrální práce do školy a jako ADT jsem použil červeno-černý strom kvůli velmi dobrým asymptotickým složitostem velikosti ADT O(N), insert algoritmu O(log(N)), delete algoritmu O(log(N)) a search algoritmu, rovněž O(log(N)). Nicméně daná logaritmická složitost search algoritmu, myslím si, platí pouze pro případ, že budu vyhledávat takový datový typ, dle něhož se červeno-černý strom řadí, je to tak?
Vyhledávací funkci mám následovně:
Uzel * R_B_Strom::najdi_uzel(int id) const
{
Uzel * temp = koren_;
while (temp != NULL)
{
if (temp->identifikacniCislo_ == id)
{
return temp;
}
else if (temp->identifikacniCislo_ > id)
{
temp = temp->levyPotomek_;
}
else
{
assert(temp->identifikacniCislo_ < id);
temp = temp->pravyPotomek_;
}
}
return temp;
}
Tedy funguje tak, jak má. Vyhledávám integer a podle integeru (resp. indentifikačního čísla) mám strom seřazený. Chápu to správně, že kdybych chtěl nalézt prvek podle stringu, tedy typ proměnné, podle kterého se strom neřadí, je třeba projít strom lineární, například INORDERem a asymptotická složitost poté bude O(N) namísto O(log(N))?