Порядок вставки деревьев B +

Question

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

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

Answer 1

Наилучшая высота дерева 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 представляет максимальное число дочерних элементов, которое может иметь один узел дерева)