Почему узел вставляется при вставке в 2-3-4 дерева?
В изображенном дереве 2-3-4 ниже (из Data Structures & Algorithm в Java, 2-е изд), почему вставка 99 вызвать разделение узлов 83/92/104 когда кажется 99 мог быть вставлен в правильного ребенка (C ребенок, на месте сразу после 97) без расщепления сделано?
2 ответа
Вставка 99 в C была бы приемлемой, так как она поддерживала бы все инварианты, но алгоритм в целом проще, если вставка всегда расширяет 4-узлы на пути вниз. Тогда всегда найдется место для любого необходимого подъема и поворотов. Это может помочь сравнить случай, когда C уже является 4-узлом.
Чтобы сохранить дерево сбалансированным, чтобы гарантировать производительность. Вставка является рекурсивной, и она попадает в 4-узел (узел с 3 значениями и 4 дочерними элементами), что приведет к выполнению разбиения.