Algorithm/Design and Analysis of Algorithms

Tree and B-Trees

Tony Lim 2020. 12. 30. 23:18
728x90

Why do we use B-Tree? if depth is still same as Binary tree 

Memory Hierarchy                   

if we use B-Tree we can utilize the whole block , instead if we use Binary tree we will have more disk io 

 

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

2-3Tree

Search

same as binary tree O(logn)

 

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

 

728x90

'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