История открытия АВЛ-дерева

В 1999 г. в сборнике «Математическое просвещение», вып. 3, были опубликованы воспоминания о профессоре Е. М. Ландисе. Там, в частности, чудесно описан процесс разработки конструкции АВЛ-дерева.

Это было в 60-е годы. Евгений Михайлович работал в Институте теоретической и экспе­риментальной физики, в математической лаборатории, которой заведовал А. С. Кронрод. ... Мы тогда занимались программными задачами, в которых надо было запоминать числа и другие объекты, а потом их же и искать. Можно запоминать объекты в порядке поступления, но тогда долго будет их искать. ... На семинаре Кронрода кто-то из аспирантов рассказал американскую работу, в которой «справочные» строились в виде дерева. Впрочем, и до этого представлять «справочную» иначе, чем в виде дерева, никому в голову не приходило. А в таком дереве очень хорошо искать.

На семинаре нам рассказали, что если все исходы равновероятны, то, вообще говоря, гулять по такому дереву, и его строить, и добавлять можно достаточно быстро. Глубина дерева будет, как правило, равняться логарифму от числа вершин, и этв же величина будет равняться количеству операций, уходящих как на поиск, так и на перестройку дерева.

Евгений Михайлович сказал, что если в среднем это так, то должен быть способ построить дерево, чтобы всегда это было так. И он бродил по лестницам, коридорам и переходам нашего здания, думал и время от времени говорил: «О, уже придумал?» За ним ходил Адельсон Вельский, и каждый раз, когда Ландис что-то придумывал, он догонял его и строил контр­пример. И так они ходили две недели друг за другом и придумывали: Ландис — алгоритм, Адельсон — противоречащий пример. Под конец у обоих создалось впечатление, что они дошли до таких алгоритмов, для которых контрпример придумывать все труднее и труднее.
И после этого они вдвоем построили правильный алгоритм. Сейчас это можно рассказать за три минуты, так это просто и красиво.

У Ландиса была такая присказка, такое любимое выражение, что математика можно узнать по тому, сколько времени он согласен думать над одной задачей. Если он согласен думать достаточно долго, то он либо уже математик, либо потенциальный математик. А если нет, то и говорить не о чем.

Автор этого отрывка — Владимир Львович Арлазаров, член-корр. РАН, генеральный директор компании Соgnitivе Тесhnоlоgiеs.