Why do we use B-Tree? if depth is still same as Binary tree
Memory Hierarchy
B-Tree (2-3Tree , B(branch factor)=2 )
B <= number of child <2B
B-1 <= number of keys < 2B-1
all the leaves are at same depth , no dangling children
Search
Insertion
even though we find right location we might have oveflow (where key is bigger than 2B-1) situation.
Split nodes into 2 part
1. remove the middle node
2. insert middle node into parent node
3. now parent might be overflow , we do this recursively until root (O(logn))
Deletion
now its underflow issue, number of keys need to be at most (B-1)
1. swap item to delete with inorder successor if time is not leaf
2. redistribute and merge nodes if there is underflowing
redistribution
1. look at sibling
1-1. if there is enough sibling's number of keys, which is at most 1 bigger than the minimum. you kinda rotate with parent key so sibling key goes to parent node and parent key goes to underflow node.
1-2 if there is only minimum we need to merge
reference == R2. 2-3 Trees and B-Trees - YouTube
'Algorithm > Design and Analysis of Algorithms' 카테고리의 다른 글
Graph Transform (0) | 2021.01.11 |
---|---|
Dijkstra , bellman-ford ,Bi-directional Djikstra (0) | 2021.01.05 |
Divide & Conquer: FFT (0) | 2020.12.27 |
Weighted Interval Scheduling (0) | 2020.12.26 |
Convex Hull , Median Find (0) | 2020.12.13 |