http://wiki.atp-fivt.org/index.php?action=history&feed=atom&title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE 2026-04-11T05:10:13Z История изменений этой страницы в вики MediaWiki 1.30.0 http://wiki.atp-fivt.org/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=438&oldid=prev 2020-05-25T00:44:13Z

<p>Новая страница: «==АВЛ-дерево== ===Определение и свойства=== &#039;&#039;&#039;АВЛ-дерево&#039;&#039;&#039; - сбалансированное по высоте двоич…»</p> <p><b>Новая страница</b></p><div>==АВЛ-дерево==<br /> ===Определение и свойства===<br /> '''АВЛ-дерево''' - сбалансированное по высоте двоичное дерево поиска, высоты поддеревьев каждого узла которого различаются не более, чем на 1.<br /> <br /> Аббревиатура АВЛ происходит от первых букв фамилий создателей АВЛ-дерева советских учёных Георгия Максимовича Адельсон-Вельского и Евгения Михайловича Ландиса.<br /> <br /> ==Высота дерева==<br /> ===Лемма о высоте===<br /> <br /> Пусть m&lt;sub&gt;h&lt;/sub&gt; - минимальное число вершин в АВЛ-дереве высотой h, тогда m&lt;sub&gt;h&lt;/sub&gt; = F&lt;sub&gt;h+2&lt;/sub&gt; - 1, где F&lt;sub&gt;h&lt;/sub&gt; - h-ое число Фибоначчи.<br /> <br /> ===Доказательство леммы===<br /> <br /> Из свойств АВЛ-дерева следует, что m&lt;sub&gt;h+2&lt;/sub&gt; = m&lt;sub&gt;h&lt;/sub&gt; + m&lt;sub&gt;h+1&lt;/sub&gt; + 1 (два поддерева высотами h и h+1 и их вершина-родитель).<br /> <br /> Докажем по индукции равенство m&lt;sub&gt;h&lt;/sub&gt; = F&lt;sub&gt;h+2&lt;/sub&gt; - 1.<br /> <br /> База индукции: m&lt;sub&gt;1&lt;/sub&gt; = F&lt;sub&gt;3&lt;/sub&gt; - 1 верно, т.к. m&lt;sub&gt;1&lt;/sub&gt; = 1, F&lt;sub&gt;3&lt;/sub&gt; = 2.<br /> <br /> Тогда имеем m&lt;sub&gt;h+1&lt;/sub&gt; = m&lt;sub&gt;h&lt;/sub&gt; + m&lt;sub&gt;h-1&lt;/sub&gt; + 1 = F&lt;sub&gt;h+2&lt;/sub&gt; - 1 + F&lt;sub&gt;h+1&lt;/sub&gt; - 1 + 1 = F&lt;sub&gt;h+3&lt;/sub&gt; - 1.<br /> <br /> Таким образом, равенство m&lt;sub&gt;h&lt;/sub&gt; = F&lt;sub&gt;h+2&lt;/sub&gt; - 1 доказано.<br /> <br /> ===Высота дерева===<br /> <br /> F&lt;sub&gt;h&lt;/sub&gt; = Ω(φ&lt;sup&gt;h&lt;/sup&gt;), φ=(√5+1)/2. <br /> <br /> То есть n ⩾ φ&lt;sup&gt;h&lt;/sup&gt;.<br /> <br /> Прологарифмировав обе части, получим:<br /> <br /> log&lt;sub&gt;φ&lt;/sub&gt;n ⩾ h<br /> <br /> Таким образом, высота АВЛ-дерева - O(log n).<br /> <br /> ==Балансировка==<br /> Для поддержания сбалансированности дерева будем в каждой вершине хранить разность высот её поддеревьев diff[i].<br /> <br /> '''Балансировка вершины''' - операция, которая в случае, если разность высот правого и левого поддеревьев АВЛ-дерева равна 2, изменяет связи &quot;предок-потомок&quot; в поддеревьях данной вершины так, что разность вершин в данном дереве составляет по модулю ⩽ 1. Операция осуществляется посредством вращения поддерева данной вершины.</div>

Algocourselecturenotes