Új hozzászólás Aktív témák
-
modder
aktív tag
válasz
Azazel999
#2000
üzenetére
Az király ha sikerült. Tegnap én sem értettem az algoritmusodat, aztán lejátszottam papíron úgy, hogy a keresett elem (a vágási pont) tetszőleges a fában, aztán rekonstruáltam az új fát, és jó lett.
Viszont nem jöttem rá, hogy beszúrásnál mi a teendő, mert ha ez egy szimpla bináris fa, és keresünk egy nem létező elemet, akkor elérünk az egyik levélbe. akkor melyik lesz a vágási pont? Kipróbáltam több verziót: a vágási pont a létező levél, vagy a vágási pont az új elem, vagy a vágási pont a levél előtti elem, de egyik esetben sem kaptam kiegyensúlyozott fát. Ezt a lépést leírnád?
Amúgy meg rekurzióval tényleg egyszerűbb. az ugye csak egy Depth First Search, ahol minden lépés után vagy B vagy J tömbbe teszed a részfákat, a végén pedig mikor visszatérsz a keresésből építesz egy új fát a B és J elemekből. De általában "hatékonyabb" a nem rekurzív megoldás: erőforráskímélőbb, hiszen nem kell állandóan függvényt hívni.
Amúgy meg erről eszembe jutott, az 1. féléves C nagyházim. Egy logikai kifejezés kiértékelő program tetszőleges logikai kifejezést megadva, épít belőle egy fát (amit ma Abstract Syntax Tree-nek mondanék, mert az jó hangzatos), majd bejárja és közben kiértékeli a kifejezést. Miután működött, három napomba tellett, mire kijavítottam a pointerezést, és a Valgrind végre nem mutatott memória szivárgást
szerk: azt akartam kihozni belőle, hogy jó, hogy meg tudtad oldani egyedül, mert mire kiszeneded magadból a megoldást, sokat megtanulsz
-
Azazel999
csendes tag
válasz
Azazel999
#1996
üzenetére
Nos, erre jutottam, de futtatáskor a vektoromból kifutok a számlálással valamiért:
void Fa::vag(Fa* v_pont){
vector<Fa*> kicsik;
vector<Fa*> nagyok;
Fa *aktualis = this, *kovetkezo;
//fa szétdarabolása
while (aktualis->kulcs != v_pont->kulcs){
if (aktualis->kulcs < v_pont->kulcs){
kicsik.push_back(aktualis);
kovetkezo = aktualis->jobb;
aktualis->jobb->apa = NULL;
aktualis->jobb = NULL;
} else if (aktualis->kulcs > v_pont->kulcs){
nagyok.push_back(aktualis);
kovetkezo = aktualis->bal;
aktualis->bal->apa = NULL;
aktualis->bal = NULL;
}
}
//vágási elem gyrekeinek levágása
if (aktualis->bal != NULL){
kicsik.push_back(aktualis->bal);
kovetkezo = aktualis->jobb;
aktualis->jobb->apa = NULL;
aktualis->jobb = NULL;
} else if (aktualis->jobb != NULL){
nagyok.push_back(aktualis->jobb);
kovetkezo = aktualis->bal;
aktualis->bal->apa = NULL;
aktualis->bal = NULL;
}
//a kisebb- és nagyobb fa felépítése
for(int i = 1; i < kicsik.size(); i++){
kicsik.at(0)->beszur(kicsik.at(i));
}
for(int j = 1; j < nagyok.size(); j++){
nagyok.at(0)->beszur(nagyok.at(j));
}
//a vágási pont gyökérré tétele, a két fa ráakasztása
v_pont->bal = kicsik.at(0);
v_pont->jobb = nagyok.at(0);
v_pont->bal->apa = v_pont;
v_pont->jobb->apa = v_pont;
} -
kingabo
őstag
válasz
Azazel999
#1994
üzenetére
Én ilyet nem tanultam, vagy nem rémlik. De ha ez ekkora művelet igénnyel jár, mint amit leírtál nem is csodálom. Szóval mit értesz önszerveződő bin kerfa alatt?
"Szóval tudom, minek kell történnie, ezt le is írtam."
Ha papíron le tudod játszani, akkor van kész algó. Miért nem írod le és segítünk lekódolni. -
-
kingabo
őstag
válasz
Azazel999
#1988
üzenetére
Ha jól sejtem Te avl fát akarsz implementálni: m. wiki, a. wiki, egyetemi jegyzet ebben, ha a matekos részeket kihagyod, sztem jó le van írva, képekkel. Csak pár pointert kell átállítani a forgatástól függően. Talán próbáld meg papíron, ott elvileg könnyebbnek kell lennie.
-
Azazel999
csendes tag
válasz
Azazel999
#1987
üzenetére
És közben rájöttem, hogy a "szétszedem őket két csoportba és egyenként beszúrom a két fába" ötlet nem jó, mivel ha más a sorrend, nem ugyanazok lesznek a részfák megfelelő részei, mint az eredetiek voltak, mert telejsen újakat épít belőlük. Szóval marad az átláncolás, de hogy a jó életbe lehet azt megcsinálni? Ha Java-ban egyszerűbb, úgy is elmagyarázhatjátok, de C++ az elsődleges célom, mivel abban magamtól is eljutottam idáig.
-
#1978
WonderCSabo
félisten
Azazel999
#1976
WonderCSabo
félisten
válasz
Azazel999
#1976
üzenetére
Nem értem, miért kéne hámoznod? Megfogod a részgát a gyökerénél fogva, és átláncolod. Ez "húzza" magával a többit is, minden alatta lévő elem hozzá van láncolva (már ha jó az implementációd).
Ja és természetesen javában is lehet láncolt adatszerkezeteket csinálni, mivel a java referenciákkal dolgozik...
-
Azazel999
csendes tag
válasz
Azazel999
#1976
üzenetére
Ja, és a kereső metódusban meg kell fordítani a kacsacsőröket, mert különben nem jól dolgozik:
Fa* Fa::keres(int kulcs){
if (this->kulcs == kulcs){
return this;
} else if (this->kulcs > kulcs){
return this->bal->keres(kulcs);
} else {
return this->jobb->keres(kulcs);
}
} -
Azazel999
csendes tag
válasz
Azazel999
#1975
üzenetére
Viszont a vágás megvalósításáról még lövésem sincs. Azt tudom, hogy kettévágom a fát két fává a vágási elem mentén. Az egyik fába kerülnek a nála kisebb elemeket tartalmazó részfák, a másikba a nála nagyobbak. Majd ő lesz az új fa gyökere és a két másik fát hozzácsapjuk bal-. és jobb leszármazottaknak. A hozzácsapással nincs is gond, az tulajdonképpen csak beszúrás, de hogyan hámozhatom ki az összes nála kisebb/nagyobb elemet, hogy aztán fát gyúrjak belőlük? Van erre valami bevált módszer?
Új hozzászólás Aktív témák
● ha kódot szúrsz be, használd a PROGRAMKÓD formázási funkciót!
- 5.1, 7.1 és gamer fejhallgatók
- Linux kezdőknek
- World of Warships
- PlayStation 5
- Star Trek
- Apple iPhone 17 Pro Max – fennsík
- Kezünkben a Xiaomi 17 sorozat telefonjai
- NVIDIA GeForce RTX 4060 / 4070 S/Ti/TiS (AD104/103)
- Milyen asztali (teljes vagy fél-) gépet vegyek?
- Reklámblokkolók topikja
- További aktív témák...
- ! Akció ! - Klipsch R-120SW Mélynyomó / Subwoofer - 1.5 év garanciával
- Lenovo X13 Thinkpad Gen2 WUXGA IPS i5-1145G7 16GB RAM 256GB SSD Intel Iris XE Win11 Pro Garancia
- Bomba ár! HP Probook 440 G10 - i3-1315U I 16GB I 256SSD I 14" FHD I W11 I Cam I Garancia!
- Bomba ár! HP Probook 450 G10 - i3-1315U I 16GB I 256SSD I 15,6" FHD I W11 I Cam I Garancia!
- Bomba ár! HP ProBook 450 G8 - i5-1135G7 I 8GB I 256SSD I HDMI I 15,6" FHD I Cam I W11 I Gar
- Bowers & Wilkins Px7 S2 fejhallgatók (több darab akár, rendelésre)
- Telefon felvásárlás!! iPhone 16/iPhone 16 Plus/iPhone 16 Pro/iPhone 16 Pro Max
- GYÖNYÖRŰ iPhone 13 mini 128GB Blue -1 ÉV GARANCIA - Kártyafüggetlen, MS3293
- Apple TV 4K 2.gen (A2169) 32 GB 6 hónap Garancia Beszámítás Házhozszállítás
- Telefon felvásárlás!! Samsung Galaxy A70/Samsung Galaxy A71/Samsung Galaxy A72
Állásajánlatok
Cég: NetGo.hu Kft.
Város: Gödöllő
Cég: Laptopműhely Bt.
Város: Budapest