Saha Suman - Advanced Data Structures

Advanced Data Structures

Theory and Applications

Advanced Data Structures

Theory and Applications

Suman Saha
Shailendra Shukla

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

2020 by Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Printed on acid-free paper

International Standard Book Number-13: 978-1-138-59260-5 (Hardback)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.

Library of Congress Cataloging-in-Publication Data

Names: Saha, Suman, author. | Shukla, S. K. (Shailendra Kumar), 1969-author.

Title: Advanced data structures : theory and applications / Suman Saha, Shailendra Shukla.

Description: Boca Raton : Taylor & Francis, a CRC title, part of the Taylor & Francis imprint, a member of the Taylor & Francis Group, the academic division of T&F Informa, plc, 2019. | Includes bibliographical references and indexes.

Identifiers: LCCN 2019011938| ISBN 9781138592605 (hardback : acid-free paper) | ISBN 9780429488757 (ebook)

Subjects: LCSH: Data structures (Computer science)

Classification: LCC QA76.9.D35 S23 2019 | DDC 005.7/3--dc23

LC record available at https://lccn.loc.gov/2019011938

Visit the Taylor & Francis Web site at

http://www.taylorandfrancis.com

and the CRC Press Web site at

http://www.crcpress.com

Dedicated to our students

Contents

FOREWORD

Current trends in computer science and engineering are driven mostly by data science, machine learning, the Internet of Things, cryptography, and other practical uses. Therefore, a complete book on advanced data structures that will work as a backbone in explaining these modern subjects is much sought after.

However, writing such a book is challenging because it must meet two goals: allowing students to understand the fundamentals of advanced data structures and enabling them to apply in-depth knowledge in their chosen areas. This book is one of the first efforts in this direction and it will play an indispensable role for students in computer science and related disciplines to enhance their expertise in advanced data structures and applications.

The authors are members of the faculty at Jaypee University of Information Technology. They have more than ten years of teaching experience and have published a wide range of peer-reviewed articles in many areas of information technology. They possess unique skills in analyzing and explaining difficult algorithms and data structures simply and elegantly. Their expertise in all areas of computer science equips them to be suitable authors of a comprehensive book about data structures.

The book chapters are well organized. details recent applications. All the material is organized logically and both students and researchers can benefit from reading this book and applying its concepts.

I hope this book will serve as a useful tool for all inquisitive students who plan to apply recent developments in data structures to their work.

Dr. Amit Chattopadhyay
International Institute of Information Technology
Bangalore, India

ACKNOWLEDGMENTS

It has been almost two years since we started writing a book about advanced data structures. This book was kept on track and seen to completion with the support and encouragement of numerous family members, friends, colleagues, teachers, and students. It is a pleasure to express our thanks to all those who contributed in so many ways to our publication success.

We are very thankful to Dr. Amit Chattopadhyay of the International Institute of Information Technology in Bangalore for reviewing our work and writing a favorable foreword message. Our heartfelt thanks also extend to our friends and colleagues for their help and encouragement.

We express our sincere thanks to the students and colleagues of Jaypee University of Information Technology, Solan, Himachal. We also appreciate the excellent work of the editorial and production teams of CRC Press and Taylor & Francis. Thanks are also due to all the reviewers who evaluated this book and provided suggestions and advice.

Readers constructive feedback and suggestions for improvement may be emailed to .

PREFACE

Advanced data structures are usually covered in core courses included in most graduate programs in computer science, engineering, and allied disciplines, during the first year or first semester of the curriculum. The objective of the course is to provide students with a much-needed foundation for advancing their technical skills and sharpening their problem-solving abilities in their respective disciplines.

Although many technical universities have offered advanced data structure courses for decades, major technology advances triggered a recent paradigm shift that focuses on huge databases and Internet-based technologies. Most technical universities have redefined their course contents to meet current needs and rely heavily on research papers because of the lack of comprehensive texts on advanced data structures.

To the best of our knowledge, existing textbooks on advanced data structures provide only partial coverage of the subject. This book evolved from materials the authors developed over several years while teaching advanced data structures at Jaypee University of Information Technology. The course was designed for advanced graduate students, although it has become accessible to advanced undergraduates and beginner researchers in the areas of computer science and bio-informatics.

This book emphasizes recent evolutions of data structures to fit new paradigms of computation and applications to various domains of computer science. We included illustrative problems, review questions, and programming projects to enable students to comprehend, implement, and appreciate advanced data structures.