CS 240: Lecture 26 – Binary Search Trees
Dear students:
Fall break is over. Just four more weeks to the next one. And then two more weeks of the semester after that. Then finals. Then whew. In the weeks that we have left we’ll be talking about trees, dictionaries, hashing, and graphs. The good news is that these are all useful tools. The bad news is that we are caught up in a system of grades and rigid schedules.
Last time we started exploring binary trees. We saw that a tree is a structure with a single root that has trees as its children. The defining characteristic of a binary tree is that each node has no more than two children. That’s it. Some of these rules can be relaxed. If you take away the hierarchy, removing the concept of a single root node and the supervisory role of parents over their children, then you end up with a graph.
Trees are a more abstract concept than lists. We humans can think of sequences all day long: books in a series, ex-friends, ex-presidents, and so on. But tree structures, especially ones that benefit from computation, are less intuitive. I can think of the following situations where a tree might come in handy:
- modeling a file system
- doing collision detection in 3D space
- representing a program
- structuring a skill-tree in an RPG
What do all these things have in common? Branching and recursion. Those are the qualities that trees nicely capture.
A tree whose children each only have 0 or 2 nodes is a full tree. No single-child parents are allowed. A full tree is truly binary. We could have used a better name than full. Maybe dyadic, two-sibling, or double-or-nothing trees. A leaf node in a full tree doesn’t have to be at the bottom level. You saw full trees in the expression lab last week. The operator nodes always had two children, and the operand nodes always had 0, as in this tree:
* / \ + 7 / \ 1 - / \ 5 2
Why is the fullness of a binary tree a quality worth knowing? I don’t know, but it does seem like the kind of trivia that one can test students on. There are other similar but more important qualities on the tree landscape, and it may get some of its importance by being a counterpoint to these other qualities.
A tree that is full and has all of its leaves at the bottom is called a perfect tree. It has no holes. Its number of nodes is the sum of a sequence of powers of 2. It’s easier to reason about a perfect tree than the others because it has a uniform structure.
If a perfect tree loses some leaves, but only the rightmost ones, it is demoted to a complete tree. Complete trees are worth knowing about because they can be stored in an array rather than a linked structure. That simplifies storage. We will talk more about complete trees later when we see the heap data structure, which has nothing to do with heap memory, just as a stack has little to do with stack memory. A complete tree is not necessarily full because there may be one parent with only one child.
Binary Search Trees
Today we discuss binary search trees, which are a special kind of binary tree. In a binary search tree, the nodes are ordered. The root is greater than its left descendents and less than its right descendents. This property holds recursively throughout the tree. We’ll examine how to search for and add values to a binary search tree. Deleting nodes is a bit more work.
The binary search trees is important because is a structure that naturally supports a binary search. Unlike a sorted array, it is a linked tree. The linkedness may confer other benefits.
For the remainder of our time together, you’ll work through some exercises on binary search trees with your neighbors.
TODO
You have some work to do before the next class:
- Submit the expression lab before 11 PM tonight.
- Read 10.11-10.12, 15.05 from OpenDSA and the AVL Trees excerpt.
- Complete the AVL tree quiz.
- Keep working on PA3.
See you next time.
P.S. It’s time for a haiku!
That tree is all trunk
It is far too tall to climb
Split it into logs