Red-black tree - gdzie znajduje się dobry opis? - Grupy dyskusyjne w eGospodarka.pl

eGospodarka.pl › Grupy › pl.comp.programming › Red-black tree - gdzie znajduje się dobry opis?

« poprzedni wątek

następny wątek »

Ilość wypowiedzi w tym wątku: 5

1. Data: 2009-01-02 01:19:53
Temat: Red-black tree - gdzie znajduje się dobry opis?
Od: Maciej Piechotka <u...@g...com>

Próbuje zrozumieć (i zaimplementować) 'czerwono-czarne' drzewo. Zasady
na wikipedii niby są opisane ale mam problem z algorytmem usuwania.

Dokładniej - skąd wiadomo że w 3 przypadku brat ma dwoje dzieci (że są
bratankowie/siostrzeńcy)? W końcu jeśli jest nil-em to nie ma żadnych
dzieci (wtedy nasz węzeł też jest nil-em ale to chyba możliwe).

Reszta 'opisów' to niestety głównie animacje albo zoptymalizowany kod.
Czy ktoś mógłby to wyjaśnić.

Pozdrawiam
--
I've probably left my head... somewhere. Please wait untill I find it.
Homepage (pl_PL): http://uzytkownik.jogger.pl/
(GNU/)Linux User: #425935 (see http://counter.li.org/)

[ pokaż wiadomość z nagłówkami ]

do góry
2. Data: 2009-01-02 08:56:34
Temat: Re: Red-black tree - gdzie znajduje się dobry opis?
Od: Amelek <A...@g...com>

jeśli brat X jest nilem to X jest czerwone (bo inaczej ścieżka
przechodząca przez X miałaby o jeden czarny więcej) oraz dodatkowo
dzieci X są nilami, wiec można usunąć X bez problemu.

Opis na (angielskiej) Wikipedii jest całkiem Ok. Inny dobry opis jest
we Wprowadzeniu do Algorytmów Cormena.

Pozdrawiam

[ pokaż wiadomość z nagłówkami ]

do góry
3. Data: 2009-01-02 11:54:00
Temat: Re: Red-black tree - gdzie znajduje się dobry opis?
Od: "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>

Polecam drzewa czerwono-czarne pochylone w lewo (left-leaning red-
black trees) Roberta Sedgewicka (2008). Są prostsze niż te z 1978.

http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.
pdf
http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

Zaimplementowałem, działa.

[ pokaż wiadomość z nagłówkami ]

do góry
4. Data: 2009-01-04 00:49:18
Temat: Re: Red-black tree - gdzie znajduje się dobry opis?
Od: Maciej Piechotka <u...@g...com>

"Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl> writes:

> Polecam drzewa czerwono-czarne pochylone w lewo (left-leaning red-
> black trees) Roberta Sedgewicka (2008). Są prostsze niż te z 1978.
>
> http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.
pdf
> http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
>
> Zaimplementowałem, działa.

Na razie przejrzałem prezentację - wygląda interesująco (zabieram się za
'danie główne').

Pozdrawiam
--
I've probably left my head... somewhere. Please wait untill I find it.
Homepage (pl_PL): http://uzytkownik.jogger.pl/
(GNU/)Linux User: #425935 (see http://counter.li.org/)

[ pokaż wiadomość z nagłówkami ]

do góry
5. Data: 2009-01-05 11:00:42
Temat: Re: Red-black tree - gdzie znajduje się dobry opis?
Od: Maciej Piechotka <u...@g...com>

Amelek <A...@g...com> writes:

> Inny dobry opis jest
> we Wprowadzeniu do Algorytmów Cormena.

Wygląda na to, że dobrze by było zaopatrzyć się w literaturę. Oprócz tej
książki ktoś poleca jakieś?

Byłem ostatnio w księgarni i niestety wszystkie książki były na 'za
podstawowym poziomie'. Jak przeglądałem spis treści to o zbalansowanych
drzewach był podpodrozdział. Za to o tym co to jest algorytm i o
złożonosciach itd. cały rozdział.

Pozdrawiam
--
I've probably left my head... somewhere. Please wait untill I find it.
Homepage (pl_PL): http://uzytkownik.jogger.pl/
(GNU/)Linux User: #425935 (see http://counter.li.org/)

[ pokaż wiadomość z nagłówkami ]

do góry