Очевидно, поиск осуществляется тем быстрее, чем ближе к корню расположен искомый элемент. В идеале двоичное дерево поиска сбалансировано, т. е. его форма такова, что каждый элемент располагается сравнительно близко к корню. Сбалансированное двоичное дерево поиска размера n имеет высоту O(log n), в предположении, что путь от корня до каждого узла имеет длину более, чем O(log n). Но совсем несбалансированное дерево поиска имеет высоту O(n); поиск в таком дереве так же неэффективен, как в связанном списке.
Рис. 1: Сбалансированное двоичное дерево | Рис. 2: Несбалансированное двоичное дерево |
Причин, по которым дерево может стать плохо сбалансированным, несколько. Во-первых, во многих приложениях входной поток элементов не обязательно будет случайным (в крайнем случае элементы вводятся в возрастающем или убывающем порядке и получающееся дерево в большинстве случаев оказывается несбалансированным). Во-вторых, порядок операций поиска (перемежающихся с операциями ввода) может быть непредсказуем (поиск недавно введенных элементов может оказаться особенно дорогим, поскольку элемент может оказаться на самом нижнем уровне двоичного дерева). В третьих, ожидаемые свойства деревьев поиска, получившихся после выполнения операций удаления не всегда хорошо понятны.
В этом подразделе будут расмотрены различные вариации двоичных деревьев, позволяющие добиться более стабильной, а, значит, более быстрой работы.
Один из подходов заключается в балансировке дерева после каждой операции. Таким образом получаются строгие ограничения на высоту узла, и, как следствие, гарантированная оценка O(logn) для операций.
Несколько заметок.
Верхние оценки высот листов для АВЛ-деревьев и красно-черных деревьев разные, но на практике деревья сбалансированы примерно одинаково;
Красно-черные деревья при правильной реализации лучше, чем АВЛ-деревья. Дело в том, что вставка и удаление элемента можно осуществить за один проход по дереву: сверху вниз[подробнее читайте здесьzip]. В АВЛ-деревьях требуется сначала пройти вниз, произвести операцию, а потом сделать балансирующий проход обратно вверх;
Реализация АВЛ-деревьев и красно-черных деревьев может быть как рекурсивной, так и итеративной. Для АВЛ-деревьев рекурсивная реализация работает в 1.5-2 раза медленнее. Красно-черные деревья, ввиду возможности вставки/удаления за один проход, также имеют большое преимущество при итеративной реализации.
Другой подход заключается в рандомизации алгоритма, то есть введения датчика случайных чисел, от которого (а не от входной последовательности) и будет зависеть форма дерева. Таким образом, дерево получается 'случайным', с оценкой O(log n).
В этом разделе :
8 Красно-черные деревья Узлы раскрашиваются в два цвета, следуя правилам. Некоторые сочетания цветов объявляются неправильными и от них избавляются путем вращений. Высота узла не более, чем в 2 раза превышает минимальную возможную для двоичного дерева. С исходником на Си.
8 Деревья со случайным поиском Каждому узлу сопоставляется приоритет - случайное число, доопределяющая место элемента дополнительно к самому ключу. Структура также обеспечивает быструю операцию нахождения большего/меньшего элемента. С исходником на С++.
8 Слоёные списки (скип-списки) Вероятнастная альтернатива сбалансированным деревьям. Проста в реализации и почти так же эффективна, как деревья. Основана на сопоставлении словаря и записной книжки. Как правило, медленнее деревьев. С исходником на Си.
| |