Peter Almazov писал(а):
Второй раз не понял. Что мешает посмотреть здесь
Не мешает ничего. Просто не помогает ни на копейку
Ну посмотрел, и чего ???
Точно с таким же успехом посмотрел таблицу значений истинности логических операторов - ну не могу я поверить, что студентам-швейцарцам на лекциях давали именно эту таблицу.
Не укладывается у меня в голове, чтобы мэтр Вирт подошел к доске и своими руками написал мелом на доске такой бред. Правду писал, скорее всего...
А вот про вывод вышеозначенных формулок - нет у меня уже определенного мнения про аналогичное "скорее всего"...
Вот и выходит, что из того факта, что англоязычный вариант соответствует бумажному - никакого вывода сделать не получается
Peter Almazov писал(а):
Просьба все-таки пояснить на примере. Пусть деревья строятся из ключей 1..2, т.е. из последовательностей {1,2},{2,1}. Какова будет средняя длина дерева?
Хм..
На дереве из двух элементов объяснять крайне сложно
Давайте из трех... А для себя в памяти зафиксируем, что средняя глубина дерева из одного элемента =0, а из двух - =1/2. Потому-что для двух -
равновероятны случаи попадания в корень (глубина=0), и в боковой уэел (глубина=1), что и дает 1/2-ю в среднем.
Ну смотрим... Дерёвы бывают разные: корневым узлом может быть узел 1, 2, или 3.
Рассмотрим для примера случай для корня =2. У этого корня могут быть левое поддерево их одного элемента (в общем случае из (i-1)-го элемента), и правое поддерево тоже из одного элемента (в общем случае из (n-i) элементов). А у нас в памяти зафиксировано, что средняя глубина деревьев из одного элемента =0. Но если мы кидаем на поиск цифрьки, уходящие в эти поддеревья, то длина пути будет вовсе не ноль (что соответствует формуле из AD), а единице - у нас же есть реальное ребро от узла 2 к узлу 1 (ну или 3)
В результате: кидаем 1 - глубина 1+0, кидаем 2 - глубина 0, кидаем 3 - глубина 1+0, средняя, соответственно A2[3]= 2/3
Далее рассмотрим случай для корня =1. У нас только одно правое поддерево из 2-х элементов (помним, что для этого поддерева - средняя глубина =1/2)
В этом случае: кидаем 1 - глубина 0, кидаем 1 - глубина 1+1/2, кидаем 3 - глубина 1+1/2, средняя, соответственно A1[3]=(0+3/2+3/2)/3=1
Для случая корня =3 - все симметрично предыдущему случаю с теми же цифрами A3[3]=A1[3]=1
Если усредним по этим трем дерёвам, то получим A[3]=(1 + 2/3 + 1)/3=8/9
Ну вот, как-то так... В общем же случае будет:
Ai[n] = ((i-1)*(A[i-1]+1) + (n-i)*(A[n-i])+1)/n, где "плюс одыны" соответствуют ребрам, выходящим из корня на рис.4.29
Ну и наконец, возводя аккуратность в религию, сверяем конечную формулу с нашими цифирьками:
A[2]=2*(H(2)*(2+1)/2-2) = 1/2, и
A[3]=2*(H(3)*(3+1)/3-2) = 8/9.
И испытываем от этого чувство глубокого удовлетворения.