Kezdőoldal » Számítástechnika » Programozás » Egy bináris fában hogy lehet...

Egy bináris fában hogy lehet megtalálni a mediánt O (log n) futásidőben?

Figyelt kérdés

Ötletek? Szerintem nem lehet.


n: a csúcsok száma



2020. jan. 2. 09:53
 1/10 anonim ***** válasza:
87%
Ha nem search tree, akkor sehogy.
2020. jan. 2. 09:57
Hasznos számodra ez a válasz?
 2/10 A kérdező kommentje:
Keresőfa* igen, köszi
2020. jan. 2. 10:01
 3/10 anonim ***** válasza:
86%
Elég józan paraszti ésszel átgondolni, ha nem rendezett a fa, akkor minden csúcsot érintened kell, tehát nem lehet O(n)-nél jobb a futásidő.
2020. jan. 2. 10:07
Hasznos számodra ez a válasz?
 4/10 anonim ***** válasza:

Ha keresőfa is akkor se megy alapból olyan futási idővel.

Már az ,hogy nem egy alap tulajdonsága a keresőfának hogy tudja a saját (nem üres) levélcsúcsának darabszámát. Ezt O(n) időbe tudod megszámolni.

Amit kérdezel azt kéne, hogy legfeljebb O(log n) időben tudja saját levélcsúcsának darabszámát, továbbá hogy O(log n) időben meg tudj keresni k.-ik (de legalább azokat a levélcsúcsokat/levélcsúcsot ami a mediánhoz kell)

Triviálisan ez működik, ha nyilvántartod minden elemnek a nagyság szerinti sorszámát, a beszúrás és törlés futási idejének rovására. Az jó kérdés lehet e, hogy ezen is segíteni illetve hogy lehet. Ha minden igaz úgy, hogyha nyilvántartod a részfák méretét a levelek nagyság szerinti sorszáma helyett.

2020. jan. 2. 15:42
Hasznos számodra ez a válasz?
 5/10 A kérdező kommentje:
#4 na, ez tök menő megoldás. Ilyenre gondoltam. Köszi!
2020. jan. 2. 15:47
 6/10 anonim ***** válasza:
:)
2020. jan. 2. 16:00
Hasznos számodra ez a válasz?
 7/10 anonim ***** válasza:

Eszembe jutott még más válaszadók javításképpen: Attól hogy keresőfa az önmagában még nem garantálja azt se hogy a egy kulcs alapján a keresési idő egyáltalán O(log n) lesz.

Például ez egy elfajuló keresőfa : [link]


Lehetne annyira elfajuló is, hogy úgy követik egymást a levelek, hogy kvázi láncolt lista.

Nem simán bináris keresőfa kell hanem önkiegyensúlyozó bináris keresőfa. A legjobb kiegyensúlyozás a törlési és beszórási műveletre nézve O(N) futási idejű, ahhoz hogy ezek is O (log n) futási idejűek legyenek ezekre vannak a piros fekete fák és az AVL fák.

2020. jan. 2. 17:53
Hasznos számodra ez a válasz?
 8/10 anonim ***** válasza:
Senki nem mondta, hogy sima bináris keresőfa kell. Annyit mondtunk, hogy ha nem keresőfáról van szó, akkor nem lehet.
2020. jan. 2. 18:07
Hasznos számodra ez a válasz?
 9/10 anonim ***** válasza:
Igen, de nem az volt a kérdés, hogy milyen bináris fában nem lehet. A nem lehet-re se volt kielégítő a válasz, mert létezik olyan keresőfa melyben szintén nem lehet, az előbbiekből következően belátható. Valaki írta, hogy belátható ha nem rendezett akkor nem lehet, de arról se volt szó, ha rendezett az szükséges de nem elegendő feltétel.
2020. jan. 2. 18:21
Hasznos számodra ez a válasz?
 10/10 anonim ***** válasza:

Azért ilyet ne állíts:

"Annyit mondtunk, hogy ha nem keresőfáról van szó, akkor nem lehet."


Mert egyszerűen nem igaz.

Pl ha úgy definiáljuk a fát, hogy a medián minden esetben a gyökérelem vagy pl a legbaloldali levél és a többi elem véletlenszerűen van, akkor ebben a típusú fában meg lehet találni O(1) ill O(log n) futásidőben, mégsem keresőfa... Más kérdés, hogy ez a fa semmire nem jó és marha nehéz új elemet hozzáadni vagy elvenni.


Illetve biztosan ki lehet találni más módokat ami talán még hasznos is valamire és mégsem keresőfa.

2020. jan. 4. 08:44
Hasznos számodra ez a válasz?

Kapcsolódó kérdések:





Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!