Tree

 

The tree with no nodes is called the null or empty tree.

A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy.

Tree: undirected, connected graph with no cycles

Examples:

  • The file system on the computer where we want to sort files by folder structure or size in the same folder.
  • Manipulate hierarchical data.
  • Make information easy to search
  • Manipulate sorted lists of data.
  • Multi-stage decision-making
  • Authorization (e.g. Admin--> All--> RW--> R)
  • Javascript document object model

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Binary Search Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Cartesian Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n)  O(n)  O(n)  O(n)

B-Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Red-Black Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Splay Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n)

AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

KD Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Graph

Graph is a data structure that consists of following two components:

  1. A finite set of vertices also called as nodes.
  2. A finite set of ordered pair of the form (u, v) called as an edge.

 

  • The pair is ordered because (u, v) is not same as (v, u) in the case of a directed graph(di-graph).
  • The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.
    • V -> Number of Vertices.
    • E -> Number of Edges.

 

Graph Classification:

The graph can be classified on the basis of many things, below are the two most common classifications:

  1. Direction Graph:
    • Undirected Graph: The graph in which all the edges are bidirectional.
    • Directed Graph: The graph in which all the edges are unidirectional.
  2. Weight Graph:
    • Weighted Graph: The Graph in which weight is associated with the edges.
    • Unweighted Graph: The Graph in which there is no weight associated with the edges.

 

Time Complexities:

  • Time Complexities in a case of Adjacency Matrix:
    • Traversal :(By BFS or DFS) O(V^2)
    • Space: O(V^2)
  • Time Complexities in the case of Adjacency List:
    • Traversal :(By BFS or DFS) O(ElogV)
    • Space: O(V+E)

Examples :

  • Google map
  • Represent network
    • Telephone
    • Social Networking sites

Representations of Graph:

  1. Adjacency Matrix
    • It is a 2D array of size V x V where V is the number of vertices in a graph.
  2. Adjacency List
    • Implemented using array of linked list.
    • Size of the array is equal to number of vertices
    • Used to represent a weighted graph
      • Weights of edges can be stored in nodes of linked lists
  3. Incidence Matrix
  4. Incidence Lis