The Design of Dynamic Data Structures by Mark H. Overmars

By Mark H. Overmars

In a variety of computing device purposes there's a desire of storing huge units of items in this kind of means that a few questions on these items should be spoke back successfully. information buildings that shop such units of gadgets might be both static (built for a hard and fast set of items) or dynamic (insertions of recent gadgets and deletions of present gadgets might be performed). particularly for extra advanced looking difficulties as they come up in such fields as computational geometry, database layout and special effects, basically static information constructions can be found. This booklet goals at remedying this loss of flexibility by means of delivering a few normal thoughts for turning static information constructions for looking out difficulties into dynamic constructions. even if the method is largely theoretical, the strategies provided are frequently essentially acceptable. The e-book is written in any such method that it really is readable if you have a few common wisdom of knowledge constructions and algorithms. even if this monograph was once first released in 1983, it really is nonetheless precise as a normal remedy of tools for developing dynamic info structures.

Show description

Read Online or Download The Design of Dynamic Data Structures PDF

Best data modeling & design books

Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization

This ebook constitutes a set of study achievements mature sufficient to supply a company and trustworthy foundation on modular ontologies. It provides the reader a close research of the state-of-the-art of the study zone and discusses the new recommendations, theories and methods for wisdom modularization.

Advances in Object-Oriented Data Modeling

Till lately, info platforms were designed round various enterprise services, equivalent to money owed payable and stock keep an eye on. Object-oriented modeling, by contrast, constructions structures round the data--the objects--that make up many of the enterprise features. simply because information regarding a selected functionality is proscribed to 1 place--to the object--the approach is protected against the results of switch.

Introduction To Database Management System

Designed in particular for a unmarried semester, first path on database structures, there are four facets that differentiate our e-book from the remainder. simplicity - often, the expertise of database platforms could be very obscure. There are

Additional resources for The Design of Dynamic Data Structures

Sample text

Ov2]) Let V = { s I ..... s n} be a set of s e g m e n t s on a line, o r d e r e d by left endpoint. G i v e n the u n i o n of the segments in A = { s l , . - , s i} and of the segments in B = { S i + l , O . , s n} (some i, l~i

A l-dimensional super B-tree is a b a l a n c e d l e a f - s e a r c h tree w i t h the leaves linked in a d o u b l y linked list. The l i n k i n g can easily be m a i n t a i n e d w h e n inserting or d e l e t i n g points. Hence, a l-dimensional B-tree can be m a i n t a i n e d in O ( l o g n) time per update u s i n g balancing. ). To insert a p o i n t p in T, it has to be i n s e r t e d in all structures a s s o c i a t e d to nodes o n the search p a t h towards p. Similar, to delete a p o i n t p, it has to be d e l e t e d from all structures a s s o c i a t e d to nodes on the search p a t h towards p.

The convex hull problem, local rebuilding does not seem to help in obtaining dynamic solutions. Biblioqraphical comments. g. Aho, Hopcroft and Ullman [AhHU], Knuth [Kn], Olivi4 [01] and Reingold, Nievergelt and Deo [REND]. 3. is based on van Leeuwen and Overmars tion of balancing in super B-trees can be found in Willard [vLOl]. A detailed descrip[will. 1. Introduction. g. g. super B-trees) another technique, named PARTIAL REBUILDING, can be useful. Generally speaking, the idea of partial rebuilding is the following.

Download PDF sample

Rated 4.12 of 5 – based on 15 votes