Порядок размещения деревьев B +

Как может измениться высота дерева B + в разных порядках размещения?

Например, для заданных значений n и двух разных порядков вставки. Какую максимальную разницу я могу получить между двумя построенными деревьями?


data-structures tree b-tree
person user550413    schedule 12.12.2011    source источник

Ответы (1)


arrow_upward
3
arrow_downward

В лучшем случае высота B + -дерева (или любого B-дерева) составляет log m n. Высота в наихудшем случае составляет log m / 2 n. (Согласно Википедии)

Максимальная разница, которую вы можете получить, составляет worstCase - bestCase, что составляет log m / 2 n - log m n, что сводится к

log m n (1 / (1 - log m 2) - 1)

(m представляет максимальное количество дочерних элементов, которые может иметь один узел дерева)

person Pops    schedule 12.12.2011