Data Structures cheat sheet

DataStructuresCheatSheet

Pre-Oreder:
	root-->left-->right
In-Oreder:
	left-->root-->right
Post-Oreder:
	left-->right-->root
==================================================
Sorts:

Max-Sort:
		Take always the max value from the array n times,
		and swap it with the last value in the array till the array is sorted.
				
		Pros:
			Realy simple and quick to implement.

		Cons:
			O(N^2) time complexity.
Bubble-Sort:
		Swap the value a[i] in the array with a[i+1] (depends on the predicate).
		
		Pros:
			Can stop in the middle if the array is sorted.
		
		Cons:
			O(n^2) time complexity.

Insert-Sort:
		Take an element from the array and put it in a new sorted array.

		Pros:
			After i steps we will get a sorted array of size i.
		Cons:
			O(n^2) time complexity.


Heap-Sort:
		1.Build a heap of n variables in O(n) time complexity.
		
		2.Pop out n maximums each pop takes O(log n).

		Pros:
			Time complexity of the sort = O(n*log n).
		Cons:
			No lieanrity

Quick-Sort:
		1.Choose pivot O(n).
		2.Split to x < pivot and x > pivot.
		
		run to pointers until we will see to elements in the wrong place and swap.
		
		stop when the two pointers swaped.
Merge-Sort:


============================================
Linear Time Sorts:

Counting/Bucket-Sort:

		
Radix-Sort:
		
		
==============================================
Search Trees:

1.Binary Tree.
2.Key-Value at each node.
3.Conforms to the search tree propety
	-Left tree smaller than root.
	-Right tree larger than root.		
		
--------
1.Find-O(height)
2.Add-O(height)
3.Remove
		1.Find-O(height).
		
		Not Found-Do nothing.

		1.Child replace the node with the child-O(1).
		2.Children-
			replace with the next previous if it was sorted.
			previous the maximum of the left tree.
			next-the minimum if the right tree.