Я пишу менеджер баз данных стиля dbm с неизменяемыми B + Trees в качестве носителя данных (см. http://sf.net/projects/aodbm/). Есть ли быстрый алгоритм для слияния двух деревьев B + (где деревья потенциально разделяют узлы)?
Есть ли быстрый алгоритм для объединения отсортированных B + деревьев?
Ответ 1
это омега (n) проблема.
Доказательство: предположим, что у него была лучшая сложность O (d) и d < п. вы можете организовать дерево B + как массив, а затем слияние двух деревьев будет слияние двух массивов. если это так, вы можете сделать слияние (A1, A2) в O (d), а использование mergesort может быть O (dlog (n)) - противоречие.
a O (n) решение (на самом деле это будет, конечно, theta (n)):
1.flat T1 и T2 в отсортированные массивы A1, A2.
2.use A < - merge (A1, A2)
3. построить пустое "почти полное" дерево T с точно | T1 | + | T2 | "место".
4. заполните T с помощью A (поиск в порядке)
5. результатом является T.
сложности:
Шаг 1 - это O (n) (в порядке поиска)
Шаг 2 - это сложность сложения О (п) (поскольку A1, A2 оба отсортированы)
Шаги 3 + 4 тривиально O (n), а также