abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 11:11 | Pozvánky

Dnes od 16:00 do 19:15 a zítra od 9:00 do 15:00 lze virtuálně navštívit festival novodobých kutilů Maker Faire Prague Online 2020.

Ladislav Hagara | Komentářů: 0
včera 22:22 | Zajímavý projekt

S pomocí 3D tiskárny vyrobitelná klávesnice Katy K80CS (Deskthority, Geekhack) inspirovaná Kinesis Advantage je nyní open hardware – včetně souborů STL nově pod licencí Creative Commons BY-SA. Firmware byl dostupný již dříve. Jedná se o alternativu k populárnímu projektu Dactyl s řadou forků včetně varianty Dactyl-Manuform (viz též galerii, kterou spravuje Xah Lee).

Fluttershy, yay! | Komentářů: 9
včera 22:11 | Nová verze

Android Studio (Wikipedie), tj. oficiální integrované vývojové prostředí pro vývoj aplikací pro mobilní operační systém Android, bylo vydáno v nové stabilní verzi 4.0. Přehled novinek i s náhledy v oficiálním oznámení a také na YouTube.

Ladislav Hagara | Komentářů: 0
včera 15:33 | Nová verze

Byla vydána verze 1.14 systému pro správu a verzování zdrojových kódů Apache Subversion (Wikipedie). Jedná se o LTS verzi. Přehled novinek v poznámkách k vydání.

Ladislav Hagara | Komentářů: 5
včera 14:22 | IT novinky

V červnu loňského roku bylo představeno Raspberry Pi 4 s 1 GB, 2 GB a 4 GB RAM. Dnes přibyla varianta s 8 GB RAM za 75 dolarů. Současně bylo oznámeno přejmenování Raspbianu na Raspberry Pi OS. K dispozici je beta verze 64bitové varianty. Minulý týden byla oznámena beta verze firmwaru umožňujícího bootování Raspberry Pi 4 z USB místo z SD karty.

Ladislav Hagara | Komentářů: 9
včera 07:00 | Zajímavý článek

Portál Stack Overflow po roce opět vyzpovídal své uživatele, jedná se především o vývojáře softwaru, a zveřejnil detailní výsledky průzkumu. Průzkumu se letos zúčastnilo téměř 65 tisíc vývojářů. Jejich nejpopulárnější i nejmilovanější platformou zůstává Linux.

Ladislav Hagara | Komentářů: 11
včera 00:33 | Nová verze

Po deseti měsících vývoje byla vydána nová verze 3.10 svobodného alternativního webového prohlížeče NetSurf (Wikipedie). Přehled změn v cgitu.

Ladislav Hagara | Komentářů: 7
27.5. 23:55 | Nová verze

Oznámení o vydání nové verze 8.3 sady aplikací pro SSH komunikaci OpenSSH obsahuje upozornění, že vzhledem v lednu publikovanému útoku na SHA-1 bude v blízké budoucnosti v OpenSSH ve výchozím stavu zakázáno použití algoritmu ssh-rsa. Zda bude komunikace se serverem i po tomto zákazu fungovat, lze vyzkoušet pomocí příkazu "ssh -oHostKeyAlgorithms=-ssh-rsa user@host".

Ladislav Hagara | Komentářů: 4
26.5. 17:11 | Nová verze

Byla vydána nová stabilní verze 5.15 toolkitu Qt. Přehled novinek na wiki stránce. Jedná se o LTS verzi. V důsledku nedávných změn je ale dlouhodobá podpora pouze pro držitele komerční licence.

Ladislav Hagara | Komentářů: 22
26.5. 11:11 | Komunita

Libre Graphics Meeting 2020, tj. konference a setkání vývojářů a uživatelů svobodných grafických softwarů, proběhne online od středy 27. května do pátku 29. května. Na programu jsou zajímavé přednášky i tutoriály. Sledovat je lze zdarma a bez registrace.

Ladislav Hagara | Komentářů: 2
Kdy přecházíte na nové vydání distribuce/OS?
 (14%)
 (13%)
 (22%)
 (7%)
 (3%)
 (41%)
Celkem 348 hlasů
 Komentářů: 0
Rozcestník

Červeno-čierne stromy

23.3.2010 23:41 | Přečteno: 3953×

V poslednom čase programujem dosť vecí do školy a tak som si povedal, že je škoda to niekam nezavesiť, nech majú z toho úžitok aj ďalšie generácie. Ako prvé budú červeno-čierne stromy...

V zimnom semestri som mal predmet Algoritmy a dátové štruktúry a ako nepovinný projekt si náš tím vybral červeno-čierne stromy, ktoré sa akosi ani nevyučovali, takže to bol trošku výber mimo rámec, no nejako sme to zvládli. Ale o čo vlastne išlo? Mali sme naprogramovať danú dátovú štruktúru, ktorá mala spĺňať nasledovné:

Okrem vymazávania a krokovania sú implementované všetky veci zo zoznamu. Dokonca v kóde sa nachádza aj vymazávanie, avšak nie v použiteľnom stave. Viem, že nepoužitý kód nemá v zdrojáku čo robiť, avšak nechám ho tam, nech tam hnije. ;) Ou, skoro som zabudol - najhlavnejšou podmienkou bolo, aby sme to naprogramovali v Lazaruse, takže to bolo celkom obmedzujúce, no dalo sa - veď posúďte sami:

Červeno-čierne stromy

Keďže som autorom všetkého kódu, tak mi nerobí problém vypustiť to pod GPLv3, čiže užívajte v zdraví - balík na stiahnutie je v diskusí.

       

Hodnocení: 100 %

        špatnédobré        

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

Milan Lajtoš avatar 23.3.2010 23:42 Milan Lajtoš | skóre: 22 | blog: /blog/babraq
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Příloha:
viď. príloha
“Every great achievement was once considered impossible.”
Saljack avatar 24.3.2010 00:03 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Hele na jakou školu chodíš? Proč bylo podmínkou Lazarus? To ještě nějací zabedněnci pořád vyučují packala?
Sex, Drugs & Rock´n Roll.
24.3.2010 00:18 Ondřej Profant | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
No on se vyučuje často a pro vysvětlení základů procedurálního programování člověku, který nikdy neprogramoval je dobrý (velmi dobře čitelný). Čili na ten první semestr. Navíc je tak "primitivní", že každý cvičí ho může znát opravdu hodně dobře (zkus najít dost cvičících, co umí hodně dobře .NET, či Javu).

Třeba na MFF se taky první semestr učí, doporučuji přečíst: Jak učit programování?
Dent avatar 24.3.2010 09:57 Dent | skóre: 21 | blog: Standovo | České Budějovice
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
To o té dobré čitelnosti Pascalu jsem nikdy nepochopil. V čem je dobře čitelný? Mě osobně ta bezzávorková begin-end syntax přijde krajně nepřehledná. Pokud je něco uvozeno závorkou, vím hned, že tam něco začíná, takže i při zběžném prolétávání kódem tak nějak vím, jak je strukturován. Begin a end jsou klasická slova, takže mi v kódu dost splývala se zbytkem a bylo to pro mě dost nepřehledné (a na odsazení nezáleželo). Fuj, ještě že už je to za mnou. { a } rulezzz :))
24.3.2010 10:20 Robo
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
ja mam naopak radsej BEGIN ... END (PL/SQL); (IF .. FI v shelly a pod.); to, kde nieco zacina a konci robim odsadzovanim textu vo vnutri daneho bloku, takze mi to pride potom prehladnejsie; zatvorky mi pridu naopak neprehladne, ak su tam viac ako jedny, zacinam sa v tom stracat a tazko sa rozlisuje {} od ()
Dent avatar 24.3.2010 10:41 Dent | skóre: 21 | blog: Standovo | České Budějovice
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Asi je to o zvyku. Řekl bych, že každý považuje za jazyk vhodný pro začátečníky ten, na kterém sám začínal.
Milan Lajtoš avatar 24.3.2010 11:07 Milan Lajtoš | skóre: 22 | blog: /blog/babraq
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Musím nesúhlasiť. Mojím prvým programovacím jazykom bol Pascal a myslím si, že Python by bol pre začiatočníkov vhodnejší.
“Every great achievement was once considered impossible.”
24.3.2010 19:46 rajcze | skóre: 6 | blog: rajcze | kus od Brna
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Musim nesouhlasit, Python je sice muj nejmilejsi jazyk, ale na vyuku programovani je IMHO stale nejlepsi Pascal. I kdyz pominu takove triviality jako nepritomnost "bezneho" for cyklu, nebo switch-case, tak Python porad dela pomerne neprijemnej maglajz treba s mutable/immutable objekty. Co se didaktickeho hlediska pro _nauceni se programovani_ tyka (tj. kdyz ty lidi potrebujes naucit _myslet_ ne neco nabastlit a ono to mozna pojede), neznam zatim nic lepsiho.

Ano, Pascal ma samozrejme svoje nevyhody (fuj objektovemu programovani v turbo pascalu), ale vylozene neprijemny je jen u veci, ktere stejne ucis na takove urovni (v idealnim pripade) kdy je tem lidem jedno, jaka je syntaxe toho konkretniho jazyka, ve kterem pisou, ale je dulezite, aby pochopili princip.
Rules of Optimization: Rule 1: Don't do it. Rule 2 (for experts only): Don't do it yet.
Milan Lajtoš avatar 24.3.2010 23:03 Milan Lajtoš | skóre: 22 | blog: /blog/babraq
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Aby sme mali jasno - pod pojmom "začiatočník" myslím človeka, ktorý naozaj nikdy nevidel žiaden programovací jazyk a absolútne nemá žiadne základy algoritmizácie.

Mne príde Python vhodný vďaka tomu, že je dynamicky typový. Človeku sa premenná vysvetlí ako krabička, do ktorej môže niečo dať. A keď mu poviem, že tam môže dať hocičo, tak je to super, pretože mu nemusím vysvetľovať aké dátové typy tam môže dávať a vôbec že nejaké dátové typy sú. (Neskôr sa k tomu aj tak dostanem, no...)

Na druhej strane by mal programovací jazyk "rásť" s človekom. Ako sa postupne učí nové veci, tak to všetko by mal programovací jazyk zvládať. V Pythone, či Jave sa nikdy nenaučím o smerníkoch, či v C++ nikdy o Lambda výrazoch (v C++0x že vraj budú).

V konečnom dôsledku, programovací jazyk má byť len nástroj na odskúšanie si svojho myslenia, teda algoritmu, nie bastliť - ako si trefne napísal.
“Every great achievement was once considered impossible.”
24.3.2010 23:59 rajcze | skóre: 6 | blog: rajcze | kus od Brna
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Na pojmu zacatecnik se, myslim, naprosto shodneme :)

Jasne, dynamicke typy a silna typova kontrola jsou svym zpusobem fajn, ale muze to byt dvojsecna zbran - ono kdyz ti uz prekladas rekne, ze scitat cislo s retezcem je kravovina, tak to IMHO taky trochu dopostrci to mysleni smerem "jak to vlastne funguje, ze to nejde" mozna spis, nez kdyz jednou nahodou zadas spatnej vstup a vybleje to na tebe vyjimku o nekompatibilite typu.

Je pravda, ze co se "rustu s clovekem" tyka, je python hodne silny (rozhodne si netroufam tvrdit, ze skvele zvladam alespon tretinu jeho skutecnych moznosti, a ze v nem delam peknych par let).

On problem "prvniho jazyka" je asi nerozhodnutelny, jedine, co vim jiste, je, ze C neni ten nejlepsi prvni jazyk :) Doucuju ted jednu slecnu (prvak gymplu) programovani - tedy snazim se ji naucit myslet - a ta si teda Pascal ve srovanani s Cckem (ve kterem zacinaji ve skole) pochvaluje. Premyslel sem o Pythonu, ale tam me odradily fakt predevsim mutable/imutable objekty, takze nemuzes smysluplne popsat predavani parametru hodnotou/odkazem, protoze v pythonu se sice _vzdy_ predava odkazem, ale holt immutable objekt nezmenis a libovolna operace nad nim vytvori novou instanci, takze se to tvari jako predane hodnotou. A pak na Pythonu vysvetli reference/dereference v Ccku...
Rules of Optimization: Rule 1: Don't do it. Rule 2 (for experts only): Don't do it yet.
Saljack avatar 25.3.2010 09:29 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
A co si třeba na tom Pascalu pochvaluje a na C nadává? Mě by celkem zajímali takové pohledy člověka co začíná já z mého pohledu bych se nejraději zezačátku vyhnul Pascalu velkým obloukem.
Sex, Drugs & Rock´n Roll.
25.3.2010 09:38 Michal Vyskočil | skóre: 60 | blog: miblog | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Naopak, Pascal (alespoň ten Turbo) je něco jako těžko na cvičišti, lehko na bojišti ;-) Na druhou stranu unit crt a hlavně turbo vision - to byla věc, to se s (n)curses nedá srovnat.
When your hammer is C++, everything begins to look like a thumb.
25.3.2010 09:59 rajcze | skóre: 6 | blog: rajcze | kus od Brna
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Asi ti to bude znit divne, ale syntaxe Pascalu ji prijde primocarejsi a min krypticka nez Ccka. Mimo jine taky kompilator Pascalu negeneruje tak otresny chybove hlasky (kolikrat by ses az divil, co dokaze vyplodit v Ccku zapomenutej strednik...).

Me by zas zajimalo, proc by ses chtel pascalu na zacatku vyhybat? Ja se klidne priznam k tomu, ze kdyz nas na gymplu nutili programovat v Pascalu, tak to byla tezka otrava, predevsim pro tech par lidi, co umeli programovat a Pascal otravoval svou ukecanou sytaxi: "Proc mam ku*va psat a = a + 1, kdyz a++ je tak krasne...", a posleze i tou nejsilenejsi implementaci OOP ever (na druhou stranu, napsal jsem v tom objektovou GUI knihovnu pro DOS, takze proc ne...).

Ale jak porad opakuju, pokud je cilem naucit se myslet, je Pascal fajn, protoze zbytecne nekomplikuje bezne cinnosti, a v mnoha pripadech je syntakticka ukecanost vykoupena nazornosti kodu (aneb function/procedure vs. [typ]/void - ano je to to stejne, ale to prvni je nazornejsi). Ve chvili, kdy te zacne pascal svazovat, tak si pravdepodobne na urovni, kdy uz neco jako syntaxi neresis (ukaz mi jazyk jehoz sytaxi se nejde naucit za maximalne pul dne), protoze te zajimaji funkcni vlastnosti jazyka.
Rules of Optimization: Rule 1: Don't do it. Rule 2 (for experts only): Don't do it yet.
Saljack avatar 25.3.2010 10:42 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Právě kvůli té v celku nelogické syntaxi a hlavně deklarování proměnných, polí atp. to je podle mě v Pascalu to co prostě nepřekousnu. Prostě se v té syntaxi vůbec nedokážu orientovat protože begin a end na první pohled splívají s ostatním kódem. Dále mi přijde jako naprostá blbost používat pro přiřazení := a pro porovnání = to je pro mě naprosto nelogická věc. Objektově bych v tom po zkušenostech ve škole nikdy nic nedělal, to bych raději neprogramoval už nic, protože člověk co to tam implementoval to neměl v hlavě asi v pořádku. Ale co když někomu přijde syntaxe pěkná tak je to jeho věc. Stejně asi holčina dál s programováním nepočítá.
Sex, Drugs & Rock´n Roll.
25.3.2010 11:29 rajcze | skóre: 6 | blog: rajcze | kus od Brna
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Ad nelogicka syntaxe - zalezi _proc_ je to pro tebe *nelogicke* - pokud je to pro to, ze "vsude jinde se prirazuje = a porovnava ==" tak je to otazka zvyku, ne logiky.

Co ti prijde nelogickeho na deklaracich v Pascalu, me osobne tam nic nerusi. Jasne, nemuzes si vytvorit promennou jen pro jeden blok kodu, aniz bys ten blok kodu vystrcil do procedury/funkce, ale uprimne, jak casto potrebujes neco takoveho delat?

Nesnadne orientovani se v kodu - jasne, muzu souhlasit s tim, ze pokud nemas zvyraznovani syntaxe, muze ti pripadat begin/end vice splyvajici, nez {}.

Na objektovym programovani v turbo pascalu je bohuzel videt, ze je tam dobastleny az post mortem. Na druhou stranu ObjectPascal (tj. Delphi) je naprosto v pohode.

Ja osobne bych v soucasnosti taky v Pascalu nechtel programovat, ale ne proto, ze bych ho nejak nenavidel (tim sem si prosel na gymplu :-D). Pascalu pro me potreby chybi siroka zakladna knihoven, kterou mi muj oblibeny Python poskytuje. Je ale potreba si uvedomit rozdil mezi jazykem urcenym pro _vyuku programovani_ (tj. mysleni) a jazykem primarne urcenym pro realne pouziti v praxi.
Rules of Optimization: Rule 1: Don't do it. Rule 2 (for experts only): Don't do it yet.
mkoubik avatar 25.3.2010 13:16 mkoubik | skóre: 5 | blog: lorem_ipsum | Praha 8 - Bohnice
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Jasne, nemuzes si vytvorit promennou jen pro jeden blok kodu, aniz bys ten blok kodu vystrcil do procedury/funkce, ale uprimne, jak casto potrebujes neco takoveho delat?
V každém for-cyklu? Ono for (int i=0;i<length;i++) je o trochu menší prasárna než int i; for (i=0;i<length;i++), ale nevim jak se to dělá v pascalu - neviděl jsem ho od maturity.
25.3.2010 17:11 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Červeno-čierne stromy

Dost praktické to může být třeba i v definici makra, např.

#define SYSTEM_ERROR(x) { \
  std::ostringstream errmsg; \
  errmsg << x; \
  throw system_error(errmsg.str()); \
}
25.3.2010 19:25 rajcze | skóre: 6 | blog: rajcze | kus od Brna
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
To bysme si jeste meli ujasnit, jaky standard Ccka berem v uvahu ;-) (ne, dobre, tohle bylo jen zlovolne rypnuti, chapu tvuj priklad). Na druhou stranu, proc ti prijde lepsi deklarovat a definovat ridici promennou cyklu v hlavicce cyklu, nez vyrobit si ji "na zacatku" (u vsech ostatnich deklaraci promennych)?
Rules of Optimization: Rule 1: Don't do it. Rule 2 (for experts only): Don't do it yet.
25.3.2010 19:53 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Červeno-čierne stromy

Je to stylově čistší v tom, že je tím jasně deklarováno, že proměnná je lokální pro daný cyklus a pokud se někde později vyskytne stejnojmenná proměnná, nemá s ní naprosto nic společného. Někdy to třeba může pomoci odhalit zapomenutou inicializaci, kterou by její nechtěná inicializace předchozím for cyklem zamaskovala.

Za sebe můžu říct, že postupem času mi začala filosofie "deklarovat až když je potřeba a jen tam, kde je potřeba" být trochu bližší než původní "všechno se nadeklaruje na začátku" a jsem docela rád, že C99 tuhle možnost z C++ převzalo.

25.3.2010 17:05 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Dále mi přijde jako naprostá blbost používat pro přiřazení := a pro porovnání = to je pro mě naprosto nelogická věc.

IMHO je to dost logické, ale nepříliš praktické. Dokonce bych řekl, že takové detaily dobře ilustrují rozdíl mezi Wirthovým a K&R přístupem: Kernighan a Ritchie ve své knize dokonce uvádějí, že když se rozhodovali, udělali si na nějakém vzorku svých programů statistiku a zjistili, že přiřazení je podstatně víc než porovnání na rovnost. Proto zvolili jednodušší symbol pro přiřazení. Naopak Wirth se podle všeho rozhodoval spíš podle logiky a přirozenosti. Takových příkladů se dá najít víc - např. nikoho, kdo se aspoň na chvíli zamyslel nad praktickou stránkou věci, by nemohlo napadnout dát logickým operátorům vyšší prioritu než porovnání; Wirth to očividně neudělal, takže se každý test, zda hodnota leží v intervalu, musí závorkovat.

Saljack avatar 25.3.2010 19:03 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
No právě z toho důvodu, že přiřazuješ víc než porovnáváš mi to příjde nelogické.
Sex, Drugs & Rock´n Roll.
25.3.2010 19:59 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Z hlediska logiky "uděláme to tak, aby to bylo praktické" ano. Ale měl jsem na mysli trochu jinou logiku. Když člověku nezatíženému programováním vysvětlím, co je to proměnná, ukážu mu nápis "a = 3" a zeptám se ho, jak by si ho vyložil, většina ho IMHO bude považovat za porovnání, ne za přiřazení. Pro přiřazení se spíš nabízí něco jako "a ← 3" nebo ještě spíš "3 → a". Dokonce naopak řada matematiků převzala pascalové "a := 3" a používá ho pro "položme a rovno třem".
Saljack avatar 25.3.2010 20:38 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Ono mezi námi tomu kdo se učí programovat je celkem u p..., že = je přiřazení pro ně je to to samé jako a se rovná 3, tudíž je zde to rovná se správně ;-).
Sex, Drugs & Rock´n Roll.
26.3.2010 07:22 Vskutečnosti Saýc | skóre: 7
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
No jasne. V matice kde se fakt prirazuje (takovy eukleiduv algoritmus, atd) taky najdes :=, a = je znak normalni rovnosti.
25.3.2010 11:03 Kvakor
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Ano, u "prvního jazyka" je dilema, jestli je lepší mít první jazyk vysokoúrovňový nebo spíš nízkoúrovňový. V tom prvním je výhoda, že se při jejich použití nemusí řešit žádné nízkoúrovňové problémy, ale na mnohá proč musíte odpovídat stylem "Protože bagr".

To u nízkoúrovňových jazyků není problém, tam se to dá vysvětlit přes samotné fungování počítače (jako např. rozdíl předávání hodnoutou vůči předávání odkazem), ale za cenu všech nevýhod nízkoúrovňového přístupu, kdy jazyk podporuje jen nutné minimum a zbytek si musíte dodělat sami, plus problémy s laděním, hlavně dynamických chyb.

Jako jediné rozumné řešení mi zatím vychází začít sice s vysokoúrovňovým jazykem, ale přidat nějaký nízkoúrovňový tak brzo, jak je to jen možné, plus alespoň základní vysvětlení funkce počítače. V opačném případě na konci vyleze buď programátor, který bude používat metodu "kanón na vrabce" a páchat pomalá a paměťově nenažraná monstra, nebo naopak bude mít tendenci kopat Panamský průplav polévkovou lžící, protože nebude znát vhodnější nástroje.

Pascal mi z toho vychází jako pokus smrsknou tyto dva kroky do jednoho - jazyk, který je sice relativně nízkoúrovňový, ale většina potenciálně nebezpečných konstrukcí je zakázána (alespoň ne ve stadnardní verzi). Jsou tu i vlastnosti z vyšších jazyků, kde se překladač sám postará o nízkoúrovňové záležitosti (např. procedury Write/WriteLn a jejich magické "automatické" parametry), ale je jich relativně málo.

Jako jazyk "sám o sobě" není špatný, pokud se použije pro výuku neprogramátorů, ale v opačném případě je tu prbklém právě v té "kočkopsovitosti" - pro ty, co pak budou programovat v něčem jiném (což budou téměř určitě tak jako tak muset), to bude znamenat nutnost odnaučit se zbytečně mnoho věcí.

Je to jako učit se jezdit na tříkolce - je bezpečná a na první pohled má to nejlepší z obou světů, ale budoucí (moto)cyklisti se na ní nenaučí držet rovnováhu a pro automobilisty je to zas příliš podobné kolu.
25.3.2010 11:12 rajcze | skóre: 6 | blog: rajcze | kus od Brna
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Nemuzu nesouhlasit :) Jen mi prijde, ze ta "kockopsovitost" neni zas tak kriticka. Na druhou stranu je otazkou, jestli to muzu objektivne posoudit - ja sem se zacal ucit programovani v SGP Baltazar, ktery me naucil myslet a Pascal na gymplu ve me IMHO nezanechal pocit, ze bych se musel neco odnaucovat - jenze jak rikam, pro me jazyk neni vic nez syntakticky cukr, ktery vice nebo mene usnadnuje konkretni vyjadreni abstraktnich myslenek...
Rules of Optimization: Rule 1: Don't do it. Rule 2 (for experts only): Don't do it yet.
25.3.2010 09:31 Michal Vyskočil | skóre: 60 | blog: miblog | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
V Pythone, či Jave sa nikdy nenaučím o smerníkoch, či v C++ nikdy o Lambda výrazoch (v C++0x že vraj budú).
No vzhledem k tomu, že drtivá většina výuky C směrníky používá ve smyslu obyčejné reference někam, tak si troufám říct, že se o nich člověk nic moc nenaučí ani v C.

BTW: Java RealTime Specification umožňuje přímý přístup k paměti ;-).
When your hammer is C++, everything begins to look like a thumb.
Saljack avatar 25.3.2010 09:40 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Ale proč přistupovat v Jave přímo k paměti? Nejen, že je to "nebezpečné" ale Java ani tak navrhnuta není. Od tohoto jsou právě jiné jazyky. Já si stejně myslím čím míň se do toho člověk sere tím míň může posrat ;-).
Sex, Drugs & Rock´n Roll.
25.3.2010 14:20 Michal Vyskočil | skóre: 60 | blog: miblog | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Tak taková komunikace s HW se bez přímého přístupu do paměti neobejde a RTS umožňuje psát i ovladače pro zařízení v Javě. Tuším, že J2ME má něco podobného.

Ale hlavně to ilustruje, jak jsou proklamace typu V Pythone, či Jave sa nikdy nenaučím o smerníkoch zavádějící. Nejenže směrníky jsou při troše dobré vůle i v té Javě, tak především z prakticky žádné výuky jazyka C se nedostaneme nad to, co by reference z ostatních jazyků nezvládaly taky.
When your hammer is C++, everything begins to look like a thumb.
25.3.2010 12:36 trekker.dk | skóre: 71
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Mě osobně ta bezzávorková begin-end syntax přijde krajně nepřehledná.
Naprosto jasně: begin znamená začátek, end znamená konec. Na první pohled je z toho zjevné, co to má znamenat.

Závorka je jenom obrázek, jehož význam si musíš domyslet.
Begin a end jsou klasická slova, takže mi v kódu dost splývala se zbytkem a bylo to pro mě dost nepřehledné (a na odsazení nezáleželo).
Od toho existují editory se zvýrazňováním syntaxe (nebo přesněji existují editory, které zvýrazňovat syntaxi neumí, i když teď mě žádný nenapadá)
Quando omni flunkus moritati
Saljack avatar 24.3.2010 11:03 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Tenhle argument pořád nechápu. Pascal je podle mě má nejhorší syntaxi ze všech jazyků co znám. Myslím si, že pascal opravdu ani ve výuce nemá místo natož v "pořádném" (teď se zase strhne flame). Ale hlavně si myslím aspoň u nás na střední to tak bylo, že se v pascalu všichni plácali. Nevidím důvod, proč nyní již od začátku nezačít s nějakým objektově orientovaným jazykem (kor na vysoké škole). Přitom je tolik jazyků, které jsou 100x vhodnější pro začátečníky např. C nebo Python. Hlavně Python se mi jeví jako nejlepší volba pro začátečníka. To, že se tvrdilo, že Pascal je vhodný pro začátečníka před 20 lety, za 1. již dnes naprosto neplatí a je to hrozný blábol a za 2. už v té době to byl blábol protože C mi příjde daleko přívětivější a jednoduší na pochopení než Pascal.
Sex, Drugs & Rock´n Roll.
24.3.2010 13:46 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Červeno-čierne stromy

Nevidím důvod, proč nyní již od začátku nezačít s nějakým objektově orientovaným jazykem

Nevidím důvod, proč začínat s objektově orientovaným jazykem

Pascal je podle mě má nejhorší syntaxi ze všech jazyků co znám

Ale většina knih i článků o algoritmizaci používá velice podobnou syntaxi.

Osobně si myslím, že pro začátečníka je důležitá jednoduchost (a logičnost) syntaxe a sémantiky.

Saljack avatar 24.3.2010 13:58 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Proč začínat s objektově orientovaným jazykem? Třeba proto, že skoro všechno je napsáno za pomocí objektově orientovaných jazyků nebo při pochopení principu to dost usnadňuje práci a bez znalosti objektového programování se nikam nehnete.
Většina knih a článků se pouze tváří jako že jsou o algoritmizaci ve skutečnosti jsou to pouze učebnice určitého jazyku. Logičnost syntaxe u Pascalu v porovnání s třeba C nebo Pythonem snad nemá ani cenu komentovat.
Sex, Drugs & Rock´n Roll.
24.3.2010 14:33 Vskutečnosti Saýc | skóre: 7
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Neucit lidi programovat objektove od zacatku ma svoje vyhody 1) je mensi sance ze budou produkovat priserny bloatware 2) objektove programovani je pro spoustu problemu (dost mozna vsechny krom GUI) slepa ulicka 3) u jednoduchych jazyku se snadno uci algoritmy, protoze muzu vyzkouset jak pracuji

Zalezi pochopitelne na tom, koho chcete vyprodukovat, jaky druh programatora. Namezdny busic javy nebo php jsou neco jineho nez nekdo kdo ma programovat vnitrky operacnich systemu nebo AI, zejo.

Pokud jde o algoritmizaci, zase, nizsi jazyky jsou pro tyhle ucely lepsi pomucka. Pochoptelne ze "webovy inzenyr" nepotrebuje vedet jak funguje ten rb strom, kdyz ma v php asociativni pole ktere ty rb stromy samo obsahuje (pokud si dobre vzpominam. mozna to jsou jiny stromy), nebo jak funguje dijkstra. Ale nekdo taky pise PHP nebo idos, zejo.

Tomu o tech knizkach moc neverim, vetsina knizek je budto "naucte se programovat v pythonu" (tedy "zaklady programovani + zaklady pythonu"), design patterny, kecy okolo (coz muze byt snadno nejlepsi literatura kolem, jako "art of unix programming" a podobne), a nebo drsna teorie, kterou snad dneska ani nikdo necte :)
Saljack avatar 24.3.2010 15:09 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Objektové programování se dá využít skoro všude a u psaní různých věcí, které budou dále použity hlavně. Umělá inteligence je úplně něco jiného. Není totiž problém to pochopit, ale najít někoho kdo vám to vysvětlí a úplně nejhorší příklad na vysvětlování je ten klasický s kružnicí a bodem z toho to snad nikdo nikdy nepochopil a stejně to profesoři znovu a znovu vykládají na tomhle příkladu. To s těma knížkami jsem myslel přesně jak jsi napsal ty. Hlavně nechápu proč třeba u nás na FEL je předmět algoritmizace, když je to normálně základy javy.
Ještě bych dodal, že nechápu proč se na FELu vyučuje jako první jazyk Java, který je pro tento účel naprosto na nic, prostě by se mělo učit C a C++ a až potom Java.
Sex, Drugs & Rock´n Roll.
24.3.2010 15:54 Vskutečnosti Saýc | skóre: 7
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Objektove programovani ale neni vselek, a spousta kusu software o kterych se da rict ze nemaji konkurenci nemaji s objektovym pristupem mnoho spolecneho, takove openssl, apache, vnitrek linuxu, klasicke unixove nastroje a tak dal.

U FELu a jinych programovacich kurzu (kursu? nekdo me kdyztak opravte) jde o jinou vec, ony to jsou fakt naproste zaklady, a pokud uz vis co je cyklus, jak funguji podminky, co je to datovy typ a jak vypada spojovy seznam (pokud si tu Algoritmizaci pamatuju spravne :) ), tak ti to musi nutne pripadat jako zaklady javy, ale ten predmet je fakt urceny pro lidi kteri nevi co je cyklus.

A pro tyhle ucely se libovolny (imperativni, atd) jazyk hodi skoro stejne, a rozhoduji takove veci jako jak snadno se da dostat k vyvojovym nastrojum a tak, a nakolik muze byt pro nekoho zvykleho na unix s cc(1) vzdy na dosah ruky sokujici, pro Windows to s vyvojovymi nastroji neni tak zhave. Vyvojovych nastroju pro javu je pritom dost, a daji se provozovat na kdecem.

Ale pro tohle by python mozna byl lepsi, to je fakt. U predmetu jako DSA (na felu) uz bych si jisty nebyl.
25.3.2010 12:37 trekker.dk | skóre: 71
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
kterych se da rict ze nemaji konkurenci nemaji s objektovym pristupem mnoho spolecneho, takove openssl, apache, vnitrek linuxu, klasicke unixove nastroje a tak dal.
Vnitřek Linuxu je hodně objektově orientovaný. Jenom na to nepoužívá objektový jazyk
Quando omni flunkus moritati
mkoubik avatar 24.3.2010 16:16 mkoubik | skóre: 5 | blog: lorem_ipsum | Praha 8 - Bohnice
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Jaký příklad s kružnicí a bodem? Asi jsem byl systémem vzdělávání zanedbán. Jinak algoritmizace je totální výsměch. Polovina lidí tam nikdy neprogramovala a je cílem je za 13 cvičení naučit vytvářet projekt v NetBeans, opisovat kód z tabule a spouštět kompilaci. Zbytek programovat umí a nudí se tam u výkladu cyklů.

Nerozhodnutelnost problému výuky objektového vs. procedurálního programování lze krásně ilustrovat na jave: "Takhle se vypisuje na výstup, takhle se dělá podmínka, takhle cyklus, toho class Abc si zatím nevšímejte" vs. "Takhle se definuje třída, takhle se vytváří objekt, toho public static void main si zatím nevšímejte".
24.3.2010 16:26 Vskutečnosti Saýc | skóre: 7
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
V jave, zejo. Ucit se v pascalu proceduralne, ve smalltalku objektove, v haskellu funkcionalne ... to by bylo pekny, ale dost studentu by zesilelo :)
24.3.2010 16:27 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Asi, že kružnice není speciální případ bodu, takže by kružnice neměla být potomkem bodu.
24.3.2010 16:31 Vskutečnosti Saýc | skóre: 7
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Ono to vubec s napasovavanim objektovych paradigmat na realitu neni tak zhave. U GUI (okna obsahuji okna, tlacitka, menu, podokna, blabla, vsechno jsou to potomci grafickeho objektu, OK je potomkem tlacitka, atd.) to jde fakt dobre, a OOP tam nema konkurenci.

Jinde uz je to horsi, Zvlast kdyz "mutable state" a "concurrency" jsou veci ktere se nemaji moc rady.
mkoubik avatar 24.3.2010 16:32 mkoubik | skóre: 5 | blog: lorem_ipsum | Praha 8 - Bohnice
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Záleží co s těmi objekty chceš dělat, dovedu si představit, že za určitých okolností by to mělo smysl. Závěr: ilustrovat programátorské poučky na objektech z reálného světa, navíc vytržených z kontextu je blbost.
24.3.2010 16:34 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Já jen objasňoval, oč zřejmě jde.
Saljack avatar 24.3.2010 16:54 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Myslím něco jako je tady, už jenom proto, že je to "navrženo špatně". Hlavně kvůli tomu, že ten kdo to nikdy neviděl, tak to z tak debilního příkladu nikdy nepochopí, to je tak těžké vymyslet jiný příklad. Někde byl krásný příklad se zvířaty, z kterého to pochopí každý, také náš přednášející na objektové modelování má krásné příklady, z kterých to opravdu pochopí každý.
Sex, Drugs & Rock´n Roll.
24.3.2010 19:55 rajcze | skóre: 6 | blog: rajcze | kus od Brna
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Dovolim si s tvym tvrzenim o "privetivejsim" Ccku nesouhlasit. Rozhodne pro zacatecnika privetivejsi neni.

Mozna bysme si meli nejprv ujasnit, kdo ze je to ten "zacatecnik" a co ho chces naucit - zacatecnik je clovek, ktery neumi programovat - tj. neumi _spravne myslet_ a _nerozumi tomu, jak vevnitr funguje pocitac_.

Kdyz vezmu jen tak hloupy priklad, jako nacteni neceho ze vstupu - v packalu naprosto jednoduche a prime Read(), v Ccku uz musis tusit, co ze je to ukazatel.

Lepsi priklad - predavani parametru proceduram odkazem - zkus zacatecnikovi vysvetlit jak funguje reference/dereference - v tomhle jsou ochotni delat blbosti i vysokoskolaci. V pascalu opet velmi primocare odliseni v definici hlavicky funkce.

Z meho pohledu neexistuje pro splneni cile _naucit lidi myslet jako programator_ lepsi jazyk, nez pascal. Ve chvili, kdy umis myslet, je ti naprosto sumak, jak vypada syntakticky cukr toho daneho jazyka (a ano, pravdepodobne ti bude vadit desiva ukecanost pascalu, tak jako me treba vadi ukecanost javy...)

Co se pythonu tyka, rozhodne je to lepsi volba nez Ccko, ale taky ma svoje mouchy (predevsim mutable/immutable objekty) (nez se zeptas - python je muj nejmilejsi jazyk).
Rules of Optimization: Rule 1: Don't do it. Rule 2 (for experts only): Don't do it yet.
24.3.2010 16:49 Andrej | skóre: 47 | blog: Republic of Mordor | Zürich
Rozbalit Rozbalit vše Re: Červeno-čierne stromy

Packal je podle mě nejhorší odpad mezi programovacími jazyky. Kdyby nevznikl, mohlo být na školách (a možná i na světě) lépe.

Packal kombinuje nevýhody nízkoúrovňových jazyků (nemá garbage collection, negarantuje konzistentní paměťové reference, podpora pro dynamicky alokované struktury je ubohá, rozumná práce se stringy prakticky neexistuje) s nevýhodami vysokoúrovňových jazyků ((téměř) žádná přímá práce s pamětí, žádná aritmetika pointerů). K tomu přidává další (těžko klasifikovatelné) nevýhody, například nesmyslné indexování polí od 1 a hloupou volací konvenci, která (mimo jiné) předem vylučuje variadické funkce.

Packal vymyslel teoretik, který netušil, jak má jazyk vypadat, a všechno zpackal. Cokoliv je lepší. Všechny ostatní jazyky mají jakousi rozumnou ideu. Drtivá většina jejich nevýhod se dá ospravedlnit výhodami, které z toho plynou. Packal má jen samé nevýhody a na oplátku nenabízí vůbec nic.

ǑǦŹǓǕǙǞǺǨȞȬḔḦḰḾṊṎṸẄẌỖ
Saljack avatar 24.3.2010 16:56 Saljack | skóre: 28 | blog: Saljack | Praha
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Pěkně si to shrnul. Tohle by si měl přečíst každý profesor, který chce učit Pascal.
Sex, Drugs & Rock´n Roll.
24.3.2010 17:18 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Červeno-čierne stromy

například nesmyslné indexování polí od 1

Indexuje se od čísla, které si určí programátor, navíc se může indexovat i výčtovými typy.

Novější Pascaly, co se dnes učí na školách, si v některých věcech polepšily.

24.3.2010 17:41 Andrej | skóre: 47 | blog: Republic of Mordor | Zürich
Rozbalit Rozbalit vše Re: Červeno-čierne stromy

Pravda, poznámku ohledně indexování beru zpět. To jsem si spletl s jiným nepovedeným jazykem.

Nevím, které Packaly se dnes učí. Já jsem zažil FPC a GPC. Samozřejmě je pěkné mít v Packalu pointerovou aritmetiku nebo operátory typu +=. Ale není pak lepší prostě místo toho použít C?

Pokud se těmi „novějšími Packaly“ rozumí něco kolem Lazarusu nebo (už dávno mrtvého) Delphi, ani tohle není žádná výhra. O zásadních chybách v návrhu ObjectPackalu by se daly napsat celé stránky. Nemyslím si, že by se něco takového mělo učit.

ǑǦŹǓǕǙǞǺǨȞȬḔḦḰḾṊṎṸẄẌỖ
24.3.2010 19:01 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Červeno-čierne stromy

Ano, myslel jsem nové Delphi případně Delphi Prism. Bohužel ty jazyky nejsou vzájemně kompatibilní.

24.3.2010 22:21 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Ha, díky za odkaz na Delphi Prism, to vypadá jako moc pěkný jazyk! Jinak ale bohužel souhlasím s tímhle.
Ještě na tom nejsem tak špatně, abych četl Viewegha.
24.3.2010 17:49 Andrej | skóre: 47 | blog: Republic of Mordor | Zürich
Rozbalit Rozbalit vše Re: Červeno-čierne stromy

BTW, přece jen tam s tím indexováním byl nějaký problém, ale týkal se pouze stringů. Pokud si to správně pamatuju, stringy měly maximálně 255 B a na indexu 0 byl byte s délkou stringu. Tudíž string samotný byl indexovaný od 1. Pokud vím, některé implementace byly navržené tak nesmyslně, že všechny stringy kromě konstantních se alokovaly napevno po 256 bytech bez ohledu na skutečnou délku.

V novějších Packalech se samozřejmě objevila jiná reprezentace, která už nesmyslná omezení nemá.

ǑǦŹǓǕǙǞǺǨȞȬḔḦḰḾṊṎṸẄẌỖ
Milan Lajtoš avatar 24.3.2010 00:28 Milan Lajtoš | skóre: 22 | blog: /blog/babraq
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Na FMFI UK. Ono to bolo tak, že sa využívalo najmä Delphi alebo Turbo Delphi, no nejako zmizla free verzia, takže hľadali alternatívu a keďže Lazarus je asi pre nich najprijateľnejší, resp. takmer to isté, tak nemali čo riešiť.
“Every great achievement was once considered impossible.”
24.3.2010 00:55 Martin Matějek | skóre: 12 | blog: Flying_circus | Kladno
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Zajímavé. Teď zrovna píšu úkol, kde se používá binární strom (vyhledávání musí mít složitost log(N)), tak by mě zajímalo v čem je Červeno-černý strom specifický od binárního. Nebo co že to vlastně je... zas tolik se v tom nevyznám. Jinak pěkné, já bych neměl nervy na to psát gui. Určitě bych strávil víc času psaním gui než samotných algoritmů.
Don't judge me by the friends I keep. No, no, no. Judge me by the enemies I have slain!
Milan Lajtoš avatar 24.3.2010 01:14 Milan Lajtoš | skóre: 22 | blog: /blog/babraq
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
V binárnom strome môžeš mať vyhľadávanie O(log n), no musíš ho mať vyvážený. Predstav si binárny vyhľadávací strom, ktorý je ako reťaz (všetky vnútorné vrcholy majú len pravého/ľavého syna) - v tomto prípade bude mať vyhľadávanie zložitosť O(n). Pri vyvážených stromoch máš zaručené, že sa ti niečo také nestane a teda budeš mať garantovanú zložitosť O(log n).

A čo sa týka toho GUI - tvoj názor je správny, viac kódu je pre vykresľovanie a veci okolo. ;)
“Every great achievement was once considered impossible.”
24.3.2010 07:05 Vskutečnosti Saýc | skóre: 7
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Kolega uz psal ze binarni strom musi byt vyvazeny, ja doplnim, ze rb strom se vyvazuje sam, a s i docela jednoduchym algoritmem ti garantuje, ze ten strom nebude hlubsi (hur vyvazey) nez je minimalni mozna hloubka (nejvetsi vyvazenost) krat nejaka konstanta (tusim (1.42?), takze se chova predvidatelne a tak.

Je to oblibeny peklo pro mlade studenty CS :) ale dost se to pouziva, treba sociativni posle ve sposute dynamickych jazyku maji uvnitr rb stromy.
xxx avatar 24.3.2010 10:50 xxx | skóre: 42 | blog: Na Kafíčko
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
To chci. Strom co se vyvazuje sam. Jako, ze se na nej podivam a on se vyvazi :) Ja bych spis rek, ze se po vlozeni podivam co vzniklo a nekterych pripadech provedu rotace.
Please rise for the Futurama theme song.
24.3.2010 14:08 Vskutečnosti Saýc | skóre: 7
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Myslim pri pohledu zvenku, samozreme :)
24.3.2010 10:16 ivan
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
RB stromy predstavuji rozumny kompromis mezi casem postrebnym pro usporadani struktury a casem na vyhledani. Predstav si, ze cerne vrcholy RB stromu tvori idealne vyvazeny binarni strom a ceverne jsou vlastne jen takovej bordel kterej do toho stromu muzes pridavet aniz bys' musel ten strom nejakam narocne dovyvazovat.

Dalsi uzitecna vlastnost RB stromu je minimalni(konecny) pocet rotaci, ke kterym dochazi pri vyvazovani. Kazdy vrchol muze nest navic nejakou zajimavou informaci(napr. "je v mem podstromu prvocislo?, "vede z meho listu cesta k nejakemu jinemu RB stromu?") takovou informaci je nutne aktualizovat prave pouze pokud dochazi k rotaci.
24.3.2010 10:37 Vskutečnosti Saýc | skóre: 7
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Hashtabulky maji casto rychlejsi pristup pro zapis i cteni. Vyhodou stromu je, ze nemusim predem vedet kolik dat je (kdezto u hashtabulky byva problem kdyz mam najednou prijde trikrat vic dat nez jste pocital), a stromy se lip iteruji, protoze kdyz ho projdu a vysypu data, dostanu je usporadane, kdezto z hashtabulky mi vypadnou vicemene nahodna data. Stromu je taky jedno, jaka v nem ukladam data, kdezto hashovani ma tendeci se obcas nahodou rozbijet, kdyz vam system z niceho nic zacne generovat divna id programu a dalsi veci ktere neovlivnite.

(fakt tu delame distribuovanou prednasku o datovych strukturach?)
24.3.2010 16:48 Martin Matějek | skóre: 12 | blog: Flying_circus | Kladno
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Děkuji všem za distribuovanou přednášku :-) Zase jsem o něco chytřejší
Don't judge me by the friends I keep. No, no, no. Judge me by the enemies I have slain!
24.3.2010 08:26 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Červeno-černé stromy v Haskellu

Když už jsme u vkládání do červeno-černých stromů, tak takhle to lze udělat v jazycích, které mají pattern matching (toto je Haskell):

data Color = R | B
data RB a = E | T Color (RB a) a (RB a)

insert :: Ord a => a -> RB a -> RB a
insert x s = T B a z b
  where
    T _ a z b = ins s
    ins E = T R E x E
    ins s@(T B a y b) | x<y       = balance (ins a) y b
                      | x>y       = balance a y (ins b)
                      | otherwise = s
    ins s@(T R a y b) | x<y       = T R (ins a) y b
                      | x>y       = T R a y (ins b)
                      | otherwise = s

balance :: RB a -> a -> RB a -> RB a
balance (T R a x b) y (T R c z d) = T R (T B a x b) y (T B c z d)
balance (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance a x b = T B a x b

Kód jsem si půjčil ze stránky Red Black Trees

24.3.2010 08:37 Senior Database Programmer
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
No a čo ste dostali za známku keď vám tam polovica vecí chýbala?
24.3.2010 10:35 Robert Krátký | skóre: 94 | blog: Robertův bloček
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Viz také popis v JN: Red-black stromy.
Jardík avatar 24.3.2010 23:40 Jardík | skóre: 40 | blog: jarda_bloguje
Rozbalit Rozbalit vše Re: Červeno-čierne stromy
Proč jsou ty ikony kostrbatý? U mě na Windows normálně Lazarus umí alpha kanál ...
Věřím v jednoho Boha.

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.