Learning Algorithms

Chapter 6. Binary Trees: Infinity in the Palm of Your Hand

In this chapter, you will learn:

• How to create and manipulate binary trees by inserting, removing, and searching for values.

• How to manage a binary search tree that enforces the global property that:

  • Values in the left subtree of a node are all smaller than or equal to that node’s value.

  • Values in the right subtree of a node are all larger than or equal to that node’s value.

• That search, insert, and remove operations can be O(log N) in balanced binary trees but can degrade to become an unacceptable O(N) if you aren’t careful.

• How to rebalance a binary search tree after insert and remove operations to guarantee O(log N) performance for search, insert, and remove.

• How to traverse a binary search tree to process each value in ascending order in O(N) performance.

• How to use a binary tree structure to implement a symbol table data type with the added benefit that its keys can be retrieved in sorted order.

• How to use a binary tree structure to implement a priority queue with the added benefit that you can generate the (key, value) entries in priority order without disrupting the priority queue.

Getting Started

Linked lists and arrays store information in a linear arrangement. In this chapter, I introduce the binary tree recursive data structure, one of the most important concepts in the field of computer science. In Chapter 5, you learned about the concept of recursion, where a function calls itself. ...