АВЛ-деревья

  • Tutorial
Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.



Понятие АВЛ-дерева


АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла. Это значит, что для поиска нужного ключа в АВЛ-дереве можно использовать стандартный алгоритм. Для простоты дальнейшего изложения будем считать, что все ключи в дереве целочисленны и не повторяются.

Особенностью АВЛ-дерева является то, что оно является сбалансированным в следующем смысле: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Доказано, что этого свойства достаточно для того, чтобы высота дерева логарифмически зависела от числа его узлов: высота h АВЛ-дерева с n ключами лежит в диапазоне от log2(n + 1) до 1.44 log2(n + 2) − 0.328. А так как основные операции над двоичными деревьями поиска (поиск, вставка и удаление узлов) линейно зависят от его высоты, то получаем гарантированную логарифмическую зависимость времени работы этих алгоритмов от числа ключей, хранимых в дереве. Напомним, что рандомизированные деревья поиска обеспечивают сбалансированность только в вероятностном смысле: вероятность получения сильно несбалансированного дерева при больших n хотя и является пренебрежимо малой, но остается не равной нулю.

Структура узлов


Будем представлять узлы АВЛ-дерева следующей структурой:

struct node // структура для представления узлов дерева
{
	int key;
	unsigned char height;
	node* left;
	node* right;
	node(int k) { key = k; left = right = 0; height = 1; }
};

Поле key хранит ключ узла, поле height — высоту поддерева с корнем в данном узле, поля left и right — указатели на левое и правое поддеревья. Простой конструктор создает новый узел (высоты 1) с заданным ключом k.

Традиционно, узлы АВЛ-дерева хранят не высоту, а разницу высот правого и левого поддеревьев (так называемый balance factor), которая может принимать только три значения -1, 0 и 1. Однако, заметим, что эта разница все равно хранится в переменной, размер которой равен минимум одному байту (если не придумывать каких-то хитрых схем «эффективной» упаковки таких величин). Вспомним, что высота h < 1.44 log2(n + 2), это значит, например, что при n=109 (один миллиард ключей, больше 10 гигабайт памяти под хранение узлов) высота дерева не превысит величины h=44, которая с успехом помещается в тот же один байт памяти, что и balance factor. Таким образом, хранение высот с одной стороны не увеличивает объем памяти, отводимой под узлы дерева, а с другой стороны существенно упрощает реализацию некоторых операций.

Определим три вспомогательные функции, связанные с высотой. Первая является оберткой для поля height, она может работать и с нулевыми указателями (с пустыми деревьями):

unsigned char height(node* p)
{
	return p?p->height:0;
}

Вторая вычисляет balance factor заданного узла (и работает только с ненулевыми указателями):

int bfactor(node* p)
{
	return height(p->right)-height(p->left);
}

Третья функция восстанавливает корректное значение поля height заданного узла (при условии, что значения этого поля в правом и левом дочерних узлах являются корректными):

void fixheight(node* p)
{
	unsigned char hl = height(p->left);
	unsigned char hr = height(p->right);
	p->height = (hl>hr?hl:hr)+1;
}

Заметим, что все три функции являются нерекурсивными, т.е. время их работы есть величина О(1).

Балансировка узлов


В процессе добавления или удаления узлов в АВЛ-дереве возможно возникновение ситуации, когда balance factor некоторых узлов оказывается равными 2 или -2, т.е. возникает расбалансировка поддерева. Для выправления ситуации применяются хорошо нам известные повороты вокруг тех или иных узлов дерева. Напомню, что простой поворот вправо (влево) производит следующую трансформацию дерева:



Код, реализующий правый поворот, выглядит следующим образом (как обычно, каждая функция, изменяющая дерево, возвращает новый корень полученного дерева):

node* rotateright(node* p) // правый поворот вокруг p
{
	node* q = p->left;
	p->left = q->right;
	q->right = p;
	fixheight(p);
	fixheight(q);
	return q;
}

Левый поворот является симметричной копией правого:

node* rotateleft(node* q) // левый поворот вокруг q
{
	node* p = q->right;
	q->right = p->left;
	p->left = q;
	fixheight(q);
	fixheight(p);
	return p;
}

Рассмотрим теперь ситуацию дисбаланса, когда высота правого поддерева узла p на 2 больше высоты левого поддерева (обратный случай является симметричным и реализуется аналогично). Пусть q — правый дочерний узел узла p, а s — левый дочерний узел узла q.



Анализ возможных случаев в рамках данной ситуации показывает, что для исправления расбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q больше высоты его правого поддерева: h(s)≤h(D).



Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.



Код, выполняющий балансировку, сводится к проверке условий и выполнению поворотов:

node* balance(node* p) // балансировка узла p
{
	fixheight(p);
	if( bfactor(p)==2 )
	{
		if( bfactor(p->right) < 0 )
			p->right = rotateright(p->right);
		return rotateleft(p);
	}
	if( bfactor(p)==-2 )
	{
		if( bfactor(p->left) > 0  )
			p->left = rotateleft(p->left);
		return rotateright(p);
	}
	return p; // балансировка не нужна
}

Описанные функции поворотов и балансировки также не содержат ни циклов, ни рекурсии, а значит выполняются за постоянное время, не зависящее от размера АВЛ-дерева.

Вставка ключей


Вставка нового ключа в АВЛ-дерево выполняется, по большому счету, так же, как это делается в простых деревьях поиска: спускаемся вниз по дереву, выбирая правое или левое направление движения в зависимости от результата сравнения ключа в текущем узле и вставляемого ключа. Единственное отличие заключается в том, что при возвращении из рекурсии (т.е. после того, как ключ вставлен либо в правое, либо в левое поддерево, и это дерево сбалансировано) выполняется балансировка текущего узла. Строго доказывается, что возникающий при такой вставке дисбаланс в любом узле по пути движения не превышает двух, а значит применение вышеописанной функции балансировки является корректным.

node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
	if( !p ) return new node(k);
	if( k<p->key )
		p->left = insert(p->left,k);
	else
		p->right = insert(p->right,k);
	return balance(p);
}

Чтобы проверить соответствие реализованного алгоритма вставки теоретическим оценкам для высоты АВЛ-деревьев, был проведен несложный вычислительный эксперимент. Генерировался массив из случайно расположенных чисел от 1 до 10000, далее эти числа последовательно вставлялись в изначально пустое АВЛ-дерево и измерялась высота дерева после каждой вставки. Полученные результаты были усреднены по 1000 расчетам. На следующем графике показана зависимость от n средней высоты (красная линия); минимальной высоты (зеленая линия); максимальной высоты (синяя линия). Кроме того, показаны верхняя и нижняя теоретические оценки.



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

Удаление ключей


С удалением узлов из АВЛ-дерева, к сожалению, все не так шоколадно, как с рандомизированными деревьями поиска. Способа, основанного на слиянии (join) двух деревьев, ни найти, ни придумать не удалось. Поэтому за основу был взят вариант, описываемый практически везде (и который обычно применяется и при удалении узлов из стандартного двоичного дерева поиска). Идея следующая: находим узел p с заданным ключом k (если не находим, то делать ничего не надо), в правом поддереве находим узел min с наименьшим ключом и заменяем удаляемый узел p на найденный узел min.

При реализации возникает несколько нюансов. Прежде всего, если у найденный узел p не имеет правого поддерева, то по свойству АВЛ-дерева слева у этого узла может быть только один единственный дочерний узел (дерево высоты 1), либо узел p вообще лист. В обоих этих случаях надо просто удалить узел p и вернуть в качестве результата указатель на левый дочерний узел узла p.

Пусть теперь правое поддерево у p есть. Находим минимальный ключ в этом поддереве. По свойству двоичного дерева поиска этот ключ находится в конце левой ветки, начиная от корня дерева. Применяем рекурсивную функцию:

node* findmin(node* p) // поиск узла с минимальным ключом в дереве p 
{
	return p->left?findmin(p->left):p;
}

Еще одна служебная функция у нас будет заниматься удалением минимального элемента из заданного дерева. Опять же, по свойству АВЛ-дерева у минимального элемента справа либо подвешен единственный узел, либо там пусто. В обоих случаях надо просто вернуть указатель на правый узел и по пути назад (при возвращении из рекурсии) выполнить балансировку. Сам минимальный узел не удаляется, т.к. он нам еще пригодится.

node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
{
	if( p->left==0 )
		return p->right;
	p->left = removemin(p->left);
	return balance(p);
}

Теперь все готово для реализации удаления ключа из АВЛ-дерева. Сначала находим нужный узел, выполняя те же действия, что и при вставке ключа:

node* remove(node* p, int k) // удаление ключа k из дерева p
{
	if( !p ) return 0;
	if( k < p->key )
		p->left = remove(p->left,k);
	else if( k > p->key )
		p->right = remove(p->right,k);	

Как только ключ k найден, переходим к плану Б: запоминаем корни q и r левого и правого поддеревьев узла p; удаляем узел p; если правое поддерево пустое, то возвращаем указатель на левое поддерево; если правое поддерево не пустое, то находим там минимальный элемент min, потом его извлекаем оттуда, слева к min подвешиваем q, справа — то, что получилось из r, возвращаем min после его балансировки.

	else //  k == p->key 
	{
		node* q = p->left;
		node* r = p->right;
		delete p;
		if( !r ) return q;
		node* min = findmin(r);
		min->right = removemin(r);
		min->left = q;
		return balance(min);
	}

При выходе из рекурсии не забываем выполнить балансировку:

	return balance(p);
}

Вот собственно и все! Поиск минимального узла и его извлечение, в принципе, можно реализовать в одной функции, при этом придется решать (не очень сложную) проблему с возвращением из функции пары указателей. Зато можно сэкономить на одном проходе по правому поддереву.

Очевидно, что операции вставки и удаления (а также более простая операция поиска) выполняются за время пропорциональное высоте дерева, т.к. в процессе выполнения этих операций производится спуск из корня к заданному узлу, и на каждом уровне выполняется некоторое фиксированное число действий. А в силу того, что АВЛ-дерево является сбалансированным, его высота зависит логарифмически от числа узлов. Таким образом, время выполнения всех трех базовых операций гарантированно логарифмически зависит от числа узлов дерева.

Всем спасибо за внимание!

Весь код
struct node // структура для представления узлов дерева
{
	int key;
	unsigned char height;
	node* left;
	node* right;
	node(int k) { key = k; left = right = 0; height = 1; }
};

unsigned char height(node* p)
{
	return p?p->height:0;
}

int bfactor(node* p)
{
	return height(p->right)-height(p->left);
}

void fixheight(node* p)
{
	unsigned char hl = height(p->left);
	unsigned char hr = height(p->right);
	p->height = (hl>hr?hl:hr)+1;
}

node* rotateright(node* p) // правый поворот вокруг p
{
	node* q = p->left;
	p->left = q->right;
	q->right = p;
	fixheight(p);
	fixheight(q);
	return q;
}

node* rotateleft(node* q) // левый поворот вокруг q
{
	node* p = q->right;
	q->right = p->left;
	p->left = q;
	fixheight(q);
	fixheight(p);
	return p;
}

node* balance(node* p) // балансировка узла p
{
	fixheight(p);
	if( bfactor(p)==2 )
	{
		if( bfactor(p->right) < 0 )
			p->right = rotateright(p->right);
		return rotateleft(p);
	}
	if( bfactor(p)==-2 )
	{
		if( bfactor(p->left) > 0  )
			p->left = rotateleft(p->left);
		return rotateright(p);
	}
	return p; // балансировка не нужна
}

node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
	if( !p ) return new node(k);
	if( k<p->key )
		p->left = insert(p->left,k);
	else
		p->right = insert(p->right,k);
	return balance(p);
}

node* findmin(node* p) // поиск узла с минимальным ключом в дереве p 
{
	return p->left?findmin(p->left):p;
}

node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
{
	if( p->left==0 )
		return p->right;
	p->left = removemin(p->left);
	return balance(p);
}

node* remove(node* p, int k) // удаление ключа k из дерева p
{
	if( !p ) return 0;
	if( k < p->key )
		p->left = remove(p->left,k);
	else if( k > p->key )
		p->right = remove(p->right,k);	
	else //  k == p->key 
	{
		node* q = p->left;
		node* r = p->right;
		delete p;
		if( !r ) return q;
		node* min = findmin(r);
		min->right = removemin(r);
		min->left = q;
		return balance(min);
	}
	return balance(p);
}



Источники


  • B. Pfaff, An Introduction to Binary Search Trees and Balanced Trees — описание библиотеки libavl
  • Н. Вирт, Алгоритмы и структуры данных — сбалансированные деревья по Вирту — это как раз АВЛ-деревья
  • Т. Кормен и др., Алгоритмы: построение и анализ — про АВЛ-деревья говорится в упражнениях к главе про красно-черные деревья
  • Д. Кнут, Искусство программирования — раздел 6.2.3 посвящен теоретическому анализу АВЛ-деревьев
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 48

    +1
    а при поворотах:
    влево: если q->right == 0
    вправо: если q->left == 0

    будет все работать?
      0
      Segmentation fault будет, но функция balance не запустит rotateleft если q->right == 0 и rotateright если q->left == 0. Этого явно не написано в коде, но это следует из логики работы функции.
        +2
        Правильно, функции поворота служебные, для внешнего пользователя (в данном случае) не нужные, а внутреннее использование подразумевает, что все нужные указатели не нулевые.
      –7
      Нет, ну рассматривать АВЛ-деревья и допускать при этом использование процедурных языков — как-то неинтересно :)

      А вообще, торт. Спасибо!
        0
        Как это не удивительно, но я не встретил ни разу рекурсивной реализации АВЛ-деревьев, везде предлагается итеративный подход. Поделитесь ссылками на реализацию на непроцедурных ЯП?
          0
          hackage.haskell.org/package/AvlTree
          Практически первое, что нашлось. АВЛ-дерево на Haskell.

          В курсе ФИЛП (функциональное и логическое программирование) было задание написать рекурсивную реализацию АВЛ-деревьев на Haskell. Надо будет дома посмотреть, вдруг найду старые исходники.
            0
            Спасибо!
              0
              Всегда пожалуйста! (:

              Кстати, где-то там же была более прозрачная реализация.
            0
            Таки нашел старый исходник.

            Код на Haskell
            #!/usr/bin/runhaskell
            
            data Avltree a = Leaf | Node a (Avltree a) (Avltree a)
            
            depth Leaf = 0
            depth (Node _ l r) = (max (depth l) (depth r)) + 1
            
            getl (Node _ l _) = l
            getr (Node _ _ r) = r
            getv (Node v _ _) = v
            
            balance t1 t2 = (depth t1) - (depth t2)
            balanceLL (Node v (Node lv ll lr) r) = (Node lv ll (Node v lr r))
            balanceLR (Node v (Node lv ll (Node rlv rll rrr)) r) = (Node rlv (Node lv ll rll) (Node v rrr r))
            balanceRL (Node v l (Node rv (Node lrv lrl lrr) rr)) = (Node lrv (Node v l lrl) (Node rv lrr rr))
            balanceRR (Node v l (Node rv rl rr)) = (Node rv (Node v l rl) rr)
            
            insert x Leaf = (Node x Leaf Leaf)
            insert x t@(Node v l r)
                | x == v = t
                | x < v && (balance left_i r) ==  2 && x < getv l = balanceLL (Node v left_i r)
                | x < v && (balance left_i r) ==  2 && x > getv l = balanceLR (Node v left_i r)
                | x > v && (balance l right_i) == -2 && x < getv r = balanceRL (Node v l right_i)
                | x > v && (balance l right_i) == -2 && x > getv r = balanceRR (Node v l right_i)
                | x < v  = (Node v left_i r)
                | x > v  = (Node v l right_i)
                    where
            			left_i = insert x l
            			right_i = insert x r
            
            delete x Leaf = Leaf
            delete x (Node v Leaf Leaf) = if v == x then Leaf else (Node v Leaf Leaf)
            delete x (Node v l Leaf) = if v == x then l else (Node v l Leaf)
            delete x (Node v Leaf r) = if v == x then r else (Node v Leaf r)
            delete x (Node v l r)
                | v == x = (Node min_v l del_m)
                | v > x && abs (balance del_l r) < 2 = (Node v del_l r)
                | v < x && abs (balance l del_r) < 2 = (Node v l del_r)
                | v > x && (balance (getl r) (getr r)) < 0 = balanceRR (Node v del_l r)
                | v < x && (balance (getl l) (getr l)) > 0 = balanceLL (Node v l del_r)
                | v > x = balanceRL (Node v del_l r)
                | v < x = balanceLR (Node v l del_r)
                    where
            			del_m = delete min_v r
            			del_l   = delete x l
            			del_r   = delete x l
            			min_v   = get_min (toList r)
            
            get_min ((x,bal):xs) = x
            
            toList Leaf = []
            toList (Node x l r) = (toList l) ++ [(x,balance l r)] ++ (toList r)
            
            isBalanced Leaf = True
            isBalanced (Node _ l r) = isBalanced l && isBalanced r && abs (balance l r) < 2
            
            main = print$isBalanced(delete 1 (insert 4(insert 5 (insert 3 (insert 9 (insert 1 Leaf))))))
            

              0
              Красиво! И местами даже понятно… :)
              +1
              Пожалуйста, вот балансировка avl-дерева на прологе, мной написано в университете на дисциплине «мат.логика».
              Pastebin.

              А за что минусы?
                +1
                Вот ещё нашёл поинтереснее, кстати! Позволяет делать различные действия с деревом.
                Pastebin.

                P.S. Ведь не так давно было, а алгоритм уже без погружения и не разберёшь)
                  0
                  Спасибо! Теперь можно сравнить с реализацией на Haskell… Кстати, не нашел удаления ключей в вашей программе. Правда, там есть union — это слияние двух деревьев? Если «да», то удаление уже несложно реализовать…
                0
                Мб потому что нет ленивости и не всегда просто оптимизировать рекурсию? PS: Это не сарказм, а вопрос :)
                +2
                Отличный пост. Даёшь еще деревья!
                  +3
                  И все-же red-black tree — сложнее, намного сложнее. Хотя если вы и о них напишите — они станут легче, намного легче)).

                  Без шуток, это самый читаемый код, из тех, что я видел на хабре. Единственное что С-style в if и ? глаза мозолят.
                    +4
                    Сначала хочется разобраться со сплей-деревьями, а потом уже очередь красно-черных…
                    +1
                    Когда-то на втором курсе делал шаблон АВЛ дерева на C++, если найду, выложу в паблик со ссылкой здесь…
                      0
                      >АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла.

                      Неверно. Ключ любого узла дерева строго больше любого ключа в левом поддереве. У вас же сказано «не меньше», что эквивалентно «больше либо равно». Вторая часть ("… и не больше любого ключа в правом поддереве") — верна.

                      А подпись к картинке, которая расположена рядом, противоречит текстовому описанию: на ней для обоих случаев изображено строго больше («A < k < B»), хотя должно быть «A < k <= B».
                        0
                        Ну что же тогда делать с деревом, которое состоит из трех равных элементов?
                          0
                          В обычное бинарное дерево поиска (с условием «A < k <= B») это укладывается элементарно:

                          N
                           \
                            N
                             \
                              N
                          

                          Как из этого сделать АВЛ-дерево — вопрос хороший.

                          А вот как уложить три равных элемента в дерево при условии «A < k < B» — я как-то не очень представляю.
                            0
                            в АВЛ как раз будет:
                            N
                            / \
                            N N
                            Из чего следует, что автор все правильно написал.
                              +1
                              Вы не понимаете суть моей претензии :)

                              Автор написал: «АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла», в то время как «стандартными» свойствами двоичного дерева поиска являются:
                              1. Оба поддерева — левое и правое, являются двоичными деревьями поиска.
                              2. У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
                              3. В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X.

                              То есть именно «A < k <= B».

                              АВЛ-дерево изменяет это условие, поэтому называть это «стандартным» свойством двоичных деревьев поиска — неверно.

                              А подпись к картинке «A < k < B» вообще исключает возможность хранения одинаковых ключей.
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  +1
                                  Интересно: вы сами же признаёте, что есть разные определения, но тут же одно из них называете «моими фантазиями». Вы уж определитесь тогда, «фантазии» это или всего лишь другое определение. Добрее надо быть, что ли… %)

                                  Да, я был неправ — не знал о существовании второго варианта определения. Вот только своё я взял я не из головы, а из университетского курса теории алгоритмов.

                                  Кстати, вариант «A <= k <= B» вводит неоднозначность при вставке, а также (ввиду неоднозначности размещения равного элемента) может запросто ломать некоторые алгоритмы поиска. А так ничего, вполне себе нормальное определение %)

                                  P.S.: кстати, что скажете по поводу подписи к картинке «A < k < B»?
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                      0
                                      >Почему? По идее поиск не должен меняться: как только мы дошли до вершины с заданным ключом, мы останавливаемся и говорим, что вершина найдена. Иначе однозначно идём направо или налево.

                                      Пример: надо найти не любую вершину с заданным ключом, а все такие вершины. И если алгоритм поиска писался для определения «A < k <= B», то налево он не пойдёт никогда (а он может быть написан именно таким образом в целях оптимизации — в этом случае исключается дополнительное сравнение, которое на очень больших деревьях может давать существенную просадку в скорости поиска), в результате чего часть данных не будет найдена.

                                      Кстати, полностью согласен с тем, что данные с одинаковыми ключами лучше хранить в одной вершине.

                                      >Но нормально написанный код будет работать и с неуникальными ключами.

                                      Как я уже сказал выше, такой «нормально написанный код» вполне может проседать по производительности, если для повторяющегося ключа нужно будет идти не только вправо, но и влево по дереву. Деревья ведь могут содержать не только сотни-тысячи элементов, но и миллиарды. Мне в одной компании давали такую задачку на собеседовании :)
                                        +1
                                        Предположим, что у нас в дереве n одинаковых ключей (предельный случай) и больше ничего, и одинаковые ключи могут быть и слева и справа. Тогда поиск найдет все их, обойдя все дерево, и выполнит при этом O(n) действий. Пока я не вижу проблемы — чтобы найти n вхождений, потребовалось выполнить O(n) действий… Может я чего-то не понимаю?
                                          –1
                                          Разумеется, в обоих случаях будет O(n). Вот только в одном из них будет ровно n сравнений, а в другом 2*n сравнений. Да, и то, и другое O(n), вот только на самом деле одно вдвое больше другого ;)

                                          Кстати, ключи далеко не всегда целочисленные, поэтому операция сравнения не всегда элементарна.
                                            0
                                            Все равно непонятно: чтобы добраться до какого-то элемента, мы должны спуститься к нему из предыдущего по дуге, что эквивалентно выполнению ровно одного сравнения. Т.е. число сравнений (<= или >=) все равно окажется равным n-1. Для примера можно взять случай с тремя вершинами (выше в комментариях) — в обоих нарисованных вариантах дерева нам потребуется 3 (т.е. n) сравнения на равенство и 2 (т.е. n-1) на меньше-больше, нет? Возможно, по другому будет, если число одинаковых ключей, которые мы ищем, равно k и оно меньше n? Сейчас подумаю…
                                              0
                                              Ну вот смотрите: мы стоим в вершине «a», ключ которой совпадает с искомым:
                                                   a
                                                  / \
                                                 b   c
                                              


                                              В случае алгоритма с «A <= k <= B» мы проверим как ключ вершины b, так и ключ вершины c. Т.е. выполним две операции сравнения. Нашли такой же ключ — спускаемся в эту вершину и делаем то же самое. Неважно, оказалась ли она слева или справа. Т.е. в каждой из n вершин мы выполняем две операции сравнения. Общее количество операций сравнения — 2*n.
                                              В случае алгоритма с «A < k <= B» мы будем проверять только ключ вершины c, и если значение совпадает с искомым, мы спускаемся в эту вершину и делаем то же самое. Т.е. в каждой из n вершин мы выполняем одну операцию сравнения. Общее количество операций сравнения — n.
                                                0
                                                Т.е. все-таки случай, когда ключи не все одинаковы! Как я понимаю, количество «ложных» срабатываний (когда мы переходим в узел, не содержащий искомого ключа, как в вашем примере) в одном случае будет 2h, во втором h, где h — высота дерева. Если дерево идеально сбалансировано, то получим 2log2n против log2n, что уже не выглядит так драматично :)
                                                  0
                                                  Да, разница будет только при прохождении конкретно этих ключей. На то, чтобы добраться до искомого значения, времени уйдёт одинаково в обоих случаях.

                                                  Не очень понял, как (и зачем :)) вы считаете количество ложных срабатываний.

                                                  В каждой из вершин (вообще в каждой, от самого корня) логика сводится к следующему:

                                                  До того, как найдено хоть одно совпадение:
                                                  Если значение текущего ключа меньше, чем искомое, мы идём в правое дерево.
                                                  Если значение текущего ключа больше, чем искомое, мы идём в левое дерево.
                                                  Если значение текущего ключа равно искомому, сохраняем текущий узел и проверяем только правое поддерево в случае A < k <= B и оба поддерева в случае A <= k <= B. И так — в каждом элементе, в котором ключ равен искомому.
                                                  Останавливаемся когда натыкаемся на ключ, не совпадающий с искомым (ниже проверять уже бессмысленно).

                                                  Так что вне зависимости от того, как расположены одинаковые элементы (хоть цепочкой, хоть идеально сбалансированно по высоте), в каждом из них мы проводим ровно две операции сравнения в одном случае и ровно одну операцию в другом случае. Так что разница всегда будет n против 2*n.
                                                    0
                                                    При а < k <= b, в случае с множеством одинаковых ключей, не получится оставлять дерево сбалансированным, что даст множество потерь на всех этапах.
                                                      0
                                                      Угу, мы уже поняли, что балансированность и «A < k <= B» уживаются плохо — одинаковые элементы при таком условии всегда будут вытянуты в цепочку вправо-вниз.

                                                      Сошлись на том, что оптимальным вариантом было бы хранить данные с одинаковыми ключами в одной и той же ноде :)
                                    0
                                    Собственно, при написании топика я этот момент не проверил, т.к. мне казалось, что я помню именно такое определение (два нестрогих неравенства). Сейчас посмотрел Кормена, оказывается я правильно помнил… Вообще-то, чуть ниже в топике (в том же абзаце) я ввел более строгое ограничение, предположив, что все ключи различны, и рисунок относится именно к этому случаю. Уникальность же ключей, например, гарантрируется, если мы с помощью дерева поиска реализуем какой-нибудь словарь (или ассоциативный массив).
                          +1
                          оффтоп: Одному мне форматирование кода показалось не очень читабельным?

                          Например здесь всё сливается в единый набор букв:
                          p->left?findmin(p->left):p;


                          А вот здесь как раз наоборот:
                          if( k > p->key )

                            +1
                            Нет, не только вам, мне теперь тоже так кажется :) Обычно пишу, как во втором варианте, а тут решил «укомпактить» код…
                              0
                              Уф :) Ну значит я не зря придрался!
                            0
                            Я по этой книжке AVL изучал shop.oreilly.com/product/9781565924536.do
                            Очень рекомендую.

                            Но у вас код как-то поаккуратнее выглядит, надо будет посравнивать…
                              0
                              Оглавление интересное, надо поискать… Спасибо!
                              PS: уже нашел :)
                              0
                              Офигенная статья, отличные иллюстрации!
                                +1
                                Вопрос: если AVL-деревья, в общем-то, неплохи, почему в стандартной библиотеке С++ используются red-black trees для имплементации std::map?
                                  +1
                                  Как я понял, АВЛ-деревья лучше сбалансированы, чем красно-черные. В этом их плюс, т.к. поиск выполняется чуть-чуть быстрее: высота в АВЛ-дереве ограничена величиной 1.44log2(n+2) против 2log2(n+1) в красно-черных. С другой стороны, это означает, что в АВЛ-деревьях больше сил затрачивается на балансировку, следовательно, операции вставки и удаления работают медленнее, чем в красно-черных деревьях. Так что однозначного победителя здесь похоже нет…
                                  0
                                  vможет уже поздно писать но нектороые изображения неверные? например разница высот h(a) — h(q) не будет равна 2. Скорее -2. Или я что-то путаю?
                                    0
                                    Отменная статья!!! Прошу еще) Больше деревьев!

                                    P.S. И графы можно
                                      +1
                                      Таким образом, хранение высот с одной стороны не увеличивает объем памяти, отводимой под узлы дерева, а с другой стороны существенно упрощает реализацию некоторых операций.

                                      Тогда объясните мне такую вещь: в любой узел приходит два поддерева, и баланс учитывает их разницу (это две высоты), если вы храните высоту, то вы будете хранить максимальную высоту (минимальная всегда еденица, с изначального построения дерева и так ей и останется не порождая поворотов, а алгоритм будет не работоспособен), а это одно поддерево, соответственно, что бы знать разницу нужно либо хранить ещё и вторую высоту либо каждый раз спускаться в другой узел (если ещё и известно какой из них другой), что бы посмотреть альтернативную высоту и посчитать разницу. То есть, либо вы в два раза больше памяти потребляете, либо, усложняете реализацию.
                                        0
                                        Не знаю, кто поставил плюс, я на самом деле, хотел комментарий автора, потому что только разбираюсь с собственной реализацией АВЛ. Дело в том, что АВЛ деревья, не такая простая тема. В частности, всё что я написал выше, очень хорошо, даже идеально ложиться на малые вращения, но как только речь заходит о больших вращениях, то там, из-за переподключения целых поддеревьев, при хранении баланса, возможно придётся высчитывать высоту поддеревьев, что бы посчитать баланс, что сложнее чем взять их уже существующие высоты.

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое