Computer Science

Introduction:           It is an Algorithm of sorting taking O(nlog(n)) time to sort. This can be better understand by recursion like in merge sort. In this algorithm we take pivot and put it at its correct position after sorting its left and right side. A partition function return position of pivot in an array after placing all the smaller element left and all the larger right. Apply Quick sort to both side of pivot position.

 After insertion we perform correction from last to first element and after deletion we perform correction from first to last element. Heapify is method to convert any array to correct head. We can apply heapify anytime in the array. This is the best way to correct the heap.

It is similar to insertion and deletion. Insert the whole in a (Min or Max) heap. Delete the whole array by moving elements at last one by one. Example: Sort the given array                    arr[] = {9,4,8,2,5,6,7}     Apply Deletion:     Apply Deletion:     Apply Deletion:     Apply Deletion          Apply Deletion     Apply Deletion     Apply Deletion Sorted Array using Heap Sort After deletion Max Heap convert to Ascending order array After deletion Min Heap convert to Descending order array Time complexity of Inserting and Deleting an Element: O(log(n)+log(n)) Time complexity for performing above operation on n Element: O(n*2*log(n)) Therefore time complexity for Heap sort will be: O(nlog(n))

               Heap must be a complete(almost) binary tree. Types of Heap:      Max Heap -> For every node parent > child      Min Heap -> For every node parent < child Height ->                      log(n) Always

 Generally all the process is same as 2-3 Tree. So here we discuss the differences of 2-3-4 Tree from 2-3 Tree. Every Node must have at least ceil(n/2 here 4/2) children and maximum 4 children that's why is is called 2-3-4 tree b/c it will have 2 or 3 or 4 child of a node. Also called B-Tree of degree 4 Every node must be at same level Representation: Splitting:          When we insert element while node is full we will have even(4) number of elements so we can't divide element uniformly for splitting. So either we put more element to right, i.e. right biased or to left i.e. left biased.      Let we insert 40 in non-empty node: 

 According the property of Red-Black tree, no two Red node come together (as Parent-Child relation). So if it happens then we have to reordering the tree either by recoloring or by rotation. Note: Here NULL will considered as Black node If the uncle of the conflicting child is red:          Apply Recoloring:                    If G is root node then change it to black, also check if parent of G is red, if yes apply reordering recursively If the uncle of the conflicting child is Black:          Apply Rotation:                 Zig-Zig Rotation: This is similar to LL/RR rotation:                    Zig-Zag Rotation: This is similar to LR/RL rotation: Let us create a tree by using the following nodes:               10, 20, 30, 50, 40, 60, 70, 80, 4, 8     Insert 10:          As every insertion will be red so 10 will be red but it is the root node so it will become black      Insert 20:         20 > 10 so it will be on right side of 10 and there is no conflict b/w Red so no reordering  

Properties: It's a height balanced BST, similar to 2-3-4 Tree. Every Node is either Red or Black Root of  a tree is Black Null is also Black Number of Blacks on paths from Root to Leaf are same No 2 consecutive Red, children and parent of Red   is Black New inserted node is Red Height in logn <= h <= 2*logn (height of AVL is 1.44logn)

Insertion:               Let we create 2-3 tree by inserting elements:                                                                      20, 30, 40, 50, 60, 10, 15, 70, 80                Insert 20,30:               Now we insert these two element in a single node as it can hold 2 elements so,       Insert 40:               Node is already full so split the node             In splitting: We take two nodes left and right and a root node Left node contain smallest element Right node contain greatest element Root node contain middle element and take lest and right as child               So the final tree will be:      Insert 50:               50 is greater than 40 and after 40 a blank space so insert 50 in that blank space:     Insert 60:               60 is greater than 50 but there is no space for 60 so split, after splitting the root element will move to the root that contain 30 b/c there is an empty space in that node, so final tree will be:     Insert 10:               10 is smal