Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Структуры данных и хэширование / Словари для произвольных данных /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


8  Красно-черные деревья
8  Деревья со случайным поиском
8  Слоёные списки (скип-списки)
Улучшенные двоичные деревья - Программирование от RIN.RU
Улучшенные двоичные деревья

Очевидно, поиск осуществляется тем быстрее, чем ближе к корню расположен искомый элемент. В идеале двоичное дерево поиска сбалансировано, т. е. его форма такова, что каждый элемент располагается сравнительно близко к корню. Сбалансированное двоичное дерево поиска размера n имеет высоту O(log n), в предположении, что путь от корня до каждого узла имеет длину более, чем O(log n). Но совсем несбалансированное дерево поиска имеет высоту O(n); поиск в таком дереве так же неэффективен, как в связанном списке.


Сбалансированное двоичное дерево
Рис. 1: Сбалансированное двоичное дерево
Несбалансированное двоичное дерево
Рис. 2: Несбалансированное двоичное дерево



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


В этом подразделе будут расмотрены различные вариации двоичных деревьев, позволяющие добиться более стабильной, а, значит, более быстрой работы.


Один из подходов заключается в балансировке дерева после каждой операции. Таким образом получаются строгие ограничения на высоту узла, и, как следствие, гарантированная оценка O(logn) для операций.


Несколько заметок.


  • Верхние оценки высот листов для АВЛ-деревьев и красно-черных деревьев разные, но на практике деревья сбалансированы примерно одинаково;

  • Красно-черные деревья при правильной реализации лучше, чем АВЛ-деревья. Дело в том, что вставка и удаление элемента можно осуществить за один проход по дереву: сверху вниз[подробнее читайте здесьzip]. В АВЛ-деревьях требуется сначала пройти вниз, произвести операцию, а потом сделать балансирующий проход обратно вверх;

  • Реализация АВЛ-деревьев и красно-черных деревьев может быть как рекурсивной, так и итеративной. Для АВЛ-деревьев рекурсивная реализация работает в 1.5-2 раза медленнее. Красно-черные деревья, ввиду возможности вставки/удаления за один проход, также имеют большое преимущество при итеративной реализации.




Другой подход заключается в рандомизации алгоритма, то есть введения датчика случайных чисел, от которого (а не от входной последовательности) и будет зависеть форма дерева. Таким образом, дерево получается 'случайным', с оценкой O(log n).






SpeedSIP значительно снижает расходы на телефонную связь и сервисы:
  • бесплатные звонки внутри сети,
  • выгодные международные и междугородные звонки,
  • СМС по всему миру,
  • покупка прямого номер любой страны,
  • видеосвязь и видеоконференции.


  • В этом разделе :

    8  Красно-черные деревья
    Узлы раскрашиваются в два цвета, следуя правилам. Некоторые сочетания цветов объявляются неправильными и от них избавляются путем вращений. Высота узла не более, чем в 2 раза превышает минимальную возможную для двоичного дерева. С исходником на Си.

    8  Деревья со случайным поиском
    Каждому узлу сопоставляется приоритет - случайное число, доопределяющая место элемента дополнительно к самому ключу. Структура также обеспечивает быструю операцию нахождения большего/меньшего элемента. С исходником на С++.

    8  Слоёные списки (скип-списки)
    Вероятнастная альтернатива сбалансированным деревьям. Проста в реализации и почти так же эффективна, как деревья. Основана на сопоставлении словаря и записной книжки. Как правило, медленнее деревьев. С исходником на Си.

    8  Красно-черные деревья
    8  Деревья со случайным поиском
    8  Слоёные списки (скип-списки)

     
      
      
        Copyright ©  RIN 2003 - 2004      * Обратная связь