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

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;

}

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

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ý.

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.