DataStructures Quick Notes:

Complete Binary Tree:
==================

Total number of Nodes :
2pow(n+1)-1


Internal Nodes:
1 to [n/2]


Leaf nodes:
[n/2]+1 to n


Max no. of nodes at a level or height:
n/[2pow(h+1)]


====================================================


How many distinct binary search trees can be created out of 4 distinct keys?
Ans:
No. of BST= 2nCn/(n+1)
Therefore 8C4/5 =14

=======================================================

A binary tree T has 20 leaves. The number of nodes in T having two children is ______.

Ans:
In Binary tree If there are N leaf nodes then the number of Nodes having two children will be N-1. So in this case answer will be 20-1, means 19.

=======================================================

*** A complete graph Kn has  power(n, n-2) spanning trees.

=======================================================


Simple Graph
A graph with no loops and no parallel edges is called a simple graph.
* The maximum number of edges possible in a single graph with ‘n’ vertices is nC2 where nC2 = n(n – 1)/2.

* The number of simple graphs possible with ‘n’ vertices = 2nc2 = 2n(n-1)/2.




The maximum number of edges with n=3 vertices −
nC2 = n(n–1)/2
   = 3(3–1)/2
   = 6/2
   = 3 edges

The maximum number of simple graphs with n=3 vertices −
2nC2 = 2n(n-1)/2
   = 23(3-1)/2
   = 23
   = 8


=======================================================

Example 1:
Let ‘G’ be a simple graph with nine vertices and twelve edges, find the number of edges in 'G-'.

You have, |E(G)| + |E('G-')| = |E(Kn)|

12 + |E('G-')| =  9(9-1) / 2 = 9C2
12 + |E('G-')| = 36

|E('G-')| = 24


=======================================================

Example 2:
‘G’ is a simple graph with 40 edges and its complement 'G−' has 38 edges. Find the number of vertices in the graph G or 'G−'.

Let the number of vertices in the graph be ‘n’.

We have, |E(G)| + |E('G-')| = |E(Kn)|

40 + 38 = n(n-1)/2

156 = n(n-1)

13(12) = n(n-1)

n = 13

=======================================================


Circuit Rank
Let ‘G’ be a connected graph with ‘n’ vertices and ‘m’ edges. A spanning tree ‘T’ of G contains (n-1) edges.
Therefore, the number of edges you need to delete from ‘G’ in order to get a spanning tree = m-(n-1), which is called the circuit rank of G.


Example 1:

For the graph given in the above example, you have m=7 edges and n=5 vertices.

Then the circuit rank is

G = m – (n – 1)
  = 7 – (5 – 1)
  = 3

=======================================================


Example 2:

Let ‘G’ be a connected graph with six vertices and the degree of each vertex is three. Find the circuit rank of ‘G’.

By the sum of degree of vertices theorem,

n
∑
i=1 deg(Vi) = 2|E|

6 × 3 = 2|E|

|E| = 9

Circuit rank = |E| – (|V| – 1)

= 9 – (6 – 1) = 4

=======================================================


Euler’s Path
An Euler’s path contains each edge of ‘G’ exactly once and each vertex of ‘G’ at least once. A connected graph G is said to be traversable if it contains an Euler’s path.
Example

Euler’s Path = d-c-a-b-d-e.


=======================================================


Example 3:

Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.

Solution:

By the sum of degrees theorem,

20
∑
i=1 deg(Vi) = 2|E|

20(3) = 2|E|

|E| = 30


By Euler’s formula,

|V| + |R| = |E| + 2

20+ |R| = 30 + 2

|R| = 12

Hence, the number of regions is 12.

=======================================================

A self-complementary graph is a graph which is isomorphic to its graph complement.

All self-complementary graphs have graph diameter 2 or 3
A disconnected graph has infinite diameter


By definition, a self-complementary graph must have exactly half the total possible number of edges, i.e., n(n-1)/4 edges for a self-complementary graph on n vertices. Since n(n-1) must be divisible by 4, it follows that n=0 or 1 (mod 4).


=======================================================


Red-Black Tree

An extended rooted binary tree satisfying the following conditions:
1. Every node has two children, each colored either red or black.
2. Every tree leaf node is colored black.
3. Every red node has both of its children colored black.
4. Every path from the root to a tree leaf contains the same number (the "black-height") of black nodes.

=======================================================