Вероятность и статистика

Чтобы найти наименьшее и наибольшее количество концевых вершин (листов) в дереве с 71 вершиной, рассмотрим два случая:

Наименьшее количество концевых вершин: Для наименьшего количества концевых вершин дерево должно быть максимальной высоты, то есть у каждой вершины должно быть только одно дочернее ребро. Это приводит к линейному дереву, в котором имеется всего два листа. Таким образом, наименьшее число концевых вершин в дереве с 71 вершиной равно 2.

Наибольшее количество концевых вершин: Для наибольшего количества концевых вершин дерево должно быть "разветвленным", то есть каждая вершина (кроме листов) должна иметь столько потомков, сколько возможно. Если рассматривать, что каждая вершина может иметь максимум два потомка, кроме последних, то это будет "полное двоичное дерево". В этом случае примерно половина вершин будут листьями, что составляет наибольшее количество листьев.

Используя следующее правило для полного двоичного дерева:

Количество листьев = (n + 1) / 2

Где nn — количество вершин. Подставим n=71n = 71:

Количество листьев = (71 + 1) / 2 = 36 листьев.

Таким образом, в дереве с 71 вершиной наименьшее количество концевых вершин равно 2, а наибольшее — 36.