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

Question

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

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-дерево, вероятно, будет лучше.Кроме того, деревья сопряжения поддерживают некоторые операции, такие как разбиение и слияние, очень эффективно, в то время как соответствующие операции дерева 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-деревья всегда лучше, чем бинарные деревья поиска, когда ваше приложение имеет дело с большим количеством данных в дереве, но будет нуждаться в доступе к подмножеству данных очень часто, чем к другим. В этом случае данные, к которым вы часто обращаетесь, появятся в корне в результате отображения. Кроме того, любой узел может быть доступен с меньшим временем, чем раньше.

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

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

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

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

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

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

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

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