Comment on page

17.6 Summary

BSTs have best-case height Θ(log⁡N)\Theta(\log N)Θ(logN)
, and worst-case height Θ(N)\Theta(N)Θ(N)
.
Big O is not the same as worst-case!
B-Trees are a modification of the BST that maintain Θ(log⁡N)\Theta(\log N)Θ(logN)
 runtime for add and contains in the worst case. They maintain perfect balance during insertion.
A B-Tree has a limit LLL
 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.

17.5 B-Tree Performance

17.7 Exercises

Last modified 9mo ago