C++ - BVS - delete – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

C++ - BVS - delete – C / C++ – Fórum – Programujte.comC++ - BVS - delete – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
tomas
~ Anonymní uživatel
510 příspěvků
1. 5. 2009   #1
-
0
-

ahoj,

programuju v C++ BVS vyhledavaci strom a snazim se vytvorit metodu delete(int val) ktera ze stromu odstrani vrchol s hodnotou val.

Strom mam reprezentovany takto:

class BVSStrom {

int value;
BVSStrom * left, * right;
}


V medote delete nejprve najdu pozadovany vrchol, a potom pokud nema zadneho syna, tak jej smazu, tj. rad bych nastavil left/right jeho otce na NULL (a uvolnil pamet).
Zkousel jsem proste delete this;, to ale nefunguje spravne (tj. nenastavi to otci ...). Dale by me napadlo bud vest si z kazdeho syna ukazatel na otce, nebo si predchudce ukladat pri pruchodu metodou delete - ani jedno se mi moc nelibi.

Neslel by nejakym zpusobem vrchol "smazat" primo ze sebe ?

Diky Tom

Nahlásit jako SPAM
IP: 217.197.149.–
Reklama
Reklama
tomas
~ Anonymní uživatel
510 příspěvků
1. 5. 2009   #2
-
0
-

Tak nakonec jsem to udelal tak, ze si v kazdem uzlu pamatuju navic odkaz na predka. Bude se mi to hodit kdyz budu chtit BVS prepsat na AVL strom ...

Tom

Nahlásit jako SPAM
IP: 217.197.149.–
ian0
Stálý člen
2. 5. 2009   #3
-
0
-

zdravim,

pokud řešíš jen obyčejné BVS bez žádného vyvažování, pak delete není problém. Při průchodu stromem si pamatuješ pointer vždy jen na aktuální uzel a na jeho otce, pak jen otci nastvíš příslušného syna na nejlevější uzel pravého podstromu (nebo nejpravější uzel levého podstromu) toho deletovaného uzlu a uzel smažež.

S těma AVL stromama to není tak jednoduché, tam se musí kvůli správnému vyvážení propragovat změna až do kořene. Myslím si, udržovat informace o předkovi v AVL stromu není dobré, protože to bude zbytečně dělat problémy při rozmýšlení převažování. Podle mě je lepší buď vytvořit vlastní zásobník, na který si budeš ukládat cestu od kořene, nebo v podobě rekurze využít ten sytémový.

Nahlásit jako SPAM
IP: 193.86.150.–
-- ian
tmi0
Věrný člen
9. 5. 2009   #4
-
0
-

souhlasim s vyuzitim zasobniku, krome jednodussi implementace se ti navic zmensi se ti velikosti nodu coz ti nejaky ten cache-missik usetri. priklonil bych se k vlastnimu zasobniku, protoze pri dvojrotacich potrebujes sahat o dve urovne nize, coz se v tom systemovem dela blbe.

Nahlásit jako SPAM
IP: 213.226.226.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
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, 57 hostů

Podobná vlákna

BVS - odstraneni uzlu — založil kn0t3k

Delete [] — založil Robo

::delete — založil Koudis

DELETE v MySQL — založil Systém

DELETE komponenty — založil otasimek

Moderátoři diskuze

 

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