| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Б деревья |
| Автор: Stream 1.12.2005, 17:22 |
| Подскажите, как можно реализовать объединение двух Б деревьев.?! |
| Автор: _hunter 1.12.2005, 17:45 |
| а это от задачи зависит... можно тупо создать одну общую родительскую ноду к которой прилепить оба дерева... |
| Автор: Stream 1.12.2005, 21:27 |
| Каждое дерево находится в отдельном файле, затем новое располагается также в одном файле. |
| Автор: _hunter 2.12.2005, 12:20 |
| и что? |
| Автор: Stream 2.12.2005, 22:23 |
| "И что ?" написано немного ранее, если кто-то ещё не заметил. |
| Автор: blackofe 2.12.2005, 22:37 |
| под "и что?", имхо, подразумевалось: "считай одно дерево из одного файла, считай другое дерево из другого файла, создай ноду, прилепи к нему оба считанных дерева и сохрани полученное общее дерево в третий файл". так доступно? |
| Автор: Stream 3.12.2005, 11:05 |
| такой вопрос: "А определение Б дерева вы хоть знаете, а то, что оно сбалансированное вам не о чём не говорит?". |
| Автор: Guest 3.12.2005, 12:14 |
| я думаю супер эффективный merge это на докторскую потянет... a на пальцах: каждый нод создается на основе предыдущих данного дерева. поэтому в общем случае ты не можешь надеяться, что сохраняется неравенство {n1_i < n2_j: по всем i в t1 и j в t2 } (т.е. все ветви t1 меньше, чем все ветви t2) т.е. нужно найти индексы in1,in2,in3,in4...in5 для превращения деревьев t1,t2 в Т, так что t1,t2 - отдельные ветки этого B-tree, а это невозможно. поэтому по моему тебе надо: выбрать дерево побольше и к нему то что поменьше нод за нодом вставлять. в принципе, если дерево не содержит своей величины, то придется тебе надеяться на авось, потому что меньшее дерево определить и вставить займет 2*О(|t_min|), a просто вставить одно в другое O(|вставляемое дерево|) времени. вопрос что дольше: 2*О(|t_min|) или O(|вставляемого дерева|) если же величина известна, то вставляй меньшее в большее. у тебя файлы. если оба дерева - в файлах, и информация - числовая, то можно предположить, что величина файла указывает на величину дерева, и этим воспользоваться для "интеллигентного" угадывания. |
| Автор: Stream 3.12.2005, 12:22 |
| А если выбрать дерево с наибольшей степенью вершин, а затем просто дабовлять в него ключи второго дерева? Или это ерунда? |
| Автор: dwr_budr 5.12.2005, 12:27 |
| Если предположить что входные деревья были построенны по правилу типа "большее число вправо, меньшее число влево", то в лоб можно сделать вот так: 1. Из каждого из деревьев получить по отсортированному массиву за O(n) 2. Из 2х отсортированных массивов сделать один за O(n) 3. Отсортированный массив запихнуть в новое дерево за O(nlogn). Запихивать надо понятное дело с умом. Центральный элемент массива - корень. Цетральный элемент правого подмассива - правый потомок. Центральный элемент левого подмассива - левый потомок. И т.п. В итоге получим сбалансированное выходное дерево за O(nlogn). Если же входные деревья просто бинарые и не используют никаких правил для построения (кроме того что у каждой ноды по два потомка), то в первый шаг нужно еще добавть сортировку выходных массивов руками. |
| Автор: pablo 5.12.2005, 14:14 |
| http://www.semaphorecorp.com/btp/algo.html Добавлено @ 14:14 Думаю будет полезно Добавлено @ 14:16 глянька сюда: http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html |
| Автор: _hunter 6.12.2005, 11:48 | ||
там не написано про сбалансированность.
согласен. особенно если учесть твои ( MastEdm ) и твои ( Stream ) посты. |
| Автор: pablo 6.12.2005, 14:21 |
| Hарод что же вы так ..., смотрели хоть те ссылки которые приведены ? Там же реализация тоже прилагается. http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html |
| Автор: Stream 6.12.2005, 19:10 |
| Большое спасибо за ссылку, но в Кормене всё выглядит намного понятнее............. Я ведь спрашиваю не про реализацию Б дерева (добавление, удаление и тд - это мне понятно), а конкретно про объединение двух таких деревьев, причём я бы хотел получить просто идею, а уж реализовать я попытаюсь сам. |
| Автор: Guest 6.12.2005, 21:32 |
| Stream я на первой странице вроде как изложил рабочую идею. |
| Автор: dwr_budr 6.12.2005, 21:33 |
| Энто был я. Забыл залогиниться. |
| Автор: Stream 7.12.2005, 14:01 |
| А других случаем нет? |
| Автор: dwr_budr 7.12.2005, 14:27 |
| А чем тебе эта не нравится то? Что то неясно или где то недочеты? Она простая, довольно эффективная и еще и сбалансированное дерево на выходе дает. Ничего сверхсложного писать не нужно. Все что нужно у тебя наверняка уже готово: обход дерева и добавление элемента в дерево. Тебе лишь необходимо правильно этими базовыми операциями воспользоваться. |
| Автор: pablo 7.12.2005, 14:32 |
| Stream А в раздел Алгоритмы обращался ? |
| Автор: MastEdm 7.12.2005, 15:54 | ||
Если я не ошибаюсь, то Б-деревья сбалансированы по определению, или не так?  |
| Автор: _hunter 7.12.2005, 16:10 |
| таки ошибаешся |
| Автор: MastEdm 7.12.2005, 17:06 | ||||
Таки, бл*, не ошибаюсь! 
|
| Автор: ToshaCh 7.12.2005, 18:00 |
| Скажу больше Б-деревья это подвид сбалансированых деревьев. И ещё, кто не врубается "Б" НЕ ЗНАЧИТ бинарное дерево (дерево, каждый узел которого содержит два потомка) это именно "Б - дерево". Кто не верит вот вам ссылка: http://tid.com.ua/scripts/ishop.exe/addonres?id=31 Добавлено @ 18:01 Смотрите самые первые строки. |
| Автор: _hunter 7.12.2005, 18:01 | ||||
и
( http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html ) ни слова про обязательную сбалансированность я не вижу... |
| Автор: ToshaCh 7.12.2005, 18:26 |
| Еп**** _hunter Перевод твоей последней цитаты: Б-дерево это чётко сбалансированое дерево, достоинство которого состоит в том, что все листья находятся внизу. Перевод немного не дословный, но смысл верен. Здесь главное слово fairly - это чётко, а не довольно, как его иногда переводят. В значение довольно это слово становится рядом с прилагательным (например fairly easy - довольно легко), а с глаголом, как здесь переводится как чётко. Добавлено @ 18:27 Блин не с прилагательным, а с другим наречием. easy - это наречие. |
| Автор: _hunter 7.12.2005, 19:14 |
| fairly well-balanced "четко хорошо-сбалансированное"??? как-то не звучит... а вот "довольно хорошо сбалансированное" имеет смысл. + как ты правильно заметил: ставится рядом с прилагательным. а что такое well? ;) |
| Автор: ToshaCh 7.12.2005, 19:28 |
| Господин хороший возьмите учебник английского. wel-balanced это глагол в данном случае в страдательном залоге (вы про такой слыхали - это когда действие происходит над существительным) Перевожу дословно: Б-дерево есть чётко сбалансировали (кто?) достоинство факта что все листья находятся внизу. Как видите здесь wel-balanced глагол. В сочитании с окончанием ed и глаголом to be в настоящем времени 3 лица, единственного числа (is) этот глагол означает, что не дерево кого-то балансировало, а его балансировали, причем чётко. Добавлено @ 19:35 wel - это наречие или прилагательное в зависимости от контекста. Но здесь не отдельное well, здесь глагол, который пишется через дефиз - well-balanced и переводится он в данном контексте на русский как прилогательное, но ЭТО ГЛАГОЛ!!!!! Добавлено @ 19:36 Просто по русский без прилогательного эту фразу фиг скажешь. |
| Автор: _hunter 7.12.2005, 20:06 |
| опять же не факт. ( особенно учитывая наличие двух равноприоритетных существительных ) перевожу ( тоже ) дословно: Б-дерево ( что? ) есть [является] деревом _довольно хорошо-сбалансированным_ ( каким? ) ( дальше -- не важно ) + well c дефисом ( как и любое прилагательное ) применяется только к прилагательным |
| Автор: blackofe 7.12.2005, 21:07 | ||
не рекомендую пользоваться онлайновыми переводчиками. иначе можно до такой абракадабры допереводиться  мой перевод: A B-tree is a fairly well-balanced tree by virtue of the fact that all leaf nodes must be at the bottom. Б-дерево является довольно хорошо сбалансированным деревом в силу того, что все его листья обязаны находиться внизу. |
| Автор: dwr_budr 7.12.2005, 22:10 |
| Никогда бы не подумал что Б дерево это не бинарное дерево. Ув. автор темы мою рекомендацию стало быть отправляй в топку. Она именно для бинарных деревьев. |
| Автор: Guest 8.12.2005, 07:15 | ||
| Смотрите вот определение сбалансированности, классическое причём. Вы его можете найти по адресу. http://khpi-iip.mipk.kharkiv.edu/library/datastr/book/prt06.html
Теперь то определение про которое мы спорим: "...все его листья обязаны находиться внизу." Связи никто не видит? А может все-таки подумаете? Или крутые программисты не думают? Им нечем. |
| Автор: ToshaCh 8.12.2005, 07:17 |
| Предидущие 2 поста мои. |
| Автор: _hunter 8.12.2005, 12:36 | ||||
ToshaCh, перед тем как брать учебник, возмите словарь:
( взято из лингво ) + не wel-balanced ( глубинный, погружной ) а, все-таки, well ++ после прочтения словаря, таки возьми(те) учебник англицкого и почитай(те) про способы комбинации прилагательных. в частности про то, зачем там всунут дефис. P.S. я предпочитаю читать первоисточники а не плохие переводы P.P.S. ты привел не полное определение:
( http://www.mstu.edu.ru/education/materials/zelenkov/ch_1_2.html ) ( если уж переводами пользуемся ) а кто-то говорил что b-дерево -- это совсем не бинарное дерево... |
| Автор: MastEdm 8.12.2005, 12:56 |
| На мой взгляд, вы сейчас не о том ведёте дискуссию. В определении Б-дерева (по Кормену, чей авторитет для меня неоспорим) чётко сказано, что все листья дерева расположены на одной высоте... А тренироваться в переводах лучше где-нибудь в другом месте. А бред типа "все листья находятся внизу" - это, извините конечно, детский сад. |
| Автор: ToshaCh 8.12.2005, 17:47 |
| _hunter При чём здесь бинарное дерево? Б-дерево это не бинарное дерево. Или вы ещё не поняли? Почитайте собственную ссылку, а не выдерайте оттуда понравившееся место. Там следующее определение как раз про Б-дерево. Почитайте хотябы пару абзацев, после той фразы, которую вы привели. |
| Автор: ToshaCh 8.12.2005, 18:03 | ||
Это более большой кусок той цитаты которую приводил _hunter |
| Автор: _hunter 8.12.2005, 18:27 |
| при том, что единственное определение сбалансированности что ты привел касается бинарных деревьев ( хотя ты постоянно твердиш что ,-деревья и бинарные деревья это не одно и то же ) следующее определение то про б-деревья, но там ( опять же ) ни слова про сбалансированность |
| Автор: ToshaCh 9.12.2005, 13:58 | ||
Да лохонулся вместо:
Надо было сказать: вот определение сбалансированности для бинарного дерева. А дальше, в том же посте, я предлагал подумать. Вы подумали? Дело в том, что как такового определения сбалансированности нет (лично я не знаю). Есть сбалансированые бинарные деревья (AVL) и сбалансированые прочие (B). Они вместе и составляют класс сбалансированных деревьев. И действительно в определениях, что я приводил нет прямого указания на сбалансированность, но ведь я предлагал подумать. |
| Автор: _hunter 9.12.2005, 14:36 | ||||
| ооо!!! наконец-то... предложения подумать я не заметил:
есть только громкие заявления и введение класса сбалансированных деревьев ( которого ( класса ) по-сути то и нет... ) + б-дерево не значит сбалансированное дерево ( по крайней мере информации об этом нет ):
|
| Автор: _hunter 9.12.2005, 16:49 |
| это был первый пост, в котором вы пытались доказать что б-деревья суть сбалансированные деревья насчет последнего поста под гостем... а с чего ты взял что утверждения/определения справедливые для бинарных деревьев справедливы и для б-деревьев ( особенно если учесть что б\деревья -- совсем не бинарные деревья )? |
| Автор: chipset 10.12.2005, 17:34 | ||
|