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

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.

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.

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.