расширенный поиск

Книга по требованию: Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem (Classic Reprint)

Товар № 11262187
Вес: 0.08 кг.
Год издания: 2015
Страниц: 42 Переплет: мягкая обложка
Товар отсутствует
Узнать о поступлении

Excerpt from Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem

Sleator and Tarjan devised a self-adjusting binary search tree, called the splay tree, that is competitive with many of the balanced search tree schemes for maintaining a dictionary. They conjectured that the splay algorithm is optimal, in an asymptotic sense, among the class of self-adjusting search algorithms that use only rotations to reorganize the tree. Tarjan proved a corollary of this conjecture, called the scanning theorem, which states that splaying requires O(n) time to access the nodes of an arbitrary n-node binary tree in symmetric order. Generalizing the scanning theorem, he conjectured that the cost of performing a sequence of m deque operations on an arbitrary n-node binary tree using splaying is O(m + n). He showed that the conjecture holds when the output operations are restricted to one end of the deque. Lucas proved that the cost of executing any sequence of deque output operations on an initial tree having a certain special shape using splaying is O(n?(n)), where ? is an inverse of the Ackerman function. A right 2-turn is a kind of double rotation performed on a binary tree. Sleator conjectured that the number of right 2-turns in any sequence of right 2-turns and right rotations performed on an arbitrary n-node binary tree is O(n). This conjecture is closely related to Tarjan's deque conjecture.

In this paper, we prove the following results:

1. Nearly tight lower and upper bounds on the maximum number of each type of rotational operation in intermixed sequences of various rotational operations performed on binary trees. In particular, our lower bound for right 2-turns refutes Sleator's turn conjecture.

2. An O((m + n)?(m + n)) bound for the deque conjecture. This bound is derived using our upper bounds for sequences of rotational operations.

3. A generalized version of the scanning theorem.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.

Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand компанией ООО «Книга по Требованию». Print-on-Demand - это технология печати книг по Вашему заказу на цифровом типографском оборудовании. Книга, произведенная по технологии Print-on-Demand (POD) представляет собой классическую печатную книгу с соблюдением всех стандартов качества, от офсетной бумаги и плотного картона до качественного клея, используемого при изготовлении. Черно-белая текстовая или полноцветная иллюстрированная книга (в зависимости от исходного файла, подготовленного к печати) может быть изготовлена в разных вариантах: - в мягкой обложке (Клеевое Бесшвейное Скрепление); - скрепление скобой (для книг с небольшим количеством страниц); - в твердом переплете с клееным текстовым блоком; Материалы, используемые при производстве книги: - бумага текстового блока - офсетная (белая или кремовая) 80 г/м2 - мягкая обложка - бумага мелованная 250 г/м2; - ламинация обложки - матовая или глянцевая; - твердый переплет - картон 2 мм, каптал, белые форзацы, прямой корешок - сверхпрочный полимерный клей; - каждая книга упакована в термопленку. Каждый заказ обрабатывается в индивидуальном порядке: каждой книге, напечатанной по технологии Print-on-Demand, присваивается уникальный номер.

Читать далее