Разница между AVL-деревьями и сплайс-деревьями

Question

Я изучаю различные деревья, и наткнулся на деревья AVL и деревья сплайсинга. я хочу знать

1. В чем разница между AVL-деревьями и Splay-деревьями?
2. На каком основании мы выбираем эти локоны?
3. Каковы положительные и отрицательные стороны этих деревьев?
4. Каковы характеристики этих деревьев с точки зрения больших обозначений O?

Answer 1

1. И деревья сплайнов, и деревья AVL являются бинарными деревьями поиска с отличными гарантиями производительности, но отличаются друг от друга тем, как они достигают тех, которые гарантируют эту производительность. В дереве AVL форма дерева всегда ограничена, так что форма дерева сбалансирована, что означает, что высота дерева никогда не превышает O(log n). Эта форма сохраняется при вставках и удалениях и не изменяется во время поиска. Сплайс-деревья, с другой стороны, поддерживают эффективность, изменяя форму дерева в ответ на поиск по нему. Таким образом, часто используемые элементы перемещаются вверх к вершине дерева и имеют лучшее время поиска. Форма деревьев сопряжения не ограничена и варьируется в зависимости от выполняемых поисков.

2. Здесь нет строгих правил. Однако одно ключевое отличие между структурами состоит в том, что деревья AVL гарантируют быстрый поиск (O(log n)) для каждой операции, в то время как деревья сопряжения могут гарантировать только то, что любая последовательность из n операций занимает самое большее O(n log n) времени. Это означает, что если вам нужны поиски в реальном времени, дерево AVL, вероятно, будет лучше. Тем не менее, splay-деревья в среднем работают намного быстрее, поэтому, если вы хотите минимизировать общее время выполнения поиска по дереву, splay-дерево, вероятно, будет лучше. Кроме того, splay-деревья очень эффективно поддерживают некоторые операции, такие как разбиение и объединение, в то время как соответствующие операции AVL-дерева более сложны и менее эффективны. Деревья Splay более эффективны по памяти, чем деревья AVL, потому что им не нужно хранить информацию о балансе в узлах. Однако деревья AVL более полезны в многопоточных средах с большим количеством поисков, потому что поиск в дереве AVL может выполняться параллельно, в то время как они не могут выполняться в деревьях splay. Поскольку деревья сопряжения изменяют свою форму на основе поиска, если вам нужно получить доступ только к небольшому подмножеству элементов дерева или если вы обращаетесь к некоторым элементам гораздо больше, чем к другим, дерево сопряжения превзойдет дерево AVL. Наконец, деревья сопряжения, как правило, легче реализовать, чем деревья AVL, поскольку логика вращения намного проще.

3. Смотрите (2)

4. Вставка, удаление и поиск AVL-дерева занимают по O (log n) каждый раз. У Splay Tree есть те же самые гарантии, но гарантия только в амортизированном смысле. Любая длинная последовательность операций займет не более O(n log n) времени, но отдельные операции могут занять до O(n) времени.

Надеюсь это поможет!

Answer 2

1) В чем разница между AVL-деревьями и Splay-деревьями?

Они похожи по структуре и операциям, которые мы им призываем. Разница в том, что в деревьях splay после каждой операции мы стараемся поддерживать дерево практически идеально сбалансированным, чтобы будущие операции занимали меньше времени.

2) На каком основании мы выбираем эти локоны?

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

Как общее правило для выбора этих деревьев, если вам нужно "Среднее" время log(n) за период операций с деревом, используйте сплайновое дерево. Двоичное дерево не может этого гарантировать.

3) Каковы положительные и отрицательные стороны этих деревьев?

Положительным моментом для обоих является то, что вы обойдете log(n) в обеих этих структурах данных теоретически.

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

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

4) Каковы характеристики этих деревьев в терминах больших O-обозначений?

Splay tree Log(n) в среднем для группы операций с деревом. Двоичное дерево Log(n), только если ваши ключи идут случайным образом.

Результаты во время выполнения здесь очевидны. Профилирование времени выполнения Splay Tree. Вы можете увидеть разницу во времени выполнения при поиске с и без Splaying.