Nie jesteś zalogowany.
Jeśli nie posiadasz konta, zarejestruj je już teraz! Pozwoli Ci ono w pełni korzystać z naszego serwisu. Spamerom dziękujemy!

Ogłoszenie

Prosimy o pomoc dla małej Julki — przekaż 1% podatku na Fundacji Dzieciom zdazyć z Pomocą.
Więcej informacji na dug.net.pl/pomagamy/.

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

  ethanak - Użytkownik

ethanak
Użytkownik
Skąd: Ungwenor
Zarejestrowany: 2010-07-19
Serwis

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

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)


Nim mechaniczne larum zagrasz mi, kanalio,
głosząc nadejście Javy - śmiertelnego wroga!
[i]Zespół Adwokacki Dyskrecja[/i]

Offline

 

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

  dominbik - Członek DUG

dominbik
Członek DUG
Zarejestrowany: 2011-07-25

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

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/algorithm-of-sorted-array-to-red-black.html
?
z ciekawości; masz jakąś dobrą implementację takiego drzewa w C?


[img]http://img34.imageshack.us/img34/5092/zw9m.png[/img] [img]http://img29.imageshack.us/img29/219/pibw.png[/img]

Offline

 

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

  ethanak - Użytkownik

ethanak
Użytkownik
Skąd: Ungwenor
Zarejestrowany: 2010-07-19
Serwis

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

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)


Nim mechaniczne larum zagrasz mi, kanalio,
głosząc nadejście Javy - śmiertelnego wroga!
[i]Zespół Adwokacki Dyskrecja[/i]

Offline

 

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

  ethanak - Użytkownik

ethanak
Użytkownik
Skąd: Ungwenor
Zarejestrowany: 2010-07-19
Serwis

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

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

(Note: Red-Black Tree is also called Balanced Binary Search Tree)[/quote]
(z właściwego artykułu [url]http://physicsmathscomputers.blogspot.com/2012/10/sorted-array-to-red-black-tree.html[/url])
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:
[url]http://en.literateprograms.org/Red-black_tree_%28C%29[/url] 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:
[url]http://cs.stackexchange.com/questions/10990/colour-a-binary-tree-to-be-a-red-black-tree?rq=1[/url]
Zobaczę co się z tego da zrobić...

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


Nim mechaniczne larum zagrasz mi, kanalio,
głosząc nadejście Javy - śmiertelnego wroga!
[i]Zespół Adwokacki Dyskrecja[/i]

Offline

 

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

  dominbik - Członek DUG

dominbik
Członek DUG
Zarejestrowany: 2011-07-25

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

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)

[img]http://img34.imageshack.us/img34/5092/zw9m.png[/img] [img]http://img29.imageshack.us/img29/219/pibw.png[/img]

Offline

 

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

  ethanak - Użytkownik

ethanak
Użytkownik
Skąd: Ungwenor
Zarejestrowany: 2010-07-19
Serwis

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

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 :)


Nim mechaniczne larum zagrasz mi, kanalio,
głosząc nadejście Javy - śmiertelnego wroga!
[i]Zespół Adwokacki Dyskrecja[/i]

Offline

 

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

  dominbik - Członek DUG

dominbik
Członek DUG
Zarejestrowany: 2011-07-25

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

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).


[img]http://img34.imageshack.us/img34/5092/zw9m.png[/img] [img]http://img29.imageshack.us/img29/219/pibw.png[/img]

Offline

 

Stopka forum

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson
Możesz wyłączyć AdBlock — tu nie ma reklam ;-)

[ Generated in 0.010 seconds, 11 queries executed ]

Informacje debugowania

Time (s) Query
0.00011 SET CHARSET latin2
0.00004 SET NAMES latin2
0.00172 SELECT u.*, g.*, o.logged FROM punbb_users AS u INNER JOIN punbb_groups AS g ON u.group_id=g.g_id LEFT JOIN punbb_online AS o ON o.ident='3.145.59.165' WHERE u.id=1
0.00100 UPDATE punbb_online SET logged=1716054798 WHERE ident='3.145.59.165'
0.00038 SELECT * FROM punbb_online WHERE logged<1716054498
0.00101 SELECT topic_id FROM punbb_posts WHERE id=271751
0.00113 SELECT id FROM punbb_posts WHERE topic_id=26143 ORDER BY posted
0.00081 SELECT t.subject, t.closed, t.num_replies, t.sticky, f.id AS forum_id, f.forum_name, f.moderators, fp.post_replies, 0 FROM punbb_topics AS t INNER JOIN punbb_forums AS f ON f.id=t.forum_id LEFT JOIN punbb_forum_perms AS fp ON (fp.forum_id=f.id AND fp.group_id=3) WHERE (fp.read_forum IS NULL OR fp.read_forum=1) AND t.id=26143 AND t.moved_to IS NULL
0.00007 SELECT search_for, replace_with FROM punbb_censoring
0.00081 SELECT u.email, u.title, u.url, u.location, u.use_avatar, u.signature, u.email_setting, u.num_posts, u.registered, u.admin_note, p.id, p.poster AS username, p.poster_id, p.poster_ip, p.poster_email, p.message, p.hide_smilies, p.posted, p.edited, p.edited_by, g.g_id, g.g_user_title, o.user_id AS is_online FROM punbb_posts AS p INNER JOIN punbb_users AS u ON u.id=p.poster_id INNER JOIN punbb_groups AS g ON g.g_id=u.group_id LEFT JOIN punbb_online AS o ON (o.user_id=u.id AND o.user_id!=1 AND o.idle=0) WHERE p.topic_id=26143 ORDER BY p.id LIMIT 0,25
0.00104 UPDATE punbb_topics SET num_views=num_views+1 WHERE id=26143
Total query time: 0.00812 s