book

Data Structures and Algorithms Using C++

by Ananda Rao Akepogu, Radhika Raju Palagiri

July 2010

Intermediate to advanced

576 pages

11h 57m

English

Pearson India

Read now

Unlock full access

Cover
Title page
Contents
About the Authors
Preface
Chapter 1. Introduction to C++
1.1 Introduction1.2 Class Overview1.2.1 Class1.2.2 Objects1.2.3 Class Members1.3 I/O Streams1.4 Access Control1.5 Class Scope1.6 Static Class Members1.6.1 Static Member Variables1.6.2 Static Member Function1.6.3 Static Object1.7 Functions1.7.1 Parameter Passing Methods1.7.2 Inline Functions1.7.3 The friend Function1.7.4 Function Overloading1.8 The this Pointer1.9 Dynamic Memory Allocation and Deallocation1.9.1 The new Operator1.9.2 The delete Operator1.10 Exception HandlingSummaryExercises
Chapter 2. Object Oriented Concepts
2.1 Goals and Principles2.1.1 Object Oriented Design Goals2.1.2 Object Oriented Design Principles2.2 Constructors and Destructors2.2.1 Constructors2.2.2 Constructor Overloading2.2.3 Destructors2.3 Operator Overloading2.3.1 Overloading the Plus (+) Operator2.3.2 Overloading the Minus (-) Operator2.3.3 Overloading Unary Operators2.3.4 Postfix form of Overloading the Unary Operator ++2.3.5 Prefix form of Overloading the Unary Operator−−2.3.6 Postfix form of Overloading the Unary Operator−−2.4 Inheritance2.4.1 Base Class Access Control2.4.2 Types of Inheritance2.4.3 Reasons for the Usage of Inheritance2.4.4 Advantages2.4.5 Disadvantages2.4.6 Delegation2.5 Polymorphism2.5.1 Virtual Functions2.5.2 Pure Virtual Functions2.6 Abstract Classes2.7 Generic Programming with Templates2.7.1 Function Templates2.7.2 Class Templates2.8 RecursionSummaryExercises
Chapter 3. Algorithms
3.1 Introduction3.2 Basic Notations3.2.1 Pseudo Code3.3 Types of Algorithms3.3.1 Brute Force Algorithms3.3.2 Divide and Conquer Algorithms3.3.3 Dynamic Programming Algorithms3.3.4 Greedy Algorithms3.3.5 Branch and Bound Algorithms3.3.6 Recursive Algorithms3.3.7 Back Tracking Algorithms3.3.8 Randomized Algorithms3.3.9 Hill Climbing Algorithms3.4 Performance Analysis3.4.1 Properties of the Best Algorithms3.5 Space Complexity3.5.1 Instruction Space3.5.2 Text Section of a Program3.5.3 Data Space3.5.4 Stack Space3.5.5 Calculating the Instruction Space3.5.6 Calculating the Data Space3.5.7 Size of Data Section3.5.8 Size of Rodata Section3.5.9 Size of bss Section3.6 Apriori Analysis3.7 Asymptotic Notation3.7.1 Big oh Notation (O)3.7.2 Omega Notation (Ω)3.7.3 Theta Notation (θ)3.7.4 Little oh Notation(o)3.8 Time Complexity3.8.1 Time Complexity Analysis of Bubble Sort3.8.2 Time Complexity Analysis of Selection Sort3.9 Worst Case, Average Case and Best Case Complexity3.9.1 Worst Case3.9.2 Average Case3.9.3 Best CaseSummaryExercises
Chapter 4. Arrays
4.1 Introduction4.1.1 Array4.2 Array Types4.2.1 Single-dimensional Array4.2.2 Multi-dimensional Array4.2.3 N-dimensional Array4.3 Array Representation4.4 Initializing Arrays4.5 Accessing Values of an Array4.6 Array Operations4.6.1 Traversing4.6.2 Insertion4.6.3 Deletion4.6.4 Sorting4.6.5 Searching4.7 Arrays as Parameters4.8 Character Sequences4.9 ApplicationsSummaryExercises
Chapter 5. Linked List
5.1 Introduction5.2 Representation of Linked List in Memory5.2.1 Static Representation5.2.2 Dynamic Representation5.3 Singly Linked List5.3.1 Operations5.4 Circular Linked List5.4.1 Merging of Two Circular Lists5.5 Doubly Linked Lists5.5.1 Representation of Doubly Linked List5.5.2 Operations5.6 Comparison of Various Linked Lists5.6.1 Linked Lists Versus Arrays5.7 Applications5.7.1 Polynomial ManipulationSummaryExercises

Chapter 6. Stacks
6.1 Definition6.2 Representation of a Stack6.2.1 Array Representation of a Stack6.2.2 Linked Representation of a Stack6.3 Operations on Stack6.3.1 Array Implementation of a Stack6.3.2 Linked Implementation of a Stack6.4 Applications of Stacks6.4.1 Expression Evaluation6.4.2 Postfix Evaluation6.4.3 Recursion6.4.4 Balancing of the Matching ParenthesisSummaryExercises
Chapter 7. Queues
7.1 Introduction7.2 Representation of a Queue7.2.1 Array Representation7.2.2 Linked Representation7.3 Operations on a Queue7.3.1 Enqueue and Deque Using Arrays7.3.2 Enqueue and Deque Using Linked List7.4 Circular Queues7.4.1 Operations on Circular Queue7.5 Deque7.5.1 Operations on a Deque7.6 Applications of Queues7.6.1 Simulation of Time-sharing System7.6.2 Queue ADTSummaryExercises
Chapter 8. Dictionaries
8.1 Dictionaries8.2 Linear List Representation8.3 Skip Lists Representation8.3.1 Operations8.3.2 Searching8.3.3 Insertion8.3.4 Deletion8.4 Hash Table8.4.1 Hash Functions8.5 Collisions8.5.1 Separate Chaining8.5.2 Open Addressing8.6 Comparison of Chaining and Open Addressing8.7 Applications8.8 Dictionary ADTSummaryExercises
Chapter 9. Trees and Binary Trees
9.1 Introduction9.2 Terminologies9.3 Representation of a Tree9.4 Binary Trees9.5 Representation of Binary Trees9.5.1 Array Representation of a Binary Tree9.5.2 Linked Representation of Binary Trees9.6 Binary Tree Operations9.7 Binary Tree Traversals9.7.1 Inorder Traversal (LVR)9.7.2 Preorder Traversal (VLR)9.7.3 Postorder Traversal (LRV)9.7.4 Level-order Traversal9.8 Conversion of a Tree into a Binary Tree9.9 Threaded Binary Trees9.9.1 Linked Representation of a Threaded Binary Tree9.10 Applications of Binary Trees9.10.1 Traversal of an Expression Tree9.10.2 Operations on Expression Trees9.11 ADT of Binary TreeSummaryExercises
Chapter 10. Graphs
10.1 Introduction10.2 Basic Terminology10.3 Representation of Graphs10.3.1 Sequential Representation of Graphs10.3.2 Linked Representation of Graphs10.4 Operations on Graphs10.5 Graph Traversals10.5.1 Breadth First Traversal10.5.2 Depth First Traversal10.6 Applications10.7 Graph ADTSummaryExercises
Chapter 11. Priority Queues
11.1 Introduction11.2 Priority Queue ADT11.3 Priority Queue Implementation Using Heaps11.3.1 Priority Queue Interface11.3.2 Min Heap-Insertion11.3.3 Min Heap-Deletion11.3.4 Max Heap-Insertion11.3.5 Max Heap-Deletion11.4 Applications11.4.1 Job Scheduling11.5 External Sorting11.5.1 Polyphase Merge11.5.2 Multiway MergeSummaryExercises
Chapter 12. Binary Search Trees and AVL Trees
12.1 Binary Search Trees12.2 Representation of a Binary Search Tree12.3 Operations on Binary Search Trees12.3.1 Searching12.3.2 Insertion12.3.3 Deletion12.3.4 Disadvantages of Binary Search Tree12.4 AVL Trees12.5 Operation of AVL Search Trees12.5.1 Searching12.5.2 Insertion12.5.3 Deletion12.6 ApplicationsSummaryExercises
Chapter 13. Multiway Trees and B Trees
13.1 Introduction13.2 Representation of a Node Structure13.3 Operations on m-Way Search Trees13.3.1 Searching13.3.2 Insertion13.3.3 Deletion13.3.4 Drawbacks of m-Way Search Trees13.4 B Trees13.5 Operations on B Trees13.5.1 Searching13.5.2 Insertion13.5.3 Deletion13.6 Height of B Trees13.7 Variations of B Tree13.7.1 B* Tree13.7.2 B+ Tree13.8 Applications13.8.1 DatabasesSummaryExercises
Chapter 14. Red-Black Trees and Splay Trees
14.1 Introduction14.2 Representation of a Red-Black Tree14.3 Operations14.3.1 Searching14.3.2 Insertion14.3.3 Deletion14.4 Splay Trees14.4.1 Splay Rotations14.4.2 Amortized Analysis14.5 ApplicationsSummaryExercises
Chapter 15. Pattern Matching and Tries
15.1 Introduction15.2 Terminology15.3 Pattern Matching Algorithms15.3.1 Fixed Pattern Matching Algorithms15.3.2 Regular Expression Pattern Matching15.4 Fixed Pattern Matching Algorithms15.4.1 Brute Force Pattern Matching Algorithm15.4.2 The Boyer-Moore Algorithm15.4.3 Knuth-Morris-Pratt Algorithm (KMP)15.5 Applications of Pattern Matching Algorithms15.6 Tries15.6.1 Standard Tries15.6.2 Compressed Tries15.6.3 Suffix Tries15.7 Applications of TriesSummaryExercises
Chapter 16. Sorting and Searching
16.1 Sorting16.1.1 Bubble Sort16.1.2 Insertion Sort16.1.3 Selection Sort16.1.4 Quick Sort16.1.5 Merge Sort16.1.6 Shell Sort16.1.7 Radix Sort16.1.8 Heap Sort16.2 Searching16.2.1 Linear Search or Sequential Search16.2.2 Binary Search16.2.3 Fibonacci SearchSummaryExercises
Solved Question Papers
Acknowledgements
Copyright

Content preview from Data Structures and Algorithms Using C++

Chapter 9 Trees and Binary Trees

In the previous chapters, linear data structures such as arrays, stacks and queues have been studied. Trees and graphs are two dimensional in structure and are referred to as non-linear data structures. The study of non-linear data structures is considered in this and forth-coming chapters. This chapter particularly deals with defining the tree data structure, the terminology related to them and their representation in different ways. A basic type of tree, i.e. binary tree is discussed in detail with its representation, operations and traversals. This chapter also includes threaded binary trees, ADT of binary trees, changing a general tree into a binary tree along with a detailed explanation about expression ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Data Structures and Algorithms Using C++ by Pearson

Publisher Resources

ISBN: 9788131755679

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Data Structures and Algorithms Using C++

by Ananda Rao Akepogu, Radhika Raju Palagiri

Chapter 9

Trees and Binary Trees

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.