Please enable JavaScript.
Coggle requires JavaScript to display documents.
Tree Data Structure Non-Linear Data structure, (Algorithm Time…
Tree Data Structure
Non-Linear Data structure
Tree Types
Generic Tree
Usage:
Binary Tree
Usage:
AVL Tree
Usage:
Balance tree
Red Black Tree
Usage:
Operations on Tree
Generate/Create Tree
Serching
Depth First (DFS)
BreadthFirst(BFS)
Sorting
Update
Traversal
Pre-order ( VLR)
In- Order ( LVR )
Post- Order ( LRV)
Find efficiency
of program
Time Complexity
Asymptotic notations
Big O
O( )
Theta Q
Omega
Space Complexity
Properties
Depth from Root
Height from Leaf node
Algorithm Time Complexity
Best Average Worst
O(log n)
Binary Search
O(n)
Linear Search
O(nlog n)
Merge Sort
O(nsquare)
Bubble Sort
Selection Sort Ω(n^2) θ(n^2) O(n^2)
Bubble Sort Ω(n) θ(n^2) O(n^2)
Insertion Sort Ω(n) θ(n^2) O(n^2)
Heap Sort Ω(n log(n)) θ(n log(n)) O(n log(n))
Quick Sort Ω(n log(n)) θ(n log(n)) O(n^2)
Merge Sort Ω(n log(n)) θ(n log(n)) O(n log(n))
Bucket Sort Ω(n+k) θ(n+k) O(n^2)
Radix Sort Ω(nk) θ(nk) O(nk)
O(n3) - n qube
Tree Algo
DFS ( Depth )
Use of STack data structure
Inorder
preorder
postorder
BFS ( Breadth )
use of Queue data structure
linear search
Time complexity O(n)
Binary Search
Time complexity: o(log n)
Print height of tree
print diameter of tree
Print tree column wise
Linked List
Multi linked Data structure
Sparse matrix
SLL
DLL
CLL
Sorting
Merge Sort
Divide and conquor
Quick Sort
Selection Sort
Bubble Sort
Time complexity: O(n2)
Space Complexity: O(1)
Graph
Types
Direction
directed
undirected
Weighted
weighted/unweighted
Cycle
cyclic
acyclic
Adjucansy matrix
Sequencial data representation
Adjustancy list -
linear linked data
Hash Table
Collision as problem
Chaining
Probing
Quadratic Probing
Double hashing
Hash Function
HashMap(Key, Value)
Greedy Algorithm
shorted path/MST
Dijkshtras
source --> Destination
only positive weights
bellman ford algo
can handle -ve weights
prims MST
Undirected graph only
kruskals
floyd warshall
knapsack problem
huffman coding
Reducing size of char
Stack
Operations
Create
Push
Pop
print
Traversal
In-fix
Pre-fix
Post-Fix
Algorithm
Huffmans Algorithm
Store frequncy of occuring data member
memoization
storing frequent operation result ( e.g. fibonacci)
Queue
Operations
Create
Enqueue
Dequeue
Print
Heap
Hash Table