АВЛ-деревья03.09.2012 23:48
![](http://habrastorage.org/storage2/7d2/ec2/114/7d2ec21142aefa93984a3d14391572ef.jpg)
Если в
одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации
АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска,
придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например,
тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще
красно-черных деревьев, но глядя на прилагаемый к этому
код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.
Читать дальше →
© Habrahabr.ru