Tak to samozrejme nemas. Jestli to planujes provozovat en masse a ne selektivne, pak budes mit hodne zajimavej diskuzni klub:)

ISTEVE: to je pravda. já nemám povinnost odpovídat ti na všechny tvoje otázky, řekl bych.

Can we do a Binary search on a linked list?
http://www.coders2020.com/can-we-do-a-binary-search-on-a-linked-list

XCHAOS: Tos mi ale stale neodpovedel na otazku...

Using binary search on a linked list
http://portal.acm.org/citation.cfm?id=101085.101088
the general consensus is that there is no advantage in trying to implement the binary search process on linked lists

ScienceDirect - Information Processing Letters : Binary search networks: A new method for key searching
http://www.sciencedirect.com/science/article/pii/0020019087901992

ok, tak jsem chtěl zkusit překřtít to na "lineární binární mesh", ale to je už taky obsazené:
linear binary mesh - Google Search
http://www.google.com/search?client=ubuntu&channel=fs&q=linear+binary+mesh&ie=utf-8&oe=utf-8

ISTEVE: no snažil jsem se pro datovou strukturu, pro kterou jsem žádný kánonický název nenašel, vymyslet název, který by co nejvíc odpovídal tomu, jak se jmenují vzdáleně podobné datové struktury.

Původně jsem tomu říkal "Binární mesh", když jsme u toho, ale to se taky nelíbilo.

ISTEVE: jestliže toto je "B+ strom" http://en.wikipedia.org/wiki/B%2B_tree - tak z logiky věci nelze [ XCHAOS @ ANSI C/C99 (specifikace), GNU C (gcc, glibc), Tiny C (tcc) a POSIX - ne nutně C++,g++,libstdc++ nebo Win32 API ] pojmenovat jinak, než "binární B+ strom".

je tedy pravda, že jisté odlišnosti proti té wikipedické definici by se u mě našly, takže tomu říkejme třeba "homogení" nebo "minimální" binární B+ strom" - homogení či minimální proto, že se pracuje s jediným typem uzlu, celou dobu - hlavně tomu neříkejme Maruška, ok ? :-)

XCHAOS: Ja vim, co je B+ strom a vim taky, jakej je rozdil mezi B stromem a B+ stromem... ale moje otazka stoji tak jak jsem ji polozil.

ISTEVE: B+ strom, ne B strom.

XCHAOS: A cetls vubec ten paper na B strom, nebo se ti jen ten nazev libil?

XCHAOS: Tak ja vim k cemu to je u red-black. Jen sem cekal od bodu tri (ve kterem by mohl spocivat kriticky detail) neco vic nez "a taky bych si tam mohl pamatovat nejakou extra informaci". Tot vse.

Mozna se to zkus podivat ne jako na linked list co ma nejaky dopredny linky, ale jako na strom co ma nejakou horizontalni linku. Treba ti to pomuze vic.

DAVIDOWITCH: kdybych to přesně věděl, tak vám předložím hotovej kód a budu se vytahovat, jak jsem hrozně dobrej, ne ? :-)

u toho red-black tree to slouží k udržování alespoň přibližné vyváženosti stromu - zabraňují tím prý případům, kdy se binární strom "vyroste" nejhorším možným způsobem (a tedy nezrychlí hledání)

XCHAOS: Hele, ja nejak nevidim zadnej conclusion z toho bodu (3). Mas teda kus spojaku, kterej je obarvenej.. co z toho plyne, nebo k cemu ta barva bude?

XCHAOS: A hlavne v defaultni konfiguraci glibc malloc pouziva mmap az pro bloky od 128k vejs, takze u tech mensich mas smulu bez ohledu na architekturu.

ANT_39: ano, v předchozím jsem úplně zapomněl na 0) existence nějakého klíče, podle které má smysl ty uzly uspořádat.

(pochopitelně, jako obecný kontejner, u kterého nezáleží na pořadí, je to nesmysl - tam stačí pole nebo jednoduchý spojový seznam)

REDGUY: ...a rozhodně jen pro některé architektury, ano. prostě občas ty stránky přeskládat lze, občas ne.

třeba u mě by se to částečně tlouklo s tou "kontextovou správou paměti": ne úplně, pravda, ale je to jeden z důvodů, proč jsem se na to zatím nadšeně nevrhnul.

ISTEVE: je to prostě "spojový seznam + něco navíc". co třeba takhle:

1) všechny uzly (vrcholy grafu) jsou spojené orientovanými hranami tak, že je lze jednoznačně procházet jako nezacyklený, spojový seznam - máme právě jeden "vstupní" uzel a právě jeden "výstupní" uzel (ze které už nevede žádná hrana). těmto "primárním" hranám říkám "next".

2) z každého uzlu (kromě výstupního) může (ale nemusí) vést ješrtě maximálně jedna orientovaná hrana, která vede jinam, než ta primární (kterou jsou pospojované uzly spojového seznamu) a která nikdy nevede do uzlu, který by nebyl součástí toho "podřízeného" spojového seznamu. volitelným sekundárním hranám říkám "seek".

toto je podle mě téměř vyčerpávající definice, ale já se domnívám, že kritický detail by mohl spočívat ve:

3) u uzlů, ze kterých nevede sekundární orientovaná hrana ("seek") máme alternativně ještě možnost jejich další kategorizace (např. "obarvení" - paralela k red-black trees, což je používaná datová struktura) (což se v Céčku implementuje velice snadno tak, že ty seek pointery budou ukazovat na něco, co z definice vůbec nebude smět být přidáno jako prvek toho binárního b+ stromu - triviální je označení hodnotou NULL, další jednoznačně "zakázaná" možnost je "ukazuji sám na sebe", apod. )

ANT_39: viz teď co jsem psal v bodě 3): já se domnívám, že by měl existovat nějaký trik, kterým "vyhandluju" informační entropii za výpočetní výkon :-) jinými slovy - pokud by to bylo jen tak, jak jsem to nakreslil zde - [ XCHAOS @ ANSI C/C99 (specifikace), GNU C (gcc, glibc), Tiny C (tcc) a POSIX - ne nutně C++,g++,libstdc++ nebo Win32 API ] - ale já se domnívám, že trik by mohl spočívat ve využití informační hodnoty těch uzlů, které nemají platný ten "seek" pointer. paralelu vidím ve struktuře http://en.wikipedia.org/wiki/Red-black_tree - kterou jsem sice úplně nepochopil, ale jednak jsou to takové hezké anarchistické barvy :) jednak je tam evidentně nějaký přidaný "prvek samoorganizace"

u mě jsou dva rozdíly: jednak je to binární B+ strom a nejen binární strom, a jednak (z myslím pochopitelných implementačních důvodů) chci obarvovat jen ty uzly, ze kterých nevedou dvě další hrany.

ve skutečnosti: zatím všechny moje pokusy nějak si to představit dost selhaly: ale víceméně si myslím, že by mohly být "obarveny" třeba ty uzly, na kterých nebo za kterými bezprostředně končí nějaká ta "seek" hrana. měl jsem vymyšlených několik takových "pravidel obarvování", ale na všechno jsem po několika pokusech našel nějaký protipříklad.