Математическое доказательство для двоичного дерева

Question

Я не скрываю, что это часть моей домашней работы, но я пробовал достаточно, прежде чем публиковать здесь.

So ...
Мне нужно доказать для двоичного дерева, что узел k имеет свой левый дочерний элемент на 2k и правый дочерний элемент на 2k + 1 позиции. Я доказал это с индукцией.

Теперь мне нужно доказать для двоичного дерева, что узел k имеет свой родительский элемент на позиции (floor)(k/2). Я взял два дела.
Пробовал и с индукцией. Это верно для дерева из трех узлов.
Если это верно для узла к докажу для узла к + 1.

1. Если узел K + 1 акции родителя с узлом K это, очевидно, верно.
2. Если узел к + 1 имеет разность родителя с узлом к ​​....

Я пытаюсь сделать общее бинарное дерево, но типы не поможет мне использовать предположение индукции. Я предполагаю, может быть, мне придется использовать то, что я раньше доказывал для положения ребенка.

Любая помощь?

Answer 1

Итак, вы доказали, что k-й узел имеет детей в 2k и 2k + 1. Затем разделим детей на два случая, даже и нечетные.

Для детей даже они расположены в i = 2k для некоторых k. Вы можете видеть, что это означает, что его родительский элемент находится в k, или i/2, или на полу (i/2).

Для нечетных детей они расположены в i = 2k + 1 для некоторого k. Вы можете видеть, что это означает, что его родительский элемент находится в точке k. (i/2) в этом случае равен полу (k + 1/2), что равно полу (k) = k, так как k является целым числом, поэтому здесь также находится родительский узел (i/2).

Поскольку множество всех нечетных и даже дети составляют все дети, родитель-го ребенка этаж (я/2)

QED? Извините, если это не строго или формально.