Интуитивный вывод формул для нахождения i-го дочернего узла узла в полном дереве с обходным номером

Question

В моем ответе answer на this я использовал две формулы, к которым я пришел специальными средствами, и я нахожусь в потеря для простого объяснения того, почему эти формулы работают. Здесь проблема в полном объеме:

Рассмотрим perfect или полное K -ичного дерево высоты H, где каждый узел помечаются их рангом в ширину-первых обход, и его сопряженное, где каждый узел помечены в глубине-первом порядке. Ниже приведен пример с К = 2, H = 2:

_ 0 _     _ 0 _ 
/ \    / \ 
    1  2    1  4 
/\ /\   /\ /\ 
3 4 5 6   2 3 5 6 

Для BF-упорядоченных дерева, я -м дочерним узлом N на глубине D определяется по формуле:

K*N + 1 + i

Для DF-упорядоченного дерева, I -м дочерним узлом N на глубине D определяется по формуле:

N + 1 + i*step, where step = (K^(H - D) - 1)/(K - 1)

Что такое интуитивное объяснение этих формул?

Формула, упорядоченная по BF, имеет смысл для меня, когда вы смотрите на любой нарисованный вручную пример, но я не могу сказать словами, почему он работает. В DF-упорядоченном случае, лучшее, что можно придумать это:

Для узла N на глубине D в ДФС-нумерованный К -ичный дерева высоты H , его первый ребенок - это просто N + 1, потому что это следующий узел, который нужно посетить в первом прохождении по глубине. Второй ребенок N будут приходить непосредственно после посещения весь суб-дерево с корнем в первого ребенка (N + 1), который сам по себе полный К -ичный дерево высоты H - (D + 1). Размер любого полного, K-дерева определяется суммой конечной геометрической серии, как описано here. Размер указанного поддерева - это расстояние между первым и вторым детьми и, фактически, это то же расстояние между всеми братьями и сестрами, поскольку каждый из их поддеревьев имеет одинаковый размер. Если мы называем это расстояние step, то:

первого ребенком является N + 1 второго ребенка N + 1 + step третьего ребенка N + 1 + step + step ... и так далее.

Может ли кто-нибудь дать лучшее объяснение того, как и почему эти формулы работают?

Answer 1

Для BFS:

Если узел N находится на глубине D и есть a узлы до N на глубине D (и b узлы после):

N = K^0 + K^1 + ... + K^(D-1) + a 

Сколько узлов будут промаркированы перед его первый ребенок? Остальные узлы b находятся на глубине D и a * K «дочерние» узлы на глубине D+1, которые придут раньше. Так что, если C является метка первого ребенка N:

C = N + b + a * K + 1 
C = K^0 + K^1 + ... + K^(D-1) + a + b + a * K + 1 
C = K^0 + K^1 + ... + K^(D-1) + K^D + a * K 

Действительно есть K^D узлы на глубине D так a + b + 1 = K^D, для них:

C = 1 + (K^0 + ... + K^(D-2) + K^(D-1) + a)* K 
C = 1 + N*k 

Для ДПП:

Чтобы вычислить размер шага, который вы должны вычислить размер оставшегося древовидного дерева, и как поддерево совершенного дерева K-ary, само по себе является идеальным K-арным деревом, вы можете вычислить его количество узлов.