Вот как следует обращаться с указателями. это ваше дерево B+ перед вставкой. (некоторые отступы используются для облегчения просмотра указателей)
[21 30 50]
/ \ \ \
[10|20|-] => [21|22|25] => [30|40|-] => [50|60|80]
После вставки 23 у вас будет 2 узла. Важно знать, что разделение слева должно быть всегда одним и тем же экземпляром, а разделение справа должно быть новым узлом. это несколько упростит работу с указателями.
Таким образом, сплиты должны выглядеть так.
old fresh
[21|22|-] => [23|25|-]
поскольку левый узел является одним и тем же экземпляром, ключ 21 в корне имеет правильный правый указатель. Вот как выглядят узлы до разделения корня и после разделения листа. мы находимся в середине процесса.
[21 30 50]
/ \ \ \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
только новый элемент с ключом 23 должен быть добавлен рядом с 21 в корне. поскольку у root нет места, он также будет разделен. средний ключ — 23 (первый элемент правого разделения).
[21 30] [ 50 ]
/ \ \ * \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Поскольку корень разделен, мы должны добавить наш средний ключ к левому или правому разделению и найти новый средний ключ для продвижения. обратите внимание на нулевой указатель справа. поскольку этот узел свежий, его нужно скоро инициализировать!
(корень был отделен от правого, что означает, что меньше элементов лежит в правом узле в случае нечетного количества элементов. но в целом не имеет значения, как вы разделяете.)
наш средний ключ был 23. так что давайте добавим 23.
[21 23 30] [ 50 ]
/ \ \ \ * \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Хорошо! Если бы здесь не было раздвоения, наша вставка была бы уже закончена. но поскольку на этом уровне есть раскол, мы должны найти новый средний ключ для продвижения. также не забудьте нулевой указатель для нового узла.
(В случае разделения листьев вы должны хранить пары "ключ-значение" в листьях и продвигать копию среднего ключа, но в случае разделения внутренних узлов вы можете безопасно перемещать и продвигать ключи вверх.)
здесь новый средний ключ равен 30. позволяет вытолкнуть его из левого узла.
30
\
[30|40|-]
(Важно, как выбрать средний ключ. Всегда узел, который получает средний ключ из нижних разделений, должен удалить один элемент для нового среднего ключа. Если этот узел является левым узлом, удалите из него последний элемент. , иначе удалить первый элемент.)
[21 23] 30 [ 50 ]
/ \ \ \ * \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Обратите внимание, что 30 не находится ни в одном из расщеплений. это наш средний ключ, с которым мы должны справиться. Всегда ставьте правый узел среднего ключа слева от нового узла.
[21 23] 30 [50]
/ \ \ * / \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Затем правый указатель среднего ключа укажет на новый узел на правом разделении. наконец, продвигается средний ключ, создается новый корень с левым или правым разделением, правым и правым разделением и ключом среднего ключа.
[ 30 ]
/ \
[21 23] [50]
/ \ \ / \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Поздравляю! вы сделали вставку. это может выглядеть легко на бумаге, но я должен признать, что это немного сложно при кодировании.
Есть несколько способов представить эти key-node элементов в памяти. мой подход заключается в том, что каждый элемент key-node имеет правильный указатель с ключом. поэтому каждый внутренний узел будет иметь массив key-nodes. таким образом, ключи и указатели узлов всегда хранятся вместе. левый самый дочерний элемент обрабатывается отдельным левым указателем, этот указатель хранится на каждом внутреннем узле и никогда не становится нулевым (после завершения операций).
person
M.kazem Akhgary
schedule
09.01.2018
