Описание тега splay-tree

Вопросы с тегом
A splay tree is a self-adjusting binary search tree with excellent amortized performance.
1 ответ

Как я могу вращать узлы в Splay Tree?

Код у меня есть private Node rotateLeftChild(Node n) { Node o = n.left; n.left = o.right; o.right = n; return o; } Когда я вызываю это, чтобы повернуть дерево, как это в корне: 7 / \ 4 8 / \ 1 5 он удаляет 4 и 1 и делает 5 левым корнем из 7. Я пытал…
30 ноя '12 в 05:17
1 ответ

Как создать восходящее дерево сплайнов из следующей последовательности

Это последовательность 20,10,5,30,40,57,3,2,4,35,25,18,22,27 Я пробовал сделать каждый новый вставленный узел корневым, но он не работает. Кто-нибудь может дать мне пошаговое объяснение?
26 дек '15 в 14:55
1 ответ

Тестирование Splay-деревьев

Я пытаюсь найти апплет в Интернете для тестирования деревьев сплайнов, но ни один из них, которые я нашел до сих пор, не удовлетворяет тому, что мне нужно. Мне нужно что-то, где я могу ввести уже построенное Splay Tree. У меня есть исходное дерево, …
23 окт '11 в 17:36
1 ответ

Сплайс деревья: как зигзаг и зигзаг вращаются в деталях?

Мне нужна помощь в понимании конкретного примера зигзагообразных и зигзагообразных вращений в деревьях сплайнов. Я читал о них в книге и в Википедии, а также в нескольких других онлайн-ресурсах, и хотя я могу понять их, когда они применяются к прост…
16 дек '16 в 12:58
2 ответа

Есть ли более быстрая реализация для этой суммы диапазона Splay Tree?

Я закодировал сплайновое дерево. Узлы представлены следующим образом. struct Node{ Node *l; /// The left Node Node *r; /// The right Node int v; /// The Value }; Теперь мне нужно знать сумму всех чисел в дереве в определенном диапазоне. Для этого я …
08 авг '16 в 08:24
1 ответ

Последовательность, которая формирует те же AVL и деревья Splay?

Существует ли такая последовательность чисел (1-7, все используемые числа, только по одному разу), которая бы образовала равные AVL и Splay Tree?
28 янв '13 в 14:41
1 ответ

Java Передача объекта в метод

У меня есть программа, которая позволяет пользователю выбирать между бинарным деревом поиска, деревом сплайнов и красным черным деревом. Я написал класс для дерева бинарного поиска, и теперь я работаю над деревом сплайнов, но я понял, что мой метод,…
07 мар '13 в 07:49
1 ответ

Работа ZigZag и ZigZig в дереве сплайнов?

Рассмотреть мое дерево, как это 5 / \ 3 7 / \ / \ 2 4 6 8 в том, что когда мы ищем элемент 2 в этот раз будет выполнена зигзагообразная операция, поэтому сначала мы поворачиваем parent and ancestor of 2 затем мы поворачиваем parent and 2, в том же с…
02 янв '15 в 12:26
2 ответа

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

Я изучаю различные деревья, и наткнулся на деревья AVL и деревья сплайсинга. я хочу знать В чем разница между AVL-деревьями и Splay-деревьями? На каком основании мы выбираем эти локоны? Каковы положительные и отрицательные стороны этих деревьев? Как…
19 сен '11 в 06:12
1 ответ

Сложность по времени makeEmpty() из дерева спуска сверху вниз

В этой реализации Splay Tree указана временная сложность makeEmpty() функция (которая удаляет все элементы) - это O(n). Это реализовано следующим образом: while( !isEmpty( ) ) { findMax( ); // Splay max item to root remove( root->element ); } Учи…
10 ноя '13 в 06:00
1 ответ

Интуиция за сплайсом (самобалансирующиеся деревья)

Я читаю основы splay деревьев. Амортизированная стоимость операции составляет O(log n) в течение n операций. Некоторая грубая основная идея заключается в том, что когда вы получаете доступ к узлу, вы выводите его на экран, т.е. вы берете его в корне…
02 май '11 в 06:08
2 ответа

Относительно кустарников

Я читаю о деревьях сплайнов в структурах данных и алгоритмах Марка Аллена Весиса Стратегия расширения похожа на идею вращения, за исключением того, что мы немного более избирательны в отношении того, как выполняются вращения. Мы все еще будем вращат…
05 сен '11 в 09:20
1 ответ

Использование универсального класса Pair и Splaytree для подсчета и хранения слов и их частот в Java

Я реализую splaytree для хранения слов и их частот и решил создать класс Pair, который будет содержать каждую пару слов-частота (ключ-значение). То есть каждый узел splaytree содержит пару класса Pair. Класс Pair выглядит следующим образом: public c…
12 окт '11 в 19:52
1 ответ

Splay tree: просмотр обхода по порядку просматривает узлы в порядке возрастания для splay tree?

Я только что закончил экзамен по этому вопросу, где я использовал обход по порядку, чтобы проверить правильный порядок узлов в одном из моих деревьев сплайнов. Это действительно?
09 ноя '16 в 06:00
1 ответ

Что быстрее на практике: Treap или Splay tree?

Я выучил как Treap, так и Splay tree и решил несколько проблем, используя их. Теоретически, их сложность в среднем равна O(log n), но в худшем случае сложность Treap равна O(n), а у Splay Tree амортизируется O(log n). В каком случае наихудший случай…
06 янв '18 в 21:17
1 ответ

Ошибка сегментации при попытке развернуть узел в дереве Splay

Я работаю над реализацией Splay Tree. Вставка работает отлично, но когда я пытаюсь развернуть вставленный узел зигзагообразным или зигзагообразным способом, я всегда получаю ошибку сегментации. Вращение вправо-влево, используемое, когда узел, которы…
19 фев '17 в 00:57
1 ответ

Использование дерева 2-3-4 вместо дерева сплайнов

Сейчас я нахожусь на курсе структур данных, и мы узнали о 2-3-4 деревьях и splay-деревьях. Мне было интересно, при каких обстоятельствах вы бы использовали 2-3-4 дерева вместо дерева? Они оба уравновешены и отсортированы, поэтому я не вижу особой ра…
16 дек '10 в 02:34
3 ответа

Как я могу реализовать splay-дерево, которое выполняет операцию zig последним, а не первым?

Для моего класса Algorithms & Data Structures мне было поручено реализовать Splay Tree в Haskell. Мой алгоритм операции Splay выглядит следующим образом: Если расширяемый узел является корневым, возвращается неизмененное дерево. Если развертываемый …
18 май '10 в 23:14
2 ответа

Когда я пересекаю дерево сплайнов, то какой из них является корневым?

У меня были сомнения, когда мы используем Splay Tree, последний доступ к элементу придет к корневому узлу. рассмотреть мое дерево 5 / \ 3 7 / \ / \ 2 4 6 8 когда я выполняю обход Inorder, вывод будет 2 3 4 5 6 7 8 так что здесь последний доступный э…
31 дек '14 в 12:30
1 ответ

Не могу понять, как работает растяжка

Я не могу понять, как работает splaying.Часть, которой я не могу следовать, - это то, как мы узнаем, если: zig II) zig-zag или iii) zig-zig должно быть сделано.Если я правильно понимаю, это связано с текущим узлом в пути.Если это ребенок корня, то э…
29 май '12 в 20:53