The Design of Dynamic Data Structures

در بسیاری از برنامه های کامپیوتری نیاز به ذخیره مجموعه های بزرگی از اشیاء وجود دارد به گونه ای که بتوان به برخی از سؤالات مربوط به آن اشیا به طور مؤثر پاسخ داد. ساختارهای داده ای که چنین مجموعه هایی از اشیاء را ذخیره می کنند می توانند ایستا (ساخته شده برای مجموعه ای ثابت از اشیاء) یا پویا (درج اشیاء جدید و حذف اشیاء موجود انجام شود). به خصوص برای مشکلات جستجوی پیچیده تر که در زمینه هایی مانند هندسه محاسباتی، طراحی پایگاه داده و گرافیک کامپیوتری بوجود می آیند، فقط ساختارهای داده ایستا در دسترس هستند. هدف این کتاب رفع این عدم انعطاف با ارائه تعدادی تکنیک کلی برای تبدیل ساختارهای داده ایستا برای جستجوی مشکلات به ساختارهای پویا است. اگرچه این رویکرد اساساً تئوری است، تکنیک های ارائه شده اغلب عملاً قابل اجرا هستند. این کتاب به گونه ای نوشته شده است که برای کسانی که دانش ابتدایی از ساختار داده ها و الگوریتم ها دارند قابل خواندن باشد. اگرچه این تک نگاری برای اولین بار در سال 1983 منتشر شد، اما همچنان به عنوان یک روش کلی برای ساختن ساختارهای داده پویا منحصر به فرد است.

In numerous computer applications there is a need of storing large sets of objects in such a way that some questions about those objects can be answered efficiently. Data structures that store such sets of objects can be either static (built for a fixed set of objects) or dynamic (insertions of new objects and deletions of existing objects can be performed). Especially for more complex searching problems as they arise in such fields as computational geometry, database design and computer graphics, only static data structures are available. This book aims at remedying this lack of flexibility by providing a number of general techniques for turning static data structures for searching problems into dynamic structures. Although the approach is basically theoretical, the techniques offered are often practically applicable. The book is written in such a way that it is readable for those who have some elementary knowledge of data structures and algorithms. Although this monograph was first published in 1983, it is still unique as a general treatment of methods for constructing dynamic data structures.