Порядок b-деревьев

Я готовлюсь к экзамену и обнаружил B-деревья. Википедия описывает B-дерево как дерево, узлы которого имеют не менее d и не более 2d ключей и, следовательно, не более 2d + 1 лист. Например, если d = 1, у него будет максимум 2 ключа и 3 дочерних элемента, что сделает его 2-3 деревом. Однако это не позволит, например, создать дерево 2-3-4, если я не ошибаюсь.

Однако наш материал описывает b-дерево как дерево, в котором каждый узел имеет не менее t> = 2 t-1 ключей и максимум 2т-1 ключей. Это означало бы, что узлы имеют нечетное количество ключей и четное количество дочерних элементов. Например, t = 2 будет иметь от 1 до 3 ключей и до 4 дочерних элементов, что сделает его 2-3-4 деревом. С другой стороны, не может быть дерева 2-3 с такой нотацией.

Вдобавок к этому есть нотация Кнута, где d будет означать максимальное количество потомков в узле. Эта запись допускает как четное, так и нечетное число дочерних элементов, позволяя как 2-3 дерева, так и 2-3-4 дерева.

Я знаю, что существуют и 2-3 дерева, и 2-3-4 дерева.

Что такое настоящие обозначения? Есть настоящие обозначения? Как дополнительный вопрос; каково максимальное количество ключей в дереве размером h?

5
задан Robin Green 12 May 2011 в 21:19
поделиться