Какова средняя высота бинарного дерева?

10

Есть ли формальное определение средней высоты бинарного дерева?

У меня есть вопрос по нахождению средней высоты двоичного дерева с помощью следующих двух методов:

  1. Естественным решением может быть определение средней длины всех возможных путей от корня до листа, то есть

    AVH1(T)знак равно1# уходит в TΣv лист Tглубина(v) .

  2. Другой вариант - определить его рекурсивно, то есть средняя высота узла - это среднее значение средних высот поддеревьев плюс один, то есть

    AVH2(N(L,р))знак равноAVH2(L)+AVH2(р)2+1

    с для листьев и для пустых слотов.л AVH 2 ( _ ) = 0AVH2(L)знак равно1LAVH2(_)знак равно0

Исходя из моего текущего понимания, например, средняя высота дереваT

    1    
   / \
  2   3
 /
4

is вторым методом, который использует рекурсию.AVH2(T)знак равно1,25

Тем не менее, я все еще не совсем понимаю, как сделать первый. неверно.AVH1(T)знак равно(1+2)/2знак равно1,5

вневременный
источник
1
Можете ли вы предоставить некоторый контекст? Не существует такого понятия, как «правильное» математическое определение; Вы можете определить «среднюю высоту бинарного дерева», как вам нравится. (Среднее из чего по какому распределению ?) Но разные определения будут более или менее полезны для разных приложений.
Джефф
@JeffE "Не сразу очевидно, как определить среднюю высоту бинарного дерева. Возможно, наиболее естественным решением может быть определение средней длины возможных путей от корня до листа. Более простое (возможно, даже упрощенное) решение это значит, что средняя высота узла - это среднее значение средних высот поддеревьев плюс один. Вам будет проще найти код для этой альтернативы. Можете ли вы привести примеры, чтобы продемонстрировать разницу? "
Вневременное
Я постарался сделать ваш пост более понятным, дав точные определения двух вариантов. Пожалуйста, проверьте, правильно ли я интерпретировал ваш текст. В частности, вам не хватало якоря для второго варианта; берете ли вы листья, чтобы иметь высоту один или ноль, имеет значение.
Рафаэль

Ответы:

3

Нет оснований полагать, что оба определения описывают одну и ту же меру. Вы также можете написать рекурсивно:AVH1

AVH1(N(L,р))знак равнолв(L)(avчас1(L)+1)+лв(р)(avчас1(р)+1)лв(L)+лв(р)

AVH1(L)знак равно0LAVH1

AVH1AVH2AVH2AVH1AVH1лв(L)знак равнолв(р)это сразу видно На несбалансированных деревьях, однако, они разные.

Ваши расчеты действительно верны (учитывая ваше определение); обратите внимание, что дерево примеров не сбалансировано по листам.

Рафаэль
источник
AVH1
AVH1
Я имею в виду код реализации с использованием рекурсии
Timeless
@null: Вы можете скопировать формулу почти буквально , если вы включите базовый вариант. Как это сделать, зависит от вашего языка программирования и реализации дерева. Я предлагаю вам вернуться к переполнению стека, если реализация является препятствием для вас.
Рафаэль
2

Редактировать: Джефф делает хорошую точку в своем комментарии выше. Вы, вероятно, должны прочитать «правильный против неправильный» в следующем ответе как «удобный / непротиворечивый против непоследовательный».

Похоже, что ваш второй расчет неверен. Пусть высота поддерева с одним узлом (т.е. листом) равна 0. Тогда высота корня поддерева в:

  • высота в 4 0
  • высота в 3 0
  • высота в 2 - средняя высота в 3 + 1 = 0 + 1 = 1
  • высота в 1 - это средняя высота в 2 и 3 = (0 + 1) / 2 + 1 = 1,5

Я думаю, что вы делаете первый расчет правильно, и 1,5 является правильным ответом.

Джо
источник
Идея - нулевой узел с высотой -1, основанный на втором подходе, средняя высота узла - это среднее из поддеревьев плюс 1, средняя высота узла 4 - ((-1) + (- 1)) / 2 + 1 = 0 средняя высота узла 2 равна (0 + (- 1)) / 2 + 1 = 0,5, поэтому средняя высота корня составляет 1,25.
Вневременное
@null Вы можете определить это таким образом, если вы настаиваете, но тогда два определения не будут согласованы.
Джо