Comment on page

# 17.6 Summary

- BSTs have best-case height$\Theta(\log N)$, and worst-case height$\Theta(N)$.
- Big O is
*not*the same as worst-case! - B-Trees are a modification of the BST that maintain$\Theta(\log N)$runtime for
`add`

and`contains`

in the worst case. They maintain perfect balance during insertion. - A B-Tree has a limit$L$on 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