Для реализации 2-3-4 деревьев обычно требуется либо несколько классов (2NODE, 3NODE, 4NODE), либо у вас есть только NODE с массивом элементов. В случае нескольких классов вы тратите много времени на создание и уничтожение экземпляров узлов, а их переучивание становится громоздким. Если вы используете один класс с массивами для хранения элементов и дочерних элементов, то вы либо постоянно меняете размеры массивов, что также приводит к расточительным затратам, либо вы тратите впустую больше половины своей памяти на неиспользуемые элементы массива. Это просто не очень эффективно по сравнению с красно-черными деревьями.
Красно-черные деревья имеют только один тип структуры узлов. Поскольку красно-черные деревья имеют двойственность с 2-3-4 деревьями, деревья RB могут использовать те же алгоритмы, что и 2-3-4 дерева (нет необходимости в глупо запутанных / сложных реализациях, описанных в Cormen, Leiserson and Rivest, которые привели деревьям АА, которые не менее сложны, чем алгоритм 2-3-4.)
Итак, красно-черные деревья для простоты реализации плюс эффективность использования памяти и процессора. (Деревья AVL тоже хороши. Они производят более хорошо сбалансированные деревья и глупы просто для кодирования, но имеют тенденцию быть менее эффективными из-за слишком частой работы, чтобы поддерживать только немного более компактное дерево.)
Да, и 2-3-4-5-6 ... и т.д. не сделано, потому что ничего не получено. У 2-3-4 есть чистый выигрыш по 2-3 деревьям, потому что они могут быть легко сделаны без рекурсии (рекурсия имеет тенденцию быть менее эффективной, особенно когда она не может быть закодирована хвостово-рекурсивно). Тем не менее, B-деревья и Bplus-деревья являются в значительной степени деревьями 2-3-4-5-6-7-8-9 и т. Д., Где максимальный размер узлов n выбирается так, чтобы n записей можно было хранить в один сектор диска. (т. е. каждый сектор диска является узлом в дереве, а размер сектора эквивалентен количеству элементов, хранящихся в узле.) Это связано с тем, что время поиска 512 записей, линейно находящихся в памяти, по-прежнему НАМНОГО быстрее, чем перемещение вниз уровень в дереве, который требует другого поиска / извлечения диска. и O (512) все еще является O (1) и, таким образом, поддерживает O (lg n) для дерева.