Vyhledávání stringu nad červeno-černým stromem, který je seřazen podle integeru – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Vyhledávání stringu nad červeno-černým stromem, který je seřazen podle integeru – C / C++ – Fórum – Programujte.comVyhledávání stringu nad červeno-černým stromem, který je seřazen podle integeru – C / C++ – Fórum – Programujte.com

 

ondrej39+1
Věrný člen
29. 12. 2014   #1
-
0
-

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))?

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 74 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý