Подскажите, как можно реализовать объединение двух Б деревьев.?!

а это от задачи зависит... можно тупо создать одну общую родительскую ноду к которой прилепить оба дерева...

Каждое дерево находится в отдельном файле, затем новое располагается также в одном файле.

и что?

"И что ?" написано немного ранее, если кто-то ещё не заметил.

под "и что?", имхо, подразумевалось: "считай одно дерево из одного файла, считай другое дерево из другого файла, создай ноду, прилепи к нему оба считанных дерева и сохрани полученное общее дерево в третий файл".

так доступно?

такой вопрос: "А определение Б дерева вы хоть знаете, а то, что оно сбалансированное вам не о чём не говорит?".

я думаю супер эффективный 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(|вставляемого дерева|)
если же величина известна, то вставляй меньшее в большее. у тебя файлы. если оба дерева - в файлах, и информация - числовая, то можно предположить, что величина файла указывает на величину дерева, и этим воспользоваться для "интеллигентного" угадывания.

А если выбрать дерево с наибольшей степенью вершин, а затем просто дабовлять в него ключи второго дерева?
Или это ерунда?

Если предположить что входные деревья были построенны по правилу типа "большее число вправо, меньшее число влево", то в лоб можно сделать вот так:
1. Из каждого из деревьев получить по отсортированному массиву за O(n)
2. Из 2х отсортированных массивов сделать один за O(n)
3. Отсортированный массив запихнуть в новое дерево за O(nlogn). Запихивать надо понятное дело с умом. Центральный элемент массива - корень. Цетральный элемент правого подмассива - правый потомок. Центральный элемент левого подмассива - левый потомок. И т.п.

В итоге получим сбалансированное выходное дерево за O(nlogn). Если же входные деревья просто бинарые и не используют никаких правил для построения (кроме того что у каждой ноды по два потомка), то в первый шаг нужно еще добавть сортировку выходных массивов руками.

http://www.semaphorecorp.com/btp/algo.html
Добавлено @ 14:14
Думаю будет полезно

Добавлено @ 14:16
глянька сюда: http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html

там не написано про сбалансированность.

Цитата

прошу обратить внимание, что в основной массе в данном топике по делу было сказано довольно мало

согласен. особенно если учесть твои ( MastEdm ) и твои ( Stream ) посты.

Hарод что же вы так ..., смотрели хоть те ссылки которые приведены ?

Там же реализация тоже прилагается.

http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html

Большое спасибо за ссылку, но в Кормене всё выглядит намного понятнее.............
Я ведь спрашиваю не про реализацию Б дерева (добавление, удаление и тд - это мне понятно), а конкретно про объединение двух таких деревьев, причём я бы хотел получить просто идею, а уж реализовать я попытаюсь сам.

Stream я на первой странице вроде как изложил рабочую идею.

Энто был я. Забыл залогиниться.

А других случаем нет?

А чем тебе эта не нравится то? Что то неясно или где то недочеты? Она простая, довольно эффективная и еще и сбалансированное дерево на выходе дает. Ничего сверхсложного писать не нужно. Все что нужно у тебя наверняка уже готово: обход дерева и добавление элемента в дерево. Тебе лишь необходимо правильно этими базовыми операциями воспользоваться.

Stream А в раздел Алгоритмы обращался ?

Цитата(_hunter @ 6.12.2005, 11:48)

там не написано про сбалансированность.

Если я не ошибаюсь, то Б-деревья сбалансированы по определению, или не так?

таки ошибаешся

Цитата(_hunter @ 7.12.2005, 16:10)

таки ошибаешся

Таки, бл*, не ошибаюсь!

Цитата

... Итак, Б-деревом назовём корневое дерево, устроенное следующим образом: 1. .... ... 4. Все листья находятся на одной и той же глубине (равной высоте дерева). ...

Скажу больше Б-деревья это подвид сбалансированых деревьев. И ещё, кто не врубается "Б" НЕ ЗНАЧИТ бинарное дерево (дерево, каждый узел которого содержит два потомка) это именно "Б - дерево". Кто не верит вот вам ссылка:
http://tid.com.ua/scripts/ishop.exe/addonres?id=31

Добавлено @ 18:01
Смотрите самые первые строки.

Цитата

A B-tree of order m is a multiway search tree of order m such that: All leaves are on the bottom level. All internal nodes (except the root node) have at least ceil(m / 2) (nonempty) children. The root node can have as few as 2 children if it is an internal node, and can obviously have no children if the root node is a leaf (that is, the whole tree consists only of the root node). Each leaf node must contain at least ceil(m / 2) - 1 keys

и

Цитата

A B-tree is a fairly well-balanced tree by virtue of the fact that all leaf nodes must be at the bottom.

( http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html )
ни слова про обязательную сбалансированность я не вижу...

Еп****


_hunter
Перевод твоей последней цитаты:

Б-дерево это чётко сбалансированое дерево, достоинство которого состоит в том, что все листья находятся внизу.

Перевод немного не дословный, но смысл верен. Здесь главное слово fairly - это чётко, а не довольно, как его иногда переводят. В значение довольно это слово становится рядом с прилагательным (например fairly easy - довольно легко), а с глаголом, как здесь переводится как чётко.
Добавлено @ 18:27
Блин не с прилагательным, а с другим наречием. easy - это наречие.

fairly well-balanced
"четко хорошо-сбалансированное"??? как-то не звучит...
а вот "довольно хорошо сбалансированное" имеет смысл. + как ты правильно заметил: ставится рядом с прилагательным. а что такое well? ;)

Господин хороший возьмите учебник английского.
wel-balanced это глагол в данном случае в страдательном залоге (вы про такой слыхали - это когда действие происходит над существительным)

Перевожу дословно:

Б-дерево есть чётко сбалансировали (кто?) достоинство факта что все листья находятся внизу.

Как видите здесь wel-balanced глагол. В сочитании с окончанием ed и глаголом to be в настоящем времени 3 лица, единственного числа (is) этот глагол означает, что не дерево кого-то балансировало, а его балансировали, причем чётко.
Добавлено @ 19:35
wel - это наречие или прилагательное в зависимости от контекста. Но здесь не отдельное well, здесь глагол, который пишется через дефиз - well-balanced и переводится он в данном контексте на русский как прилогательное, но ЭТО ГЛАГОЛ!!!!!
Добавлено @ 19:36
Просто по русский без прилогательного эту фразу фиг скажешь.

опять же не факт. ( особенно учитывая наличие двух равноприоритетных существительных )
перевожу ( тоже ) дословно:
Б-дерево ( что? ) есть [является] деревом _довольно хорошо-сбалансированным_ ( каким? ) ( дальше -- не важно )
+ well c дефисом ( как и любое прилагательное ) применяется только к прилагательным

Цитата(ToshaCh @ 7.12.2005, 19:28)

Перевожу дословно: Б-дерево есть чётко сбалансировали  (кто?) достоинство факта что все листья находятся внизу.

не рекомендую пользоваться онлайновыми переводчиками. иначе можно до такой абракадабры допереводиться

мой перевод:

A B-tree is a fairly well-balanced tree by virtue of the fact that all leaf nodes must be at the bottom.

Б-дерево является довольно хорошо сбалансированным деревом в силу того, что все его листья обязаны находиться внизу.

Это сообщение отредактировал(а) blackofe - 7.12.2005, 21:15

Никогда бы не подумал что Б дерево это не бинарное дерево. Ув. автор темы мою рекомендацию стало быть отправляй в топку. Она именно для бинарных деревьев.

Смотрите вот определение сбалансированности, классическое причём. Вы его можете найти по адресу.
http://khpi-iip.mipk.kharkiv.edu/library/d...book/prt06.html

Цитата

Одно из определений сбалансированности было дано Адельсоном-Вельским и Ландисом: Дерево является СБАЛАНСИРОВАННЫМ тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1. Поэтому деревья, удовлетворяющие этому условию, часто называют "АВЛ-деревьями" (по фамилиям их изобретателей).

Теперь то определение про которое мы спорим:
"...все его листья обязаны находиться внизу."

Связи никто не видит? А может все-таки подумаете? Или крутые программисты не думают? Им нечем.

Предидущие 2 поста мои.

ToshaCh, перед тем как брать учебник, возмите словарь:

Цитата

balanced [ ] прил. уравновешенный; гармоничный; пропорциональный, сбалансированный

( взято из лингво )
+ не wel-balanced ( глубинный, погружной )
а, все-таки, well

++ после прочтения словаря, таки возьми(те) учебник англицкого и почитай(те) про способы комбинации прилагательных. в частности про то, зачем там всунут дефис.

P.S.
я предпочитаю читать первоисточники а не плохие переводы

P.P.S.
ты привел не полное определение:

Цитата

Бинарное дерево называют сбалансированным (balanced), если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1.

( http://www.mstu.edu.ru/education/materials...kov/ch_1_2.html )
( если уж переводами пользуемся )
а кто-то говорил что b-дерево -- это совсем не бинарное дерево...

На мой взгляд, вы сейчас не о том ведёте дискуссию. В определении Б-дерева (по Кормену, чей авторитет для меня неоспорим) чётко сказано, что все листья дерева расположены на одной высоте... А тренироваться в переводах лучше где-нибудь в другом месте.

А бред типа "все листья находятся внизу" - это, извините конечно, детский сад.

Это сообщение отредактировал(а) MastEdm - 8.12.2005, 12:57

_hunter
При чём здесь бинарное дерево? Б-дерево это не бинарное дерево. Или вы ещё не поняли?
Почитайте собственную ссылку, а не выдерайте оттуда понравившееся место. Там следующее определение как раз про Б-дерево. Почитайте хотябы пару абзацев, после той фразы, которую вы привели.

Цитата

Определение: Бинарное дерево называют сбалансированным (balanced), если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1. При поиске данных во внешней памяти очень важной является проблема сокращения числа перемещений данных из внешней памяти в оперативную. Поэтому, в данном случае по сравнению с бинарными деревьями более выгодными окажутся сильно ветвящиеся деревья - т.к. их высота меньше, то при поиске потребуется меньше обращений к внешней памяти. Наибольшее применение в этом случае получили В-деревья (В - balanced) Определение: В-деревом порядка n называется сильно ветвящееся дерево степени 2n+1, обладающее следующими свойствами: Каждый узел, за исключением корня, содержит не менее n и не более 2n ключей. Корень содержит не менее одного и не более 2n ключей. Все листья расположены на одном уровне. Каждый нелистовой узел содержит два списка: упорядоченный по возрастанию значений список ключей и соответсвующий ему список указателей (для листовых узлов список указателей отсутствует).

Это более большой кусок той цитаты которую приводил _hunter

при том, что единственное определение сбалансированности что ты привел касается бинарных деревьев ( хотя ты постоянно твердиш что ,-деревья и бинарные деревья это не одно и то же )

следующее определение то про б-деревья, но там ( опять же ) ни слова про сбалансированность

Да лохонулся вместо:

Цитата(Guest @ 8.12.2005, 07:15)

вот определение сбалансированности,

Надо было сказать:

вот определение сбалансированности для бинарного дерева.
А дальше, в том же посте, я предлагал подумать. Вы подумали?

Дело в том, что как такового определения сбалансированности нет (лично я не знаю). Есть сбалансированые бинарные деревья (AVL) и сбалансированые прочие (B). Они вместе и составляют класс сбалансированных деревьев. И действительно в определениях, что я приводил нет прямого указания на сбалансированность, но ведь я предлагал подумать.

ооо!!! наконец-то...


предложения подумать я не заметил:

Цитата(ToshaCh @ 7.12.2005, 17:00)

Скажу больше Б-деревья это подвид сбалансированых деревьев. И ещё, кто не врубается "Б" НЕ ЗНАЧИТ бинарное дерево (дерево, каждый узел которого содержит два потомка) это именно "Б - дерево". Кто не верит вот вам ссылка: http://tid.com.ua/scripts/ishop.exe/addonres?id=31 Добавлено @ 18:01 Смотрите самые первые строки.

есть только громкие заявления и введение класса сбалансированных деревьев ( которого ( класса ) по-сути то и нет... )

+ б-дерево не значит сбалансированное дерево ( по крайней мере информации об этом нет ):

Цитата

The B-tree's creator, Rudolf Bayer, has not explained what the B stands for. The most common belief is that B stands for balanced, as all the leaf nodes are at the same level in the tree. B may also stand for Bayer, or for Boeing, because he was working for Boeing Scientific Research Labs.

это был первый пост, в котором вы пытались доказать что б-деревья суть сбалансированные деревья

насчет последнего поста под гостем...
а с чего ты взял что утверждения/определения справедливые для бинарных деревьев справедливы и для б-деревьев ( особенно если учесть что б\деревья -- совсем не бинарные деревья )?

!	Весь оффтоп который тут был в изобилии пошёл ффтопку. Настоятельно рекомендую не допускать рецидива во избежании...