Сбалансированные деревья

Cтраница 1

Сбалансированные деревья позволяют программе эффективно управлять данными. [1]

Сбалансированные или приближенно сбалансированные деревья гарантируют эффективное выполнение трех основных операций над деревьями: поиск, добавление и удаление элемента. Время выполнения этих операций пропорционально log n, где п - число вершин дерева. [2]

Среди бинарных деревьев полностью сбалансированные деревья имеют наиболее простую структуру и могут быть представлены в памяти ЭВМ без использования указателей. [3]

Сложность операции балансировки предполагает, что сбалансированные деревья следует использовать только тогда, когда поиск информации происходит значительно чаще, чем ее включение. Это утверждение особенно верно, поскольку вершины дерева поиска для экономии памяти обычно хранятся в виде плотно упакованных записей. Поэтому решающим фактором, определяющим эффективность операции балансировки, часто бывают доступность показателя балансировки и простота его изменения, ведь для его представления нужно всего два разряда. Опыт показывает, что сбалансированные деревья сразу же теряют почти всю свою привлекательность, как только речь заходит о плотной упаковке для записей. И действительно, простой и очевидный алгоритм включения в дерево превзойти трудно. [4]

Между полностью сбалансированными деревьями и деревьями Фибоначчи располагаются самые разные сбалансированные деревья. [5]

Таким образом, среди случайных деревьев редко встречаются вырожденные, а большей частью - достаточно хорошо сбалансированные деревья; следовательно, число сравнений не слишком увеличивается, если даже не пытаться превратить случайное дерево в полностью сбалансированное. [6]

Поскольку 4-узлы не играют никакой специальной роли в алгоритме с использованием 2 - 3 - 4-деревьев, сбалансированные деревья можно строить по существу так же, используя только 2-узлы и 3-узлы. Построенные таким образом деревья называют 2 - 3-деревьями. Такие деревья были исследованы Хопкрофтом ( Hopcroft) в 1970 г. 2 - 3-деревья не обладают достаточной гибкостью, чтобы можно было построить удобный алгоритм нисходящей вставки. Кроме того, RB-структура может упростить реализа-цию % но восходящие 2 - 3-деревья не обеспечивают особых преимуществ по сравнению с восходящими 2 - 3 - 4-деревьями, поскольку для поддержания баланса по-прежнему требуются одиночные и двойные ротации. Восходящие 2 - 3 - 4-деревья несколько лучше сбалансированы и обладают тем преимуществом, что для каждой вставки требуется максимум одна ротация. [7]

Поскольку 4-узлм FIC играют никакой специальной роли н алгоритме с использован и ем T - j - J - jicpcHuea, сбалансированные деревья можно строить л о существу так же, nciiu. Такие дсрсиьн бьшн исследованы Хспкрофтом ( Hopcroft) в 1970 г, 2 - 3 - деревья кс об. запяюг лестничной гибкостью, чтобы можно было построить уяобный алюритм нисходящей UCTSHSKH. Кроме того1 RB-структура может упростите реализацию, но т с ходящие 2 - 3 - д ревья не обеспечивают особых преимуществ и о сравнению с го1с х днищми 2 - 3 - 4-аеревьями, поскольку лпн поддержания Баланса по-прежнему требуются одиночные н двойные ротации. Восходящие 2 - 3 - 4 -деревья несколько лучше сбал а н си рои аи ы и пблалают тем преимуществом, что для каллой нст-эвхи требуется максимум едят ротацил. [8]

Другими словами, асимптотически для больших п в среднем по классу всех весовых последовательностей, выбираемых в соответствии с описанной выше процедурой, сбалансированные деревья так же хороши, как оптимальные деревья, и монотонные деревья так же плохи, как случайные деревья. Аналогичные результаты имеют место в общем случае, когда веса листьев ненулевые и выбираются независимо из множества неотрицательных веществе нных чисел с другим распределением вероятностей. [9]

Экспериментальные результаты исследования реализаций trie - деревьев. [10]

Эти сравнительные значения времени построения и поиска в таблицах символов, содержащих случайные последовательности 32-разрядных целых чисел, подтверждают, что поразрядные методы конкурируют с методами, использующими сбалансированные деревья, даже в случае ключей, хранящих случайные разряды. [11]

Посмотрим, что включает в себя понятие сбалансированного дерева. Ясно, что полностью сбалансированные деревья являются частным случаем сбалансированных деревьев и среди сбалансированных деревьев они являются деревьями с минимальной высотой при заданном числе узлов. Посмотрим, что представляют собой сбалансированные деревья максимальной высоты. [12]

Мы их будем просто называть сбалансированными деревьями, поскольку упомянутый критерий сбалансированности выглядит наиболее подходящим. Заметим, что все идеально сбалансированные деревья являются также и АВЛ-деревьямн. [13]

Нарисуйте 1 - 2-дерево, образованное в результате вставки ключей Е A S Y Q UESTIONe первоначально пустое дерево. Объясните, почему 1 - 2-деревья не представляют практического интереса как сбалансированные деревья. [14]

Алгоритмы поиска ( Часть 4), предназначенные для поиска конкретных элементов в больших коллекциях элементов, также имеют важное значение. Мы рассмотрим основные и расширенные методы поиска с использованием деревьев и преобразований численных ключей, в том числе деревья бинарного поиска, сбалансированные деревья, хеширование, деревья цифрового поиска и методы, которые подходят для очень больших файлов. Мы отметим взаимосвязь между этими методами, приведем статистические данные о их сравнительной производительности и установим соответствие с методами сортировки. [15]

Страницы: 1 2