Linear Data Structures

• Array
• Linked list
• Stack
• Queue
• Priority Queue
• Heap

Nonlinear Data structures

• Graphs
• Directed
• Undirected
• Veighted
• Trees

Graph representation G = (V,E) V set of vertices, E set of edges

• Adjacency list
• Adjacency matrix

Some definitions for undirected graphs:

• Path from vertex u to vertex v is sequence of adjacent vertices that starts with u and ends with v.

• Simple path is a path where all edges connecting adjacent vertices are different.

• Path length is number of edges in the path. (one less than the number of vertices in the path)

• Cycle – simple path that starts and ends in the same node.

• Acyclic graph – graph with no cycle

• Connected graph – graph satisfying the property that every two vertices in it are connected with some path.

• Tree (Free tree) – connected acyclic graph.

• Forest – acyclic graph (or collection of trees)

GRAPH PROPERTIES:

• If graph is a tree then |E| = |V| - 1.

• If |E|= |V|-1 it does not necessarily mean that graph G = (V, E) is a tree. Example Fig 1.9 page 32.

• For every two vertices in a tree there exists exactly one simple path between the two vertices.

• In a connected acyclic graph (free tree) we can select an arbitrary vertex and consider it as a root of the so called rooted tree. (Fig 1.11 page 33)

Definitions for Rooted Trees

• Ancestors of a vertex v – all the vertices on a path from the root to v.

• The vertex itself is considered its own ancestor.

• Proper ancestors of vertex v – The set of all ancestors without the vertex v itself.

• Descendants of vertex v – all the vertices for which vertex v is an ancestor.

• Parent of v is vertex adjacent to v on the path from v toward the root.

• Vertex v is child of vertex u if u is parent of v.

• Siblings of v are all vertices that have the same parent as vertex v.

• Subtree of a tree T rooted at vertex v is vertex v together with all its descendants.

• Leaf – vertex with no children.

• Depth of a vertex v is the length of the simple path from the root to v.

• Height of a tree T is the length of the longest path from the root to a leaf. A single node has height 0 and empty tree has height -1.

• Ordered tree is a rooted tree in which all the children are ordered.

• Binary tree is an ordered tree in which every vertex has at most two children.

• Binary Search Trees are binary trees where vertices have labels such that labels of the vertices in left subtree are smaller than the label of the vertex and labels of the vertices in the right subtree have labels that are larger than the label of the vertex. If we allow duplicates equality is added on one side.

BST implementation

Page 35 Fig 1.13

First child – next sibling representation of ordered tree.