2-3-4 Tree
Nodes hold one to three keys. Isomorphic to red-black trees.
B-Tree: A 2-3-4 tree: three keys per node
10 20 50 70 has 4 keys and the limit is 3, so it splits. The middle key, 50, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Cost
- Search
- O(log n)
- Insert
- O(log n)
- Delete
- O(log n)
- Space
- O(n)
Before this
Related
Taught by the same lesson
B-Tree covers these too, in the same run.