Конкретная проблема со вставкой B-дерева
Я играл с очень прохладным апплетом B-дерева по slady.net. Я испытываю затруднения при понимании особого поведения. Смотрите на это начальное состояние:
сопроводительный текст http://www.freeimagehosting.net/uploads/db2931c7da.jpg
Это конкретное состояние прибылось путем вставки следующей последовательности: 10, 15, 30, 16, 70, 1, 9, 27, 45, 50, 55.
Мой вопрос расценивает то, что происходит с эти [45], узел, когда я вставляю следующее значение в последовательность, 65.
сопроводительный текст http://www.freeimagehosting.net/uploads/3b70c1d302.jpg
[55,70] узел будет разделен этими 65 и быть средним значением, эти 65 переместятся, создают резервную копию и затем разделяют [30,50] узел также. Мой вопрос: Почему эти [45], узел заканчивается ребенок эти [30], узел? Это - родитель, первоначально имел 3 детей, левые больше всего и право больше всего стали новыми отдельными узлами. Эти 45 были между теми значениями, и кажется, что это, возможно, закончилось под эти [65], узел точно также... Почему?
3 ответа
Картинка стоит тысячи слов; анимация стоит миллион:
http://constellationmedia.com/~funsite/static/btree-insert-animation.gif
Главное, на что следует обратить внимание, это то, что когда центральный узел 50 поднимается вверх, он должен выбросить своего правого ребенка, потому что он слишком далеко вниз. Однако 65 нужен новый левый дочерний элемент, поэтому 50 передает 45 на 65. 50 теперь нужен новый правый дочерний элемент, а узел, содержащий 65, должен быть заморожен, поэтому он занимает вновь сформированное 65 на своем месте.
Вот проиллюстрированные правила вставки B-дерева (где максимальный размер узла составляет 4 элемента, 5 дочерних узлов):
http://constellationmedia.com/~funsite/static/btree-insertion-rules.png
xr не будет существовать и не будет иметь значения, если вы вставляете в лист (что вы делаете в первую очередь). Однако, если вам нужно разделить узел пополам, новый x будет центральным элементом, который вы вытащили, а новый xr - правым дочерним элементом x ].
Нет смысла для узла 45 быть дочерним узлом 65 на второй диаграмме, поскольку самая правая ветвь предназначена для значений> 50 (на основе самого правого значения корневого узла) - так что 45 должно где-то перейти в среднюю ветвь.
У каждого узла всегда есть n + 1 дочерний узел, где n - количество ключей в этом узле.
Перед разделением узел [30, 50], как и ожидалось, имеет два ключа и три дочерних элемента. Когда вы разделите это, вы получите узел [30, -] и узел [65, -] (и поднимите 50 на уровень выше).
На следующем уровне ниже у вас есть (ранее существовавшие) [16, 27] и [45, -], а также недавно разделенные узлы [55, -] и [70, -].
У вас есть два родительских узла и четыре дочерних узла. У каждого родителя должно быть двое детей, потому что у него единственный ключ. Следовательно, с учетом правил упорядочивания, [45, -] должен быть дочерним по отношению к [30, -], потому что в противном случае (1) [30, -] не будет иметь достаточно детей и (2) [ 65, -] будет слишком много детей. [ РЕДАКТИРОВАТЬ - не слишком много для узла незаконно, но предполагается, что разделение будет сбалансировано].
Воля А также верна. Это следствие выбора нажатия клавиши 50 при разделении узла среднего уровня, но на самом деле это не было выбором. Разделение, чтобы произвести либо [-, -] и [50, 65] подталкивание вверх 30, либо [30, 50] и [-, -] выталкивание вверх 65, нарушит правило, согласно которому каждый узел должен быть заполнен как минимум наполовину.