Comment on page
17.6 Summary
- BSTs have best-case height, and worst-case height.
- Big O is not the same as worst-case!
- B-Trees are a modification of the BST that maintainruntime for
add
andcontains
in the worst case. They maintain perfect balance during insertion. - A B-Tree has a limiton the number of values a node can hold, instead of having one item per node like a BST.
- Upon
add
in a B-Tree, we simply append the value to an existing leaf node in the correct location instead of creating a new leaf node. If the node is too full, it splits and pushes a value up.
Last modified 9mo ago