Non-Linear Data

Structures
 Tree
In computers, a tree is an abstract model of a hierarchical structure
A tree consists of nodes with a parent-child relation
Applications: Organization charts, File systems, Programming
environments A
Root: node without parent (A)
Internal node: node with at least one child B C D
(A, B, C, F)
E F G H
External node (or leaf node ): node without
children (E, I, J, K, G, H, D) I J K

Ancestors of a node: parent, grandparent etc.

Depth of a node: number of ancestors
Height of a tree: maximum depth of any node (3)
Descendant of a node: child, grandchild etc.
Subtree: tree consisting of a node and its descendants
Siblings: Children of the same parent
Operations on a tree
 size()
 isEmpty()
 root()
 parent(p)
 children(p)
 isInternal(p)
 isExternal(p)
 isRoot(p)
 swapElements(p, q)
 replaceElement(p, o)
 Binary Tree
 is a tree in which each internal node has at
most two children
 Ordered Binary Tree
 The children of a node are an ordered pair
and are referred as left child and right child
 Alternative recursive definition: a binary
tree is either a tree consisting of a single
node, or whose root has an ordered pair of
children, each of which is a binary tree
 Complete Binary tree which consists of
each internal node having exactly two
children.
 Perfect or full binary tree will have each
internal node having two children and all
leaf nodes will be at the same level
 Arithmetic expressions, decision processes,
searching
Binary Tree
 n number of nodes
 e number of external nodes
 i number of internal nodes
 h height

 h  i For Binary trees

 Properties: For Complete Binary Tree
 e=i+1
 n = 2e – 1

 h  (n - 1)/2

 e  2h
 h  log2 e
 h  log2 (n + 1) - 1
 Traversals in a tree
 A traversal visits the nodes of a tree in a systematic manner
 In a preorder traversal, a node is visited before its descendants
 Application: print a structured document
a
 In a postorder traversal, a node is visited after its
descendants b e

 Application: compute space used by files in a c d

directory and its subdirectories f g

 Specialization of an inorder traversal

 Preorder abcdfge Postorder cfgdbea Inorder
cbfdgae
 Evaluating arithmetic operation is equivalent to a postorder
traversal
Given pre and inorder

 Preorder abcdfge Inorder cbfdgae

 From preorder we know that a is the root, now
find a in the inorder traversal
 Now I know e is the right subtree
 We are left with the subtree
 bcdfg cbfdg
 dfg fdg
 Given pre and post order
 We cannot find inorder because there can be two trees with the
same pre and post order
 pre a b c
 post c b a
 If each internal node of the binary tree has at least two children
then the tree can be determined from pre and post order
traversals.
 pre post
 abcdfge c f g d b e a from this I know that a is the
root then I know that e is the right child of a from post order and
from Preorder I see that there is nothing after e so e is the leaf
 bcdfg cfgdb
 Now I see that b is the root of the left sub tree and d is the right
children ( from post order) and then from inorder I see that c is the
only child of d which is the left child and so on.
Successor

 Given x, find the node with the

smallest key greater then key[x]
 we can distinguish two cases depending upon
the right subtree of x
 case 1: Right subtree of x is nonempty, then
successor is leftmost node in the right subtree
 case 2: The right subtree of x is empty, then the
successor is the closest ancestor v of x such that
x is descended from the left child of v.If there is
no such ancestor then successor is undefined.
Insertion
 take an element whose left and right children are null and
insert it into T
 find place in T where z belongs (as if searching for z)
and add z
 Runtime on a tree of height h is O(h)
 Deletion case 1
if x has no children : just remove x
Deletion Case 2
if x has exactly one child then to delete x simply make p[x]
point to that child
 Deletion Case 3
 if x has two children, then to delete it we have to find its
predecessor(going left and finding the rightmost node) or
successor y
 Replace x with y (it will have at most one child) and delete y
Deletion

Running time for delete in worst case is O(h)

Inorder traversal of a BST gives a sorted list and taken O(n) time.
 Graph
 A graph is a pair(V,E) where V is set of nodes called
vertices E is a collection of pair of vertices called
edges. vertices and edges are positions and store
elements
 Directed Edge: ordered pair of vertices(u,v) where
first vertex u is the origin and second vertex v is
the destination
 Undirected Edge:unordered pair of vertices for
example distance between two cities
 In Directed graph all the edges are directed and in
undirected graph all the edges are undirected
 Electronic circuits, printed circuit boards,
Integrated Circuits, Transportation network,
Highway network, rail network, flight network,
traffic network, electricity network, water
network, Computer networks, LAN, Web ,
Databases- ER diagrams
 Graphs
 End vertices of an edge U and V are the endpoints of a
 Edge incident on a vertex a, d,b are incident on v
 adjacent vertices u and v are adjacent
 Degree of a vertex : x has degree 5
 If All vertices have the same degree it is called the
regular graph.
 parallel edges: h and i are parallel edges
 Self loop : j is a self loop
 Graphs
 path-sequence of alternating vertices and edges
 begins with a vertex and ends with a vertex
 each edge is preceded and followed by its
endpoints
 Simple path- a path such that all edges and
vertices are distinct
 v,b,x,h,z is a simple path
 u,c,w,e,x,g,y,f,w,d,v is not a simple path
 cycle- circular sequence of alternating vertices and
edges
 each edge is preceded and followed by its endpoints
 Simple cycle : such that all its vertices and edges are
distinct
 v,b,x,g,y,f,w,c,u,a,v is a simple cycle
 u,c,w,e,x,g,y,f,w,d,v,a, u is not a simple cycle
Operations on a graph
 incidentedges(v)
 endvertices(e)
 isdirected(e)
 origin(e)
 destination(e)
 opposite(v,e)
 areadjacent(v,w)
 insertvertex(o)
 insertedge(v,w,o)
 insertdirectededge(v,w,o)
 removevertex(v)
 removeedge(e)
 numvertices()
 numedges()
 Sub Graph: A Graph consisting of Subset of edges and
subset of vertices of another graph is a sub graph of that
graph.
 A connected graph without cycles is a tree
 A Collection of trees is called a forest.
 m=no. of edges n= no. of vertices
 for a trees m=n-1 if m<n-1 Graph is not connected
Incidence matrix

 The graph is represented by a matrix of size |V| (number of

vertices) by |E| (number of edges) where the entry [vertex,
edge] contains the edge's endpoint data (simplest case: 1 -
incident, 0 - not incident).

U V W X

A 1 1 0 0
B 0 1 0 1

C 1 0 1 0
D 0 1 1 0

E 0 0 1 1
Adjacency matrix

 This is an n by n matrix A, where n is the number of vertices

in the graph. If there is an edge from a vertex x to a
vertex y, then the element ax,y is 1 (or in general the number
of xy edges), otherwise it is 0. Every element in matrix can
be represented by a single bit. However in case of sparse
graphs it can be a waste of space and time. In computing,
this matrix makes it easy to find subgraphs, and to reverse
a directed graph

U V W X
U 0 1 1 0
V 1 0 1 1
W 1 1 0 1
X 0 1 1 0
 Adjacency List
 an array indexed by vertex numbers points to a singly-linked list of
the neighbors of each vertex.
 In a complete graph each pair of vertices is joined by an edge, that
is, the graph contains all possible edges.
 In a bipartite graph, the vertices can be divided into two
sets, W and X, so that every edge has one vertex in each of the two
sets.
 A planar graph can be drawn in a plane with no crossing
edges (i.e., embedded in a plane).
 Eulerian path is a path in a graph which visits
each edge exactly once and returns to the starting vertex.
A Graph has a Eulerian Path if all vertices have even
degree.
 Hamiltonian path (or traceable path) is a path in an undirected
graph which visits each vertex exactly once. Hamiltonian
cycle (or Hamiltonian circuit) is a cycle in an undirected graph which
visits each vertex exactly once and also returns to the starting
vertex.
 Independent set or stable set is a set of vertices in a graph, no two of
which are adjacent. That is, it is a set I of vertices such that for every
two vertices in I, there is no edge connecting the two.
 A maximum independent set is a largest independent set for a given
graph G.
 Maximum Independent set is { U,Z,Y}
Vertex Cover

 Vertex cover of a graph is a set of vertices such that each edge

of the graph is incident to at least one vertex of the set. A
vertex cover of a graph G is a set C of vertices such that each
edge of G is incident to at least one vertex in C. The set C is
said to cover the edges of G. Figure shows vertex covers in two
graphs (the set C is marked with red).
 Minimum vertex cover is vertex cover of smallest possible size.
Clique

 Clique in an undirected graph G = (V, E) is a subset of

the vertex set such that for every two vertices in the subset,
there exists an edge connecting the two.
 A maximum clique is a clique of the largest possible size in a
given graph