Fundamentals of Data Structure PDF

CSE408 in Fundamentals of Data y. ud Stru...

CSE408 in Fundamentals of Data y. ud Structure st ty si er iv un Lecture #2 Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Fundamental data structures list graph in array tree and binary tree y. ud linked list set and dictionary st string ty si er stack iv un queue priority queue/heap Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Linear Data Structures Arrays ◼ Arrays in A sequence of n items of the same data ◼ fixed length (need preliminary y. type that are stored contiguously in reservation of memory) ud computer memory and made accessible ◼ contiguous memory locations by specifying a value of the array’s direct access st index. ◼ Insert/delete ty Linked List ◼ si Linked Lists A sequence of zero or more nodes each◼ er containing two kinds of information: some data and one or more links called ◼ dynamic length iv pointers to other nodes of the linked ◼ arbitrary memory locations un list. ◼ access by following links Singly linked list (next pointer) ◼ Insert/delete Doubly linked list (next + previous pointers) a1 a2 … an. Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Stacks and Queues Stacks A stack of plates in – insertion/deletion can be done only at the top. y. – LIFO ud Two operations (push and pop) st Queues ty A queue of customers waiting for services si er – Insertion/enqueue from the rear and deletion/dequeue from the iv front. un – FIFO Two operations (enqueue and dequeue) Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Priority Queue and Heap ◼ Priority queues (implemented using heaps) in y. ◼ A data structure for maintaining a set of elements, ud each associated with a key/priority, with the following operations st ty ◼ Finding the element with the highest priority si Deleting the element with the highest priority er ◼ iv ◼ Inserting a new element 9 un ◼ Scheduling jobs on a shared computer 6 8 5 2 3 9 6 8 5 2 3 Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Graphs Formal definition A graph G = is defined by a pair of two sets: a in finite set V of items called vertices and a set E of vertex y. pairs called edges. ud Undirected and directed graphs (digraphs). st What’s the maximum number of edges in an undirected graph ty with |V| vertices? Complete, dense, and sparse graphs si er A graph with every pair of its vertices connected by an edge iv un is called complete, K|V| 1 2 3 4 Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Graph Representation Adjacency matrix n x n boolean matrix if |V| is n. in y. The element on the ith row and jth column is 1 if there’s an edge ud from ith vertex to the jth vertex; otherwise 0. The adjacency matrix of an undirected graph is symmetric. st ty Adjacency linked lists si A collection of linked lists, one for each vertex, that contain all the er vertices adjacent to the list’s vertex. iv Which data structure would you use if the graph is a 100-node star un shape? 0111 2 3 4 0001 4 0001 4 0000 Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Weighted Graphs Weighted graphs Graphs or digraphs with numbers assigned to the edges. in y. ud 5 st 1 2 ty 6 7 9 si 3 8 4 er iv un Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Graph Properties -- Paths and Connectivity Paths in A path from vertex u to v of a graph G is defined as a sequence of y. adjacent (connected by an edge) vertices that starts with u and ends with ud v. Simple paths: All edges of a path are distinct. st ty Path lengths: the number of edges, or the number of vertices – 1. si Connected graphs er A graph is said to be connected if for every pair of its vertices u and v iv there is a path from u to v. un Connected component The maximum connected subgraph of a given graph. Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Graph Properties -- Acyclicity Cycle in A simple path of a positive length that starts and ends a y. ud the same vertex. st Acyclic graph ty A graph without cycles si er DAG (Directed Acyclic Graph) iv un 1 2 3 4 Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Trees Trees A tree (or free tree) is a connected acyclic graph. Forest: a graph that has no cycles but is not necessarily connected. in Properties of trees y. ud For every two vertices in a tree there always exists exactly one simple st path from one of these vertices to the other. Why? ty – Rooted trees: The above property makes it possible to select an si arbitrary vertex in a free tree and consider it as the root of the so er called rooted tree. iv – Levels in a rooted tree. un rooted 3 ◼ |E| = |V| - 1 1 3 5 4 1 5 2 4 2 Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Rooted Trees (I) Ancestors For any vertex v in a tree T, all the vertices on the simple path from the root to that vertex are called ancestors. in Descendants y. All the vertices for which a vertex v is an ancestor are said to be ud descendants of v. st Parent, child and siblings ty If (u, v) is the last edge of the simple path from the root to si vertex v, u is said to be the parent of v and v is called a child of er u. iv Vertices that have the same parent are called siblings. un Leaves A vertex without children is called a leaf. Subtree A vertex v with all its descendants is called the subtree of T rooted at v. Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Rooted Trees (II) Depth of a vertex in The length of the simple path from the root to the vertex. y. ud Height of a tree st The length of the longest simple path from the root to a leaf. ty si er iv h=2 un 3 4 1 5 2 Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1 Ordered Trees Ordered trees An ordered tree is a rooted tree in which all the children of each vertex are ordered. in Binary trees y. A binary tree is an ordered tree in which every vertex has no more than ud two children and each children is designated s either a left child or a right st child of its parent. ty Binary search trees si Each vertex is assigned a number. er A number assigned to each parental vertex is larger than all the numbers iv in its left subtree and smaller than all the numbers in its right subtree. un log2n  h  n – 1, where h is the height of a binary tree and n the size. 9 6 6 8 3 9 5 2 3 2 5 8 Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1  in y. ud st ty si er iv un Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1