Skip to main content


Showing posts with the label Data Structure

What is B+ tree ?

B+ TreeWhat 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 

What Is B-tree

B-treeWhat 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) . AdvantageOf B-tree :                             1) Keeps keys in sorted order for sequential traversing .

What is Splay Tree

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)

What Is Red-Black Tree

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                                                        2) N is parent (p) is black .  …

Storage Allocation Strategies (Static allocation, Stack allocation, Heap Allocation)

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

Disadvantage : Heap Management is Overhead