сбалансированное по весу дерево - это двоичное дерево, в котором для каждого узла число узлов в левом поддереве составляет не менее половины и не более чем вдвое больше количества узлов в правом поддереве. Максимально возможная высота (число узлов на пути от root до самого дальнего листа) такого дерева на n узлах лучше всего описывается с помощью какого из следующих элементов:
A. log2 (n)
B. log4 / 3 (n)
C. log3 (n)
D. log3 / 2 (n)
My Try:
Число узлов в левом поддереве составляет не менее половины и самое большее, вдвое больше количества узлов в правом поддереве.
В дереве n узлов, один узел равен root, теперь осталось n-1 узлов. чтобы получить максимальную высоту дерева, мы разделим эти (n-1) узлы на три части размером n-13 каждая. Теперь оставим две части в LST и одну часть в RST. LST = 2 ∗ (n − 1) / 3 и RST = (n − 1) / 3
Следовательно, T (n) = T (2/3 (n-1) + (n-1) ) / 3) и для максимальной высоты мы будем рассматривать только H (n) = H (2/3 (n-1)) + 1 и H (1) = 0. Я пытался решить H (n) повторение с помощью подстановки, но я застрял в точке: 2 ^ k / 3 ^ k (nk) = 1 Вот как решить для k? Пожалуйста, помогите