What do you think?
Rate this book
Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem
Excerpt from Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem
They proved that, in an amortized sense and up to a constant factor, the splay tree is as efficient as many of the balanced search trees and the static optimal binary search tree for processing a sequence of dictionary operations. They and Tarjan [7] made the following conjectures concerning the performance of the splay Conjecture 1 (dynamic optimality conjecture Consider an arbitrary sequence of m searches of items in an n-node binary search tree. Let tsa the minimum time required to execute this sequence of searches on any self-adjusting binary search tree, assuming that each search costs (1+the accessed item's depth) and that each rotation costs 1. Then, t'he cost of performing this sequence of accesses on the splay tree is O(n tsa).
They proved that, in an amortized sense and up to a constant factor, the splay tree is as efficient as many of the balanced search trees and the static optimal binary search tree for processing a sequence of dictionary operations. They and Tarjan [7] made the following conjectures concerning the performance of the splay Conjecture 1 (dynamic optimality conjecture Consider an arbitrary sequence of m searches of items in an n-node binary search tree. Let tsa the minimum time required to execute this sequence of searches on any self-adjusting binary search tree, assuming that each search costs (1+the accessed item's depth) and that each rotation costs 1. Then, t'he cost of performing this sequence of accesses on the splay tree is O(n tsa).
41 pages, Paperback
First published July 28, 2015
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
No one has reviewed this book yet.