Почему мы не используем 2-3 или 2-3-4-5 деревьев?
У меня есть общее представление о том, как 2-3-4 дерева поддерживают операцию свойства баланса высоты после операции, чтобы гарантировать, что даже наихудшие операции выполняются O(n logn).
Но я не понимаю этого достаточно хорошо, чтобы знать, почему только 2-3-4?
Почему не 2-3 или 2-3-4-5 и т. Д.?
3 ответа
Реализация 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) для дерева.
Если честно, я не знал о 2-3-4 деревьях. В моем классе Data Structures нас учили 2-3 дерева, и, честно говоря, большинство из нас реализовали деревья AVL для мокрой части упражнения.
Но, по-видимому, существует обобщение этого типа дерева: (а, б) дерево.
На моем курсе алгоритмов нам сказали, что они обычно используются для доступа к памяти с жесткого диска - известные как B/B+ деревья. Вы создаете дерево, в котором хранится размер вашего доступного ОЗУ, и тем самым вы минимизируете количество тростников от операции с диском (если вы создали B с узлом, который хранит, например, 10^8 элементов, вам нужно только log_10^8 (n) тростника от операции с диском до найти на жестком диске что-то, что не является ничем.Так что то, что вы назвали деревьями 2-3-4-5-..., на самом деле является распространенным решением.