Вот как следует обращаться с указателями. это ваше дерево 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 в корне. так как корень не имеет места, он также будет разделен. средняя клавиша - 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]
Congrats! Вы сделали вставку. на бумаге это может показаться простым, но я должен признать, что это немного сложнее при кодировании.
Существует несколько способов представления этих key-node элементов в памяти. мой подход заключается в том, что каждый элемент key-node имеет правый указатель с ключом. поэтому каждый внутренний узел будет иметь массив key-node с. таким образом, ключи и указатели узлов всегда хранятся вместе. Самый левый дочерний элемент обрабатывается отдельным левым указателем, этот указатель сохраняется на каждом внутреннем узле и никогда не является нулевым (после завершения операций).