Forum Debian Users Gang

ethanak · 2014-07-18 08:34:09

Szlag mnie za chwilę trafi - jakoś wszelkie znane mi źródła milczą na ten temat a nie usmiecha mi się ponowne wynajdowanie koła.
Zadanie (nie, nie na klasówkę, fragment kodu nowej wersji Mileny):
mam tablicę zawierającą węzły luzem (tzn. wskaźniki do struct node), uporządkowane według kluczy, bez powtórzeń.
muszę zrobić z tego drzewo red-black.
Ilość orientacyjnie elementów w tablicy: 10k<N<100k
Ktoś ma namiary na jakiś sensowny algorytm?
Pytanie zastępcze: jeśli zrobię z tego wyważone drzewo binarne (to akurat trywialne) - jak je najprościej pokolorować?

Ostatnio edytowany przez ethanak (2014-07-19 10:33:42)

dominbik · 2014-07-18 14:36:58

masz posortowaną tablice rbt_node *arr; tyle, że te node nie mają przydzielonego rbt_node *left, *right, *parent i enum rbt_color color? czy to jakieś inne node (np. listy) ?

patrzyłeś na to:
http://physicsmathscomputers.blogspot.com/2013/03/a … ed-black.html
?
z ciekawości; masz jakąś dobrą implementację takiego drzewa w C?

ethanak · 2014-07-18 14:40:24

a. dokładnie tak
b. nie widziałem, teraz nie sprawdzę
c. podeślę link jak będę w domu (pełna implementacja w C)

ethanak · 2014-07-19 06:39:30

Ech... co tu dużo mówić...

(Note: Red-Black Tree is also called Balanced Binary Search Tree)

(z właściwego artykułu http://physicsmathscomputers.blogspot.com/2012/10/s … ack-tree.html)
Czyli kolesiowi nie wróżę zrobienia większej kariery w czym bardziej skomplikowanym niż pasanie kóz.
Ale dzięki za zainteresowanie.

Co do używanego kodu:
http://en.literateprograms.org/Red-black_tree_%28C%29 i na końcu masz "download".
Tu masz dość ładny artykulik z prawie działającym kodem. Prawie - bo znalazłem jednego babola: cieknie przy próbie wstawienia węzła który już istnieje, bo węzeł jest alokowany przed lookup_node. Poza tym nie mogę nic powiedzieć na temat tego czy to dobra implementacja... w każdym razie działa.
Ja wykorzystałem tylko część dotyczącą lookup/insert, w moim kodzie nie występuje usuwanie.

Edytka :)
Znalazłem właśnie coś takiego:
http://cs.stackexchange.com/questions/10990/colour- … ack-tree?rq=1
Zobaczę co się z tego da zrobić...

Ostatnio edytowany przez ethanak (2014-07-19 07:35:39)

dominbik · 2014-07-19 10:27:55

właśnie tą implementacje sobie ściągnąłem wcześniej wydała mi się dość czytelna i niezła, ale trochę mnie zasmucił wynik valgrinda odnośnie ich skompilowanego testmain.c ;\

Kod:

==2176== HEAP SUMMARY:
==2176==     in use at exit: 51,176 bytes in 1,067 blocks
==2176==   total heap usage: 5,001 allocs, 3,934 frees, 240,008 bytes allocated
==2176== 
==2176== Searching for pointers to 1,067 not-freed blocks
==2176== Checked 64,024 bytes
==2176== 
==2176== 432 bytes in 9 blocks are indirectly lost in loss record 1 of 3
==2176==    at 0x4C28730: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2176==    by 0x400E89: new_node (in /home/kelloco2/Downloads/drzewooo/Red-black_tree_(C)/rbtree)
==2176==    by 0x40117B: rbtree_insert (in /home/kelloco2/Downloads/drzewooo/Red-black_tree_(C)/rbtree)
==2176==    by 0x40096E: main (in /home/kelloco2/Downloads/drzewooo/Red-black_tree_(C)/rbtree)
==2176== 
==2176== 440 (8 direct, 432 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 3
==2176==    at 0x4C28730: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2176==    by 0x400E43: rbtree_create (in /home/kelloco2/Downloads/drzewooo/Red-black_tree_(C)/rbtree)
==2176==    by 0x4008D3: main (in /home/kelloco2/Downloads/drzewooo/Red-black_tree_(C)/rbtree)
==2176== 
==2176== 50,736 bytes in 1,057 blocks are definitely lost in loss record 3 of 3
==2176==    at 0x4C28730: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2176==    by 0x400E89: new_node (in /home/kelloco2/Downloads/drzewooo/Red-black_tree_(C)/rbtree)
==2176==    by 0x40117B: rbtree_insert (in /home/kelloco2/Downloads/drzewooo/Red-black_tree_(C)/rbtree)
==2176==    by 0x40096E: main (in /home/kelloco2/Downloads/drzewooo/Red-black_tree_(C)/rbtree)
==2176== 
==2176== LEAK SUMMARY:
==2176==    definitely lost: 50,744 bytes in 1,058 blocks
==2176==    indirectly lost: 432 bytes in 9 blocks
==2176==      possibly lost: 0 bytes in 0 blocks
==2176==    still reachable: 0 bytes in 0 blocks
==2176==         suppressed: 0 bytes in 0 blocks
==2176== 
==2176== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 1 from 1)
--2176-- 
--2176-- used_suppression:      1 dl-hack3-cond-1 /usr/lib/valgrind/default.supp:1196
==2176== 
==2176== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 1 from 1)

ethanak · 2014-07-19 10:33:04

Podejrzewam że to ten babol o którym mówiłem - poprawisz sam czy mam wysłać swój pomysł (ale to już nie teraz bo wypadam na piwo)?
BTW. kolorowanie ze stackexchange działa bezbłędnie - a tak się tego naszukałem :)

dominbik · 2014-07-19 10:37:35

nie spoko jak będę potrzebować to sobie to poprawie. po prostu byłem ciekaw czy może jakaś fajniejsza implementacja jest tego. (tj. bardziej czytelna niż ta).

Forum Debian Users Gang

Ogłoszenie

#1 2014-07-18 08:34:09

ethanak - Użytkownik

[SOLVED]Jak zrobić drzewo red-black z posortowanej tablicy

#2 2014-07-18 14:36:58

dominbik - Członek DUG

Re: [SOLVED]Jak zrobić drzewo red-black z posortowanej tablicy

#3 2014-07-18 14:40:24

ethanak - Użytkownik

Re: [SOLVED]Jak zrobić drzewo red-black z posortowanej tablicy

#4 2014-07-19 06:39:30

ethanak - Użytkownik

Re: [SOLVED]Jak zrobić drzewo red-black z posortowanej tablicy

#5 2014-07-19 10:27:55

dominbik - Członek DUG

Re: [SOLVED]Jak zrobić drzewo red-black z posortowanej tablicy

Kod:

#6 2014-07-19 10:33:04

ethanak - Użytkownik

Re: [SOLVED]Jak zrobić drzewo red-black z posortowanej tablicy

#7 2014-07-19 10:37:35

dominbik - Członek DUG

Re: [SOLVED]Jak zrobić drzewo red-black z posortowanej tablicy

Stopka forum