8 Balanced trees

In this chapter

  • You learn about a new data structure called binary search trees (BSTs).
  • You learn about balanced trees and why they often perform better than arrays or linked lists.
  • You also learn about AVL trees, a type of balanced BST. In the worst-case scenario, binary trees can be slow. A balanced tree will help them perform effectively.

In the last chapter, you learned about the new data structure, trees. Now that you and trees are best friends, it’s time to see what they are used for. When arrays and linked lists fail to deliver the desired performance, a good next step is to try a tree. In this chapter, we’ll discuss the performance that trees can offer. We’ll then explore a special type of tree that can offer exceptional ...

Get Grokking Algorithms, Second Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.