tag:blogger.com,1999:blog-10303035.post3544514046478261147..comments2024-02-04T23:20:04.066+03:00Comments on Алёна C++: Красно-черные деревьяAlenahttp://www.blogger.com/profile/09389124127364799922noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-10303035.post-85475555775150828892017-05-16T12:46:45.864+03:002017-05-16T12:46:45.864+03:00статья супер. наконец-то я начала понимать профит ...статья супер. наконец-то я начала понимать профит КЧДМарияhttps://www.blogger.com/profile/15534840481929624167noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-53448267702396686872015-02-21T13:43:24.597+03:002015-02-21T13:43:24.597+03:00добрый день! скажите, пожалуйста, каждое ли АВЛ де...добрый день! скажите, пожалуйста, каждое ли АВЛ дерево можно раскрасить так, чтобы оно было красно черным? нигде не могу найти ответ на этот вопрос. Спасибо!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-85998885465052782152013-12-08T02:21:27.701+04:002013-12-08T02:21:27.701+04:00Сергей, похоже моя статья вас чем-то расстроила и ...<b>Сергей</b>, похоже моя статья вас чем-то расстроила и вы рветесь в бой.<br /><br />Если вам действительно интересно сравнение AVL и красно-черных деревьев, то вы его найдете, например, <a href="http://attractivechaos.wordpress.com/2008/10/02/comparison-of-binary-search-trees/" rel="nofollow">здесь</a>. <br /><br />Если вам хочется просто поспорить, то вам не сюда.Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-54422101683060953322013-12-07T19:46:23.176+04:002013-12-07T19:46:23.176+04:00Если почитать сам пост и комментарии автора приход...Если почитать сам пост и комментарии автора приходишь к выводу, что сбалансированными деревьями здесь называют AVL деревья. При этом почему-то балансировку называют слишком дорогой. И получается, что красно-черные быстрее. А может ли автор привести реальный пример сравнения AVL и Red-Black деревьев где бы AVL уступили цветным?<br />А то борьба с велосипедизмом смотрится смешно, если ссылаться только на то, что цветные используются в STL.<br /><br />СергейAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-1446213374191464532011-11-29T12:22:55.655+04:002011-11-29T12:22:55.655+04:00вот такое попалось, достаточно понятно нарисовано....вот такое попалось, достаточно понятно нарисовано. вдруг кому-нть пригодится.<br />http://rain.ifmo.ru/cat/view.php/vis/trees/red-black-2002Fl0noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-15553535372213043552010-08-11T15:32:01.828+04:002010-08-11T15:32:01.828+04:00Простите за глупости, а зачем эти сбалансированные...<i>Простите за глупости, а зачем эти сбалансированные деревья?</i><br /><br />Это структура данных, используется в программировании. Подробности знает Google.Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-80009765077676115012010-08-11T13:02:55.536+04:002010-08-11T13:02:55.536+04:00Простите за глупости, а зачем эти сбалансированные...Простите за глупости, а зачем эти сбалансированные деревья?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-85709365310925327042010-07-30T01:46:20.766+04:002010-07-30T01:46:20.766+04:00тьфу, чёрный - центральный, красный - боковой.тьфу, чёрный - центральный, красный - боковой.Kodthttps://www.blogger.com/profile/12739971468788709431noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-62491738242790846812010-07-30T01:43:42.913+04:002010-07-30T01:43:42.913+04:00Мне кажется, что для понимания КЧД нужно курить не...Мне кажется, что для понимания КЧД нужно курить не все эти трюки с вращением, а начать с того, что КЧД - это отображение троичного B-дерева на двоичное. (Как известно, с помощью двоичных деревьев можно реализовать любую структуру данных. Доказано LISP'ом с его cons-парами).<br /><br />Красные узлы - центральные в блоке, чёрные - боковые.<br /><br />Все эти выверты с вращениями - это отображение алгоритмов перебалансировки троичного B-дерева.<br /><br />По-моему, то ли в Кормене, то ли в Седжвике об этом хорошо написано.Kodthttps://www.blogger.com/profile/12739971468788709431noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-42125576130693127112010-07-29T20:36:50.469+04:002010-07-29T20:36:50.469+04:00В университетском курсе у нас термины "АВЛ&qu...<i>В университетском курсе у нас термины "АВЛ" и "сбалансированные" деревья употреблялись как синонимы.</i><br />Как хорошо, что еще есть университетские курсы, где преподают сбалансированные деревья :)<br /><i>Сейчас заглянула в перевод Кнута (Т.3, глава 6.2.3) "Бинарное дерево называется сбалансированным, если высота левого поддерева любого узла отличается не более чем на +/-1 от высоты правого поддерева". Так что все ОК вроде.</i><br />Вполне возможно, что меня ввели в заблуждение какие-то другие источники.Sergey Kishchenkohttps://www.blogger.com/profile/13451038740185023562noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-13546017108546392582010-07-29T11:43:09.178+04:002010-07-29T11:43:09.178+04:00Спасибо.
Использовать ли RB-trees -- конечно, дел...Спасибо.<br /><br />Использовать ли RB-trees -- конечно, дело хозяйское, но новичкам для общего образования пост очень полезен.Andrey ``Bass'' Shcheglovhttps://www.blogger.com/profile/00882744014756862371noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-50505894469188189272010-07-28T17:17:40.553+04:002010-07-28T17:17:40.553+04:00Есть интересное расширения/упрощение обычных RB-де...Есть интересное расширения/упрощение обычных RB-деревьев. Так называемые <a href="http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf" rel="nofollow">Left-leaning RB-деревья</a>. В них правила балансировки несколько проще.Александрhttps://www.blogger.com/profile/03980297457924475954noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-64251765421034745082010-07-28T16:44:26.011+04:002010-07-28T16:44:26.011+04:00Красно-чорные деревья говно.
Во-первых, это сочета...Красно-чорные деревья говно.<br />Во-первых, это сочетание цветов = анархо-коммунизм<br />http://en.wikipedia.org/wiki/Anarchist_Catalonia<br /><br />Во-фторых, их придумывали во времена когда RAM latency был 1 такт.<br />В современном мире, когда доступ к памяти порядка 30-150 тактов, подобные структуры данных хорошо работают только если влезают в кеш. Связные списки из этой же серии.<br /><br />В тех редких случаях когда мне нужны деревья, предпочитаю B-trees.<br />Их как и многие другие полезные вещи тоже придумывали во времена когда RAM latency был 1 такт.<br />Однако придумывали для, цитата с wikipedia, "systems that read and write large blocks of data", шо в полной мере относится к оперативной памяти современных компьютеров: запросы в память нынче блоками по 64 байта, если свопится, то вообще страницами по 4kb.<br /><br />Вот красивые графики, из которых следуети, что RB-trees сливают B-trees в среднем в 2.5 раза:<br />http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html<br />На некоторых операциях вперёд вырываюццо hashmaps.<br />Обращаю ваше внимание, шо в 100% тестах B-trees худший выбор из возможных.<br /><br />Это кстати одна из причин, по которой я искренне считаю STL говном: как ты упомянула, он зачем-то использует RB-trees для реализации map.<br /><br />Вот у Microsoft как обычно всё чётко: CAtlMap реализован через HashMap, к тому же память под элементы выделяется не как в STL, а большими блоками, причём об этом никому знать не обязательно - всё аккуратно спрятано внутри реализации. Это приводит к тому что типичные алгоритмы работающие с ассоциативными списками при использовании CAtlMap вместо std::map выигрывают от 2 раз до 1 порядка (когда-то пару раз измерял).<br /><br />Soonts.<br /><br />P.S. Но для расширения кругозора + прохождения собеседований конечно надо знать шо такое красно-чорные деревья.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-33557924592526977222010-07-28T16:43:06.511+04:002010-07-28T16:43:06.511+04:00Отличная статья.
RB-tree используется в реализац...Отличная статья. <br /><br />RB-tree используется в реализации <a href="http://en.wikipedia.org/wiki/COM_Structured_Storage" rel="nofollow">Microsoft COM Structured Storage</a><br /><br />Интересно так же было бы их поискать в имплементации файловых систем.<br /><br />Видео - класс!Aleksei Konstantinovhttps://www.blogger.com/profile/00751778902829826891noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-40691347666266689052010-07-28T15:05:46.835+04:002010-07-28T15:05:46.835+04:00@Alena
>И в функциональных языках вроде тоже.
В...@Alena<br />>И в функциональных языках вроде тоже.<br />В библиоткех функциональных языков. Встроенной в ядро языка реализации я не встречал (возможно, где-то в целях оптимизации применяются).Дмитрий Scriptinhttps://www.blogger.com/profile/05249583887958608405noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-19108226059045670752010-07-28T14:14:14.048+04:002010-07-28T14:14:14.048+04:0067108864
Почему именно rb-tree?
Потому что оно и...<b>67108864</b><br /><br /><i>Почему именно rb-tree?</i><br /><br />Потому что оно используется в STL. И в функциональных языках вроде тоже.Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-69961089682732261372010-07-28T14:12:09.954+04:002010-07-28T14:12:09.954+04:00Sergey Kishchenko
ЕМНИП, четкого определения сбал...<b>Sergey Kishchenko</b><br /><br /><i>ЕМНИП, четкого определения сбалансированности нет, есть несколько разных. Поэтому я бы немного подправил вводную часть. АВЛ-деревья не являются единственными "действительно" сбалансированными деревьями, красно-черные тоже сбалансированны, но по другому определению.</i> <br /><br />В университетском курсе у нас термины "АВЛ" и "сбалансированные" деревья употреблялись как синонимы. Сейчас заглянула в перевод Кнута (Т.3, глава 6.2.3) "Бинарное дерево называется сбалансированным, если высота левого поддерева любого узла отличается не более чем на +/-1 от высоты правого поддерева". Так что все ОК вроде.<br /><br /><i>Не нужно напрасно пугать читателей и вынуждать их искать более сложные алгоритмы</i><br /><br />Да если что - ссылки на Википедию есть, народ разберется если чего не так.<br /><br /><i>P.S. Отличный цикл, так держать!</i><br /><br />Спасибо :-)Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-13460366362912257752010-07-28T14:07:16.983+04:002010-07-28T14:07:16.983+04:00Почему именно rb-tree? C точки зрения ручной реали...Почему именно rb-tree? C точки зрения ручной реализации - это порядка 5-6 нетривиальных поворотов. А если надо удалять, так это вообще для большинства деревьев жестокая реализация.<br /><br />Наиболее простым сбалансированным деревом (имхо) является декартово дерево (дерамида, treap), там только 2 тривиальных поворота, балансировка достигается как в двоичной куче за счет случайного дополнительного атрибута.<br /><br />Почти успел реализовать Б-дерево, но понял что удаление из дерева очень не просто.<br /><br />Дерамида у мена влезла в 10Кб исходников, а все другие реализации деревьев которые я нашел отличаются в большую строну на порядок (не менее двоичного).<br /><br />Считаю, что красно-черное дерево не является велосипедом, а скорее какой-то монстрообразный танк.67108864https://www.blogger.com/profile/02888735973047043835noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-73598105367966878232010-07-28T14:05:23.779+04:002010-07-28T14:05:23.779+04:00pure virtual
Нраведцо ^_^
:-)
Это, насколько я ...<b>pure virtual</b><br /><br /><i>Нраведцо ^_^</i><br /><br />:-)<br /><br /><i>Это, насколько я понимаю, всё ещё борьба с велосипедизмом?</i> <br /><br />Ага<br /><br /><i>Жестокие же велосипедисты встречались на Вашем пути:)</i><br /><br />Не, попыток придумать свои красно-черные деревья я не видела, к счастью.Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-3482348911615516222010-07-28T13:45:25.202+04:002010-07-28T13:45:25.202+04:00ЕМНИП, четкого определения сбалансированности нет,...ЕМНИП, четкого определения сбалансированности нет, есть несколько разных. Поэтому я бы немного подправил вводную часть. АВЛ-деревья не являются единственными "действительно" сбалансированными деревьями, красно-черные тоже сбалансированны, но по другому определению. Не нужно напрасно пугать читателей и вынуждать их искать более сложные алгоритмы<br />P.S. Отличный цикл, так держать!Sergey Kishchenkohttps://www.blogger.com/profile/13451038740185023562noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-89691818349130047532010-07-28T13:36:46.502+04:002010-07-28T13:36:46.502+04:00Нраведцо ^_^
Это, насколько я понимаю, всё ещё бо...Нраведцо ^_^<br /><br />Это, насколько я понимаю, всё ещё борьба с велосипедизмом? Жестокие же велосипедисты встречались на Вашем пути:)pure virtualhttps://www.blogger.com/profile/16786779539675023451noreply@blogger.com