В каком порядке вы должны вставить набор известных ключей в B-Tree, чтобы получить минимальную высоту?

Ответ 1

Следующий трюк должен работать для большинства упорядоченных деревьев поиска, предполагая, что данные для вставки - это целые числа 1..n.

Рассмотрим двоичное представление ваших целых ключей - для 1..7 (с точками для нулей), которые...

Bit : 210
  1 : ..1
  2 : .1.
  3 : .11
  4 : 1..
  5 : 1.1
  6 : 11.
  7 : 111

Бит 2 изменяется чаще всего, бит 0 изменяется чаще всего. Это противоположность тому, что мы хотим, так что, если мы отменим порядок этих бит, а затем отсортируем наши ключи в порядке этого значения с битовым изменением...

Bit : 210    Rev
  4 : 1.. -> ..1 : 1
  ------------------
  2 : .1. -> .1. : 2
  6 : 11. -> .11 : 3
  ------------------
  1 : ..1 -> 1.. : 4
  5 : 1.1 -> 1.1 : 5
  3 : .11 -> 11. : 6
  7 : 111 -> 111 : 7

Проще всего это объяснить с точки зрения несбалансированного дерева двоичного поиска, растущего путем добавления листьев. Первый элемент - мертвый центр - это именно тот предмет, который мы хотим для корня. Затем добавим ключи для следующего слоя вниз. Наконец, мы добавляем слой листа. На каждом шаге дерево так же сбалансировано, как и может быть, поэтому даже если вы создаете сбалансированное дерево AVL или красно-черного цвета, логику перебалансировки никогда не следует вызывать.

[ EDIT Я понял, что вам не нужно сортировать данные на основе этих значений с битовым обращением, чтобы получить доступ к ключам в этом порядке. Хитрость заключается в том, чтобы заметить, что бит-реверсирование является его собственным обратным. Помимо сопоставления клавиш с позициями, он сопоставляет позиции с ключами. Поэтому, если вы переходите через 1..n, вы можете использовать это значение с битовым изменением, чтобы решить, какой элемент вставить дальше - для первой вставки используйте 4-й элемент, для второй вставки используйте второй элемент и так далее. Одно осложнение - вам нужно округлить n вверх до одного меньше, чем два (7 в порядке, но используйте 15 вместо 8), и вы должны ограничить - проверьте значения, восстановленные по биту. Причина в том, что бит-вспять может переместить некоторые позиции в границах за пределы и наоборот.]

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

Для дерева B высота дерева увеличивается путем добавления нового корня. Таким образом, доказательство этих работ немного неудобно (и для этого может потребоваться более тщательный node -сложение, чем обычно требуется дерево B), но основная идея такая же. Несмотря на то, что происходит перебалансировка, это происходит сбалансированным образом из-за порядка вставок.

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

ПРЕДУПРЕЖДЕНИЕ. Это не эффективный способ построения идеально сбалансированного дерева из уже известных отсортированных данных.

Если у вас уже отсортированы ваши данные и знаете его размер, вы можете построить идеально сбалансированное дерево в O (n) времени. Здесь некоторый псевдокод...

if size is zero, return null
from the size, decide which index should be the (subtree) root
recurse for the left subtree, giving that index as the size (assuming 0 is a valid index)
take the next item to build the (subtree) root
recurse for the right subtree, giving (size - (index + 1)) as the size
add the left and right subtree results as the child pointers
return the new (subtree) root

В принципе, это определяет структуру дерева на основе размера и пересекает эту структуру, создавая фактические узлы на этом пути. Это не должно быть слишком сложно адаптировать для B деревьев.

Ответ 2

Вот как я добавил элементы в b-tree.

Благодаря Steve314, для того, чтобы дать мне начало с двоичным представлением,

Заданы n элементов для добавления в порядке. Мы должны добавить его в b-дерево m-order. Возьмите их индексы (1... n) и преобразуйте их в радиус m. Основная идея этой вставки заключается в том, чтобы вставить число с самым высоким битом m-radix в настоящее время и сохранить его выше меньших чисел m-radix, добавленных в дерево, несмотря на разделение узлов.

1,2,3.. являются индексами, поэтому вы фактически вставляете числа, на которые они указывают.

For example, order-4 tree
      4       8         12           highest radix bit numbers
1,2,3   5,6,7   9,10,11    13,14,15  

Теперь в зависимости от медианного порядка может быть:

• порядок четный → число ключей нечетное → медиана средняя (средняя медиана)
• порядок нечетный → число ключей равно → медиана медианной или правой медианной

Выбор медианного (левого/правого) для продвижения будет определять порядок, в котором я должен вставлять элементы. Это должно быть исправлено для b-дерева.

Я добавляю элементы в деревья в ведрах. Сначала я добавляю элементы ковша, а затем по завершении следующего ведра по порядку. Ведра могут быть легко созданы, если медиана известна, размер ковша - порядка m.

I take left median for promotion. Choosing bucket for insertion.
    |  4     |  8      |   12       |    
1,2,|3   5,6,|7   9,10,|11    13,14,|15  
        3       2          1             Order to insert buckets.

• Для левого медианного выбора я вставляю ведра в дерево, начиная с правой стороны, для выбора правой медианности я вставляю ведра с левой стороны. Выбирая левую медианную, сначала вставляем медианную, затем элементы слева от нее, затем остальную часть чисел в ведре.

Пример

Bucket median first
12,
Add elements to left
11,12,
Then after all elements inserted it looks like,
|   12       | 
|11    13,14,| 
Then I choose the bucket left to it. And repeat the same process.
Median
     12        
8,11    13,14, 
Add elements to left first
       12        
7,8,11    13,14, 
Adding rest
  8      |   12        
7   9,10,|11    13,14, 
Similarly keep adding all the numbers,
  4     |  8      |   12        
3   5,6,|7   9,10,|11    13,14, 
At the end add numbers left out from buckets.
    |  4     |  8      |   12       |   
1,2,|3   5,6,|7   9,10,|11    13,14,|15 

• Для средних медианных (даже ордеров b-деревьев) вы просто вставляете медиану, а затем все числа в ведро.

• Для правого медиана я добавляю ведра слева. Для элементов внутри ведра я сначала вставляю медианные, затем правые элементы, а затем левые элементы.

Здесь мы добавляем самые высокие числа m-radix, и в процессе я добавил числа с немедленным меньшим битом m-radix, убедившись, что самые высокие номера m-radix остаются на вершине. Здесь у меня только два уровня, для большего количества уровней я повторяю один и тот же процесс в порядке убывания бит-бита.

В последнем случае оставшиеся элементы имеют один и тот же бит radix и нет чисел с меньшим радическим битом, а затем просто вставляют их и завершают процедуру.

Я бы привел пример для трех уровней, но это слишком долго, чтобы показать. Поэтому, пожалуйста, попробуйте другие параметры и сообщите, работает ли он.

Ответ 3

Чтобы создать конкретное B-дерево, используя Insert() как черный ящик, работайте назад. Учитывая непустое B-дерево, найдите node с более чем минимальным количеством детей, максимально приближенным к листьям. Корень считается минимальным 0, поэтому node с минимальным количеством детей всегда существует. Удалите значение из этого node, которое должно быть добавлено к списку вызовов Insert(). Работайте с листьями, объединяя поддеревья.

Например, учитывая 2-3 дерева

       8
   4       c
 2   6   a   e
1 3 5 7 9 b d f,

мы выбираем 8 и делаем слияния для получения предшественника

   4      c
 2   6  a   e
1 3 5 79 b d f.

Тогда выберем 9.

   4     c
 2   6 a   e
1 3 5 7 b d f

Тогда a.

    4    c
 2    6    e
1 3  5 7b d f

Тогда b.

   4   c
 2   6   e
1 3 5 7 d f

Тогда c.

   4
 2   6  e
1 3 5 7d f

Et cetera.

Ответ 4

Итак, существует ли конкретный способ определения последовательности вставки, которая уменьшила бы потребление пространства?

Изменить примечание: поскольку вопрос был довольно интересным, я пытаюсь улучшить свой ответ с помощью немного Haskell.

Пусть k - порядок Кнута B-дерева и list список ключей

Минимизация потребления пространства имеет тривиальное решение:

-- won't use point free notation to ease haskell newbies
trivial k list = concat $ reverse $ chunksOf (k-1) $ sort list

Такой алгоритм будет эффективно создавать неэффективное время B-Tree, неуравновешенное слева, но с минимальным потреблением пространства.

Существует множество нетривиальных решений, которые менее эффективны для производства, но показывают лучшую производительность поиска (меньшая высота/глубина). Как вы знаете, все о компрометации!

Простой алгоритм, который минимизирует глубину B-дерева и потребление пространства (но не работает минимизировать производительность поиска!), выглядит следующим образом

-- Sort the list in increasing order and call sortByBTreeSpaceConsumption 
-- with the result
smart k list = sortByBTreeSpaceConsumption k $ sort list

-- Sort list so that inserting in a B-Tree with Knuth order = k 
-- will produce a B-Tree  with minimal space consumption minimal depth 
-- (but not best performance)
sortByBTreeSpaceConsumption :: Ord a => Int -> [a] -> [a]
sortByBTreeSpaceConsumption _ [] = []
sortByBTreeSpaceConsumption k list
    | k - 1 >= numOfItems = list  -- this will be a leaf
    | otherwise = heads ++ tails ++ sortByBTreeSpaceConsumption k remainder
    where requiredLayers = minNumberOfLayersToArrange k list
          numOfItems = length list
          capacityOfInnerLayers = capacityOfBTree k $ requiredLayers - 1
          blockSize = capacityOfInnerLayers + 1 
          blocks = chunksOf blockSize balanced
          heads = map last blocks
          tails = concat $ map (sortByBTreeSpaceConsumption k . init) blocks
          balanced = take (numOfItems - (mod numOfItems blockSize)) list
          remainder = drop (numOfItems - (mod numOfItems blockSize)) list

-- Capacity of a layer n in a B-Tree with Knuth order = k
layerCapacity k 0 = k - 1
layerCapacity k n = k * layerCapacity k (n - 1)

-- Infinite list of capacities of layers in a B-Tree with Knuth order = k
capacitiesOfLayers k = map (layerCapacity k) [0..]

-- Capacity of a B-Tree with Knut order = k and l layers
capacityOfBTree k l = sum $ take l $ capacitiesOfLayers k

-- Infinite list of capacities of B-Trees with Knuth order = k 
-- as the number of layers increases
capacitiesOfBTree k = map (capacityOfBTree k) [1..]

-- compute the minimum number of layers in a B-Tree of Knuth order k 
-- required to store the items in list
minNumberOfLayersToArrange k list = 1 + f k
    where numOfItems = length list
          f = length . takeWhile (< numOfItems) . capacitiesOfBTree

С помощью этой функции smart, заданной a list = [21, 18, 16, 9, 12, 7, 6, 5, 1, 2] и B-Tree с порядком knuth = 3, мы должны получить [18, 5, 9, 1, 2, 6, 7, 12, 16, 21] с полученным B-Tree как

              [18, 21]
             /
      [5 , 9]
     /   |   \
 [1,2] [6,7] [12, 16]

Очевидно, что это субоптимально с точки зрения производительности, но должно быть приемлемым, поскольку получение лучшего (например, следующего) было бы намного более дорогостоящим (вычислительным и экономическим):

          [7 , 16]
         /   |   \
     [5,6] [9,12] [18, 21]
    /
[1,2]

Если вы хотите запустить его, скомпилируйте предыдущий код в файле Main.hs и скомпилируйте его с помощью ghc после добавления

import Data.List (sort)
import Data.List.Split
import System.Environment (getArgs)

main = do
    args <- getArgs
    let knuthOrder = read $ head args
    let keys = (map read $ tail args) :: [Int]
    putStr "smart: "
    putStrLn $ show $ smart knuthOrder keys
    putStr "trivial: "
    putStrLn $ show $ trivial knuthOrder keys

Ответ 5

К сожалению, все деревья демонстрируют наихудший сценарий времени работы сценария и требуют жестких методов балансировки, когда данные вводятся в таком порядке. Бинарные деревья быстро превращаются в связанные списки и т.д.

Для типичных случаев использования B-Tree (базы данных, файловые системы и т.д.) вы обычно можете рассчитывать на то, что ваши данные, естественно, будут более распределены, создавая дерево больше похоже на ваш второй пример.

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

for( i=1; i<8; ++i )
    tree.push(hash(i));