Institute Academy

                                   B+ Tree What is B+ Tree ? B+ Tree : A B+ tree is an N-ary tree with a variable but often earge number of children per node . A B+ tree Consist Three Thing                                                1) Root                                               2) Internal node                                               3) External node or leaf node A B+ tree can be viewed as a B-tree in which each node contain only keys and to an additional level is added at the bottom with linked leaves .                                                    Time Complexity of  B+ Tree   : Insertion , Deletion and searching all cases are take time in worst case is O( log n ) . Space Complexity  of  B+ Tree  : Space Complexity in worst Case is O(n) . Properties   of  B+ Tree  :                        b =  Order of the B+ Tree 

                                     B-tree What is B-tree ?  B-tree : A b-tree is a self-balancing Tree data Structure  . it maintains sorted data and allows searches , Sequential access , insertion and deletion in O( log n ) Time . Properties Of B-tree : A B-tree of order M is a tree which satisfied the following properties                          1) Every Node At most M children                         2) Every non-leaf node has at least ⌈ M /2⌉Child nodes .                         3) The root has at least two children if it is not a leaf node .                         4) A non-leaf node with k children contains k-1 keys .                         5) All leaves appear in the same level . Time Complexity Of B-tree : Insertion , deletion and searching all operation are worst case time complexity is O(log n) . Space Complexity Of B-tree : worst case is  O(n) . Advantage   Of B-tree :                             1) Keeps keys in sort

                                Splay Tree What is Splay Tree ?  Splay Tree : A Splay Tree is a Self-Adjusting Binary search Tree with the additional property that recently accessed element are quick to access again . Time Complexity Of  Splay Tree   : average case = O( log n ) and worst case = O(n) .   Space Complexity  Of  Splay Tree    : both Cases Average and worst cases show O(n) . Advantage  Of  Splay Tree     :                            1) Comparable performance : Average case performance is as efficient ( O)log n ) ) .                           2) Small Memory footprint : Splay trees do not need to store any bookkeeping data . Disadvantage :                                   1) The height of Splay tree can be linear                                  2 ) worst case Time Complexity is O(n)

                          Red-Black Tree What is Red-Black Tree ? Red Black Tree : A Red Black Tree is a kind of Self-Balancing binary search Tree in Computer Science .  Properties :                             1)  Root node is always Black if Root Node is red then you have to change into black.                           2) each node either red or black .                           3) All leaves ( Nil ) are black .                           4) if a node is red then it's both children is black .                           5) every path from a given node to any its descendant nil node contains the same number of black nodes . Time Complexity : worst case = O( log n ) Space Complexity : Worst case = O( n ) Insertion : Insertion is very similar manner as a binary search tree . Insertion Follows few's property                                                          1) N is the root node , i.e , first node of the red black tree     

                  Run time Environment Storage Allocation Strategies : There are three type Storage Allocation Strategies        i) Static Allocation        ii) Stack Allocation         iii) Heap Allocation 1) Static Allocation :  i) Allocation is done at Compile Time                               ii) Binding Do not Change at run time                               iii) one activation record per procedure Disadvantage : i) Recursion is not supported                         ii) size of data object must be known at compile time                         iii) data structure can not be created dynamically 2) Stack Allocation : i) whenever a new activation begin activation record is pushed on to the stack and whenever activation ends, activation record is popped off. local variable are bound to fresh storage. disadvantage : local variable can not be retained once activation end 3) Heap allocation : allocation and Deallocation can be in any order