Изучение нового всегда дает возможность полностью поразить ваш разум. Имейте в виду, этого не всегда происходит - по крайней мере, когда дело доходит до области информатики. Однако время от времени вы узнаете что-то, что действительно вас восхищает, что-то, что на самом деле потрясающе в истинном словарном смысле этого слова; что-то такое, что действительно похоже на зажигание лампочки, что заставляет вас чувствовать огромную благодарность за то, что вы с самого начала попытались понять это.
Я, конечно, говорю из личного опыта, потому что именно это случилось со мной, когда я узнал о чудесах деревьев AVL. Оказывается, у информатики есть элементы математики под поверхностью, некоторые из которых мы уже видели в ходе этой серии. Но у математики есть еще один скрытый слой: связь с окружающим нас миром природы.
Часто, когда мы изучаем супертеоретические вещи (например, множество основных концепций информатики), трудно понять, где эти концепции были созданы, почему мы их используем и почему нам это должно быть небезразлично. Понимание истории того, почему что-то было изобретено, так же важно, как понимание его применения и использования. Для нас немного редко можно увидеть, как что-то в информатике напрямую связано с другими областями, которые не имеют ничего общего с вычислениями!
Однако в сегодняшнем посте математика, информатика и природа объединяются самым волшебным образом. Итак, приступим!
Ищем образцы деревьев
На прошлой неделе мы узнали об уникальной структуре данных, называемой AVL-дерево, которая представляет собой тип самобалансирующегося двоичного дерева поиска. Надеюсь, вы помните, что дерево AVL - это дерево со сбалансированной высотой, что означает, что оно следует золотому правилу: ни один лист в дереве не должен иметь значительно более длинный путь от корневого узла, чем любой другой лист дерева.
Об этом золотом правиле важно помнить о том, что по мере роста дерева AVL оно должно иметь минимальное количество узлов на каждом уровне, прежде чем можно будет добавить еще один.
Показанная здесь иллюстрация иллюстрирует это. На этом рисунке мы видим пять разных деревьев AVL, каждое с разной высотой.
В дереве AVL с высотой 0 узлов нет, поэтому n равно 0. В дереве AVL с высотой 1 имеется ровно 1 узла, а в дереве AVL с высотой 2 ровно 2 узлов. Помните, что мы учитываем только минимальное количество узлов. Технически мы могли бы добавить к нашему AVL-дереву третий узел высотой 2, и это все равно было бы хорошо; но нам нужны как минимум минимум два узла, чтобы создать сбалансированное по высоте AVL-дерево с высотой 2.
Что происходит, когда нам нужно создать дерево AVL высотой 3? Что ж, для этого нам нужно как минимум 4 узлов, поскольку нам нужно добавить правильное поддерево, прежде чем мы сможем приступить к добавлению другого уровня. Аналогичная ситуация для дерева с высотой 4: нам нужно 7 узлов, чтобы создать сбалансированное по высоте правое поддерево перед добавлением еще одного узла в левое поддерево.
Давайте сделаем еще один шаг: какое минимальное количество узлов нам нужно, чтобы создать дерево AVL с высотой 5?
Итак, исходя из того, что мы узнали на прошлой неделе о деревьях AVL, мы знаем, что разница между левым и правым поддеревьями не может быть больше одного уровня по высоте. Это означает, что нам нужно будет добавить правое поддерево, прежде чем мы сможем вырастить левое поддерево.
Пример, показанный здесь, показывает, каким будет наш минимальный номер узла для дерева AVL с высотой 5: нам нужно, как минимум, 12 узлов, чтобы создать дерево AVL с высотой 5. Если мы разберем его на части. Далее, мы видим, что нам нужно 7 из этих узлов в левом поддереве и 4 узла для правого поддерева. И, конечно же, нам понадобится узел для корня.
Если мы достаточно долго посмотрим на левое поддерево и правое поддерево, мы заметим, что они кажутся знакомыми. Это потому, что мы видели их минуту назад, когда смотрели на наши AVL-деревья высотой 4 и 3! Эти два дерева просто являются двумя структурами, которые были до дерева AVL с минимальным количеством узлов и высотой 5.
Если вам кажется, что здесь есть интересная закономерность, вы правы.
Высота дерева AVL с минимальным количеством узлов представляет собой комбинацию двух предшествующих ему деревьев AVL минимальной высоты.
Это не уникально для дерева AVL с высотой 5; фактически, если мы посмотрим на предыдущую иллюстрацию и внимательно рассмотрим дерево AVL высотой 4, мы заметим точно такую же закономерность. Левое поддерево дерева AVL с высотой 4 - это дерево AVL с высотой 3, а правое поддерево - дерево AVL с высотой 2.
Мы могли бы даже продолжить рисовать более крупные деревья со сбалансированной высотой и увидеть, как этот узор продолжается, даже если высота дерева становится очень большой.
Итак, как превратить этот паттерн во что-то более абстрактное? Мы выводим этот шаблон из следующей формулы: «высота дерева n эквивалентна сумме высот деревьев n-1 плюс n-2 плюс 1».
Другой способ подумать об этом состоит в том, что минимальное количество узлов для создания дерева высотой n - это объединение двух деревьев, которые идут перед ним, и добавление еще одного узла для корневого узла. Другими словами, чтобы определить минимальное количество узлов, необходимое для создания дерева высотой 10, вам потребуется количество узлов из дерева высотой 9 и высотой 8 плюс один дополнительный узел для корневого узла.
Если мы просуммируем два AVL-дерева перед тем, которое мы ищем, мы сможем программно вычислить минимальное количество узлов, которое нам понадобится для создания любого данного AVL-дерева со сбалансированной высотой.
Вуаля! Мы обнаружили последовательность Фибоначчи прямо у нас под носом!
Нахождение Фибоначчи и золотого сечения
Паттерн суммирования двух чисел для получения третьего числа известен как последовательность Фибоначчи, названная в честь Леонардо Фибоначчи. То, на что наткнулся молодой Леонардо, можно резюмировать как математическую последовательность, которая следует одному правилу, а это именно то, что мы знаем как последовательность Фибоначчи:
каждое число после первых двух чисел является суммой двух предшествующих ему чисел.
Как только у нас есть первые два числа последовательности Фибоначчи, у нас будет достаточно, чтобы построить все (но это продолжается вечно и вечно, поэтому мы просто пропустим это сейчас)! Так уж получилось, что первые два числа запомнить довольно легко: это 0 и 1.
Мы уже знаем, что существует некоторая корреляция между последовательностью Фибоначчи и левым и правым поддеревом AVL-дерева со сбалансированной высотой. А именно, мы знаем, что минимальное количество узлов для дерева с высотой H будет двумя минимальными деревьями узлов, которые идут перед ним, плюс еще один узел для корневого узла.
Поскольку в предыдущем разделе мы вывели формулу для определения высоты дерева на основе количества узлов, можем ли мы использовать последовательность Фибоначчи для определения обратного? Можем ли мы абстрагироваться от формулы, чтобы определить минимальное количество узлов для дерева на основе его высоты?
Конечно можем!
Давайте разберемся с математикой, которая работает здесь за кулисами, и посмотрим, сможем ли мы выяснить, что на самом деле происходит.
На иллюстрации, показанной здесь, мы собираемся сделать обратную формулу, которую вывели ранее, что означает, что мы продолжим работать с деревом с высотой H 5. Если мы ищем n, минимальное количество узлов для дерева высотой H, мы можем найти число Фибоначчи, расположенное в индексе Fibonacci[H+2], и вычесть единицу из него, чтобы определить минимальное количество узлов для создания дерева высотой H.
Итак, в случае дерева с высотой H, равной 5, нам нужно будет найти число Фибоначчи по индексу 5 + 2 или 7. Напомним, что мы проиндексировали нашу последовательность Фибоначчи, начиная с 0 в качестве первого индекса, поэтому элемент с Fibonacci[7] даст нам 13. Поскольку 13 - 1 равно 12, мы знаем, что нам понадобится минимум 12 узлов, чтобы создать дерево высотой 5.
Когда в предыдущем разделе мы нарисовали сбалансированное дерево высотой 5, именно столько узлов у нас было!
Хорошо, а как насчет дерева с высотой H 6? Ну, 6 + 2 это 8, а элемент, расположенный в индексе Fibonacci[8], будет числом 21. Помните, что даже если мы не знаем элемент с индексом Fibonacci[8], мы знаем это Fibonacci[6] = 8 и Fibonacci[7] = 13, что означает, что мы можем суммировать эти два элемента, чтобы получить следующий элемент в последовательности. Начиная с Fibonacci[8] = 21, мы можем вычесть из него единицу и знать, что нам нужно как минимум 20 узлов, чтобы создать сбалансированное по высоте дерево AVL с высотой 6.
Рад! Мы только что перевернули нашу первую формулу, которая использовала паттерн Фибоначчи, на его противоположность ... которая также использует паттерн Фибоначчи!
Хорошо, это круто, но скоро станет еще круче.
Последовательность, которую долгое время приписывали (и называли в честь!) Фибоначчи, на самом деле была открыта сотнями лет назад древнеиндийскими математиками еще в 6 веке. Только после открытия Фибоначчи 600 лет спустя западный мир узнал об этой последовательности и, таким образом, смог изучить ее еще глубже.
По мере того, как все больше математиков, ученых и художников начали изучать эту последовательность, они начали понимать ее глубокую связь с окружающим миром. Одна из вещей, которые они обнаружили, заключалась в том, что последовательность Фибоначчи была очень тесно связана с другим особым свойством в геометрии и математике: золотой спиралью и золотым сечением.
Неясно, когда было обнаружено золотое сечение; хотя именно греческий математик Евклид первым упомянул об этом в своем знаменитом, хорошо изученном и цитируемом тексте Элементы, также весьма вероятно, что древние египтяне использовали его, когда строили пирамиды. ", тысячи лет назад. Золотое сечение часто называют «фи (φ или ϕ), а также оно известно как золотая пропорция Да Винчи. ”. С математической точки зрения, две величины имеют золотое сечение, если соотношение между двумя величинами такое же, как отношение двух суммированных элементов по сравнению с большей из двух величин.
Золотое сечение обычно иллюстрируется на примере прямоугольника, состоящего из квадрата и прямоугольника соответственно.
В примере, показанном выше, мы видим, как работает золотое сечение. Когда мы делим линию на две части так, чтобы вся длина, разделенная на большую часть, была равна большей части, разделенной на меньшую часть, мы получаем золотое сечение. В этой конкретной иллюстрации отношение длинной стороны прямоугольника, сумма a + b, к стороне a будет таким же, как отношение длины из a в сторону b.
Но что такое золотое сечение? Мы сравниваем a и b, но что это на самом деле означает? Что ж, давайте посмотрим на золотое сечение, используя реальные числа, и посмотрим, сможем ли мы получить более конкретный ответ.
Мы знаем, что золотое сечение часто описывают следующим образом:
a + b is to a, as a is to b
Давайте заменим здесь a и b целыми числами: a = 5 и b = 3.
Если a + b относится к a, как a - к b, тогда мы должны быть в состоянии доказать, что отношение 5 + 3 к 5 такое же, как у 5 к 3.
Что ж, пора посчитать и выяснить, так ли это на самом деле!
Начиная с 5 + 3 = 8, мы определяем соотношение здесь, разделив 8/3, что составляет 1.6. Если разделить 5/3, мы получим 1,6, повторяя.
В обоих случаях мы на самом деле очень близко подошли к значению phi (φ), которое представляет собой иррациональное число, которое представляет собой сумму 1 и квадратного корня из 5, деленного на 2. Это иррациональное число примерно приближается к 1.6180339887, часто для краткости обозначается просто 1.618.
Так как же золотое сечение связано с золотой спиралью? Что ж, золотая спираль - это геометрическая логарифмическая спираль, фактор роста которой на самом деле оказывается равным - сюрприз, сюрприз! - золотое сечение. И угадай что? Здесь снова в игру вступает последовательность Фибоначчи!
Если мы построим квадраты с шириной каждого последовательного элемента в последовательности Фибоначчи, мы можем начать строить прямоугольники. Мы заметим, что в каждом из этих прямоугольников есть золотое сечение! И по мере того, как эти прямоугольники растут, начинает появляться спиральная форма.
Мы заметим, что ширина каждого квадрата состоит из двух частей: другого квадрата и прямоугольника, ширина каждого из которых является суммой двух квадратов (двух чисел Фибоначчи), предшествующих ему. Например, ширина квадрата 8, нарисованного розовым цветом, является суммой ширины двух квадратов, предшествующих ему: 5 и 3. Точно так же ширина красного квадрата 13 является суммой двух квадратов, которые были до него: 8 и 5.
Снова появляется последовательность Фибоначчи! Соотношение между каждым из этих квадратов, которое мы использовали для построения нашей золотой спирали, напрямую связано с золотым сечением. Если мы разделим каждое число Фибоначчи на предшествующее ему число, это станет более очевидным.
Обратите внимание, что мы приближаемся к фактическому значению phi (φ) по мере того, как наши числа Фибоначчи увеличиваются в размерах. Мы никогда не попадем в золотое сечение точно, поскольку это иррациональное число; но чем больше у нас число Фибоначчи, тем ближе мы к нему подойдем, сравнивая одно отношение с другим.
Последовательность Фибоначчи и Золотая спираль существуют повсюду вокруг нас - в руках морской звезды, узорах морской ракушки, ветвях дерева - и даже внутри нас - внутри человеческого уха, в пределах пропорций наших пальцев и даже пропорций человеческой руки! Мой личный любимый пример этой последовательности в природе происходит от моего любимого цветка: подсолнечника.
Согласно исследованию Американской ассоциации развития науки
Контрольный признак - это количество различных спиралей семян на лицевой стороне подсолнечника. Подсчитайте спирали по часовой стрелке и против часовой стрелки, которые достигают внешнего края, и вы обычно найдете пару чисел из последовательности: 34 и 55, или 55 и 89, или - с очень большими подсолнухами - 89 и 144. Хотя математика может Будьте красивы, биологи растений не разработали механистическую модель, которая полностью объясняет, как возникают образцы семян подсолнечника.
И угадай что? Есть еще другой способ, которым этот шаблон связан с деревьями AVL, что, возможно, и делает их такими чертовски золотыми.
Время узнать!
Золотое (высота дерева) соотношение
Каков последний лепесток в этом метафорическом цветке Фибоначчи?
Чтобы все это понять, нам нужно вернуться к тому, с чего мы начали: к определению взаимосвязи между минимальным количеством узлов и высотой AVL-дерева. Мы рассмотрели две разные формулы: во-первых, мы выяснили, как определить высоту на основе минимального количества необходимых нам узлов; Затем мы определили количество узлов, которые нам понадобятся, исходя из высоты дерева.
Что ж, оказывается, что последовательность Фибоначчи и золотое сечение находились под поверхностью обеих этих формул все время!
Когда мы использовали минимальное количество узлов в дереве, чтобы определить его высоту, то, что мы на самом деле делали, это брали журнал с базой золотого сечения минимального количества узлов, что дало нам приблизительную высоту дерева. Фактически, именно отсюда и возникает логарифмическая сложность AVL-дерева! Мы просто обычно не ссылаемся на базу, поэтому в большинстве случаев явно не говорится, что мы берем log base 1.618.
Например, когда мы определили, что дерево с минимальным числом узлов 54 даст нам высоту 8, то, что мы на самом деле делали, это взяли базу журнала 1,618 из 54 , что приблизительно дает нам 8,29, что округляется до целого числа 8.
Если бы мы изобразили зависимость между количеством узлов и высотой дерева, мы бы фактически изобразили логарифмическое золотое сечение n, где n - количество узлов в дереве.
Другой способ мышления заключается в том, что отношение между количеством узлов и высотой дерева является логарифмическим.
Поскольку минимальное количество узлов в дереве AVL растет линейно, высота дерева увеличивается логарифмически.
Если вы помните изучение логарифмов ранее в этой серии, то вы можете вспомнить, что логарифмическая функция является обратной по отношению к экспоненциальной функции. Итак, как насчет второй формулы, которую мы рассмотрели, где мы определили минимальное количество узлов на основе высоты дерева?
Отношение будет обратным логарифмическому соотношению: оно будет экспоненциальным. Мы можем увидеть это на иллюстрации ниже.
Поскольку высота AVL-дерева растет линейно, минимальное количество узлов, которые оно имеет, будет расти экспоненциально (примерно, конечно).
Мы видим, что каждый раз, когда мы брали высоту дерева в качестве входных данных и использовали ее для получения минимального количества узлов для AVL-дерева нашей введенной высоты, мы эффективно увеличивали золотое сечение до степени нашей высоты, h.
Например, когда мы хотели вычислить минимальное количество узлов для дерева AVL с высотой 8, мы увеличили φ до степени 8, что дало нам приблизительно 46,98. Помните, поскольку мы имеем дело с округленной версией иррационального числа, в противном случае, по мере того, как наши числа становятся больше, наши приближения имеют гораздо большую погрешность. Это объясняет, почему наши вычисления для дерева с высотой 2, 3, 4 или 5 намного точнее, чем наши вычисления для дерева с высотой 8. Если бы мы построили график этих результатов, мы бы фактически построили график. золотое сечение в степени h, высота нашего дерева.
Если вы чувствуете изумление, трепет и полное удивление от того, что вы только что узнали, не волнуйтесь - я тоже чувствовал то же самое. Я не думаю, что когда-либо снова буду думать о подсолнечнике или дереве AVL таким же образом.
(И, если я хорошо выполнил свою работу, вы тоже.)
Ресурсы
Мне было трудно сдержать все свое волнение по поводу Фибоначчи, золотых отношений и деревьев AVL, и я провел много исследований по всем трем этим темам. Если вы так же очарованы и поражены ими, как и я, вам понравятся ссылки ниже.
- Абстракции данных: деревья AVL, профессор Рут Андерсон
- Последовательность Фибоначчи, Math Is Fun
- Максимальная высота дерева AVL, Департамент CSA, IISc, Бангалор
- 15 необычных примеров золотого сечения в природе, Георгий Дворский
- Число Фибоначчи, Исследование Вольфрама.
- AVL Trees, профессор Эрик Александер
