Особая проблема со вставкой btree

Question

Я играл с очень классным апплетом btree на 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,] ... Почему?

Answer 1

Картинка стоит тысячи слов; анимация стоит миллион:

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.

Answer 2

Каждый узел всегда имеет n + 1 дочерних элементов, где n - количество ключей в этом узле.

Перед разбиением, узел [30, 50] имеет два ключа и три дочерних элемента, как и ожидалось. Когда вы разделяете это, вы получаете узел [30, -] и узел [65, -] (и толкаете 50 вверх на уровень).

На следующем уровне ниже у вас есть (ранее существовавшие) [16, 27] и [45, -], а также недавно разделенные узлы [55, -] и [70, -].

У вас есть два родительских узла и четыре дочерних узла. У каждого родителя должно быть двое детей, потому что у него один ключ. Поэтому, учитывая правила упорядочения, [45, -] должно быть потомком [30, -], потому что в противном случае (1) [30, -] не будет достаточно детей, и (2) [ 65, -] было бы слишком много детей. [ EDIT - незаконно не слишком много для узла, но разделение предполагается сбалансированным].

Воля А также верна. Это является следствием выбора нажатия клавиши 50 при разделении узла среднего уровня, но на самом деле это не был выбор. Расщепление для получения [-, -] и [50, 65] с повышением на 30, или [30, 50] и [-, -] с увеличением до 65 нарушило бы правило, согласно которому каждый узел должен быть заполнен как минимум наполовину.

Answer 3

Нет смысла для 45-го узла быть дочерним по отношению к 65-му узлу на второй диаграмме, поскольку самая правая ветвь предназначена для значений> 50 (на основе крайнего правого значения корневого узла) - поэтому 45 нужно перейтисредняя ветка где-то.