Binary Trees
- Why Use Binary Trees?
- Tree Terminology
- An Analogy
- How Do Binary Search Trees Work?
- Finding a Node
- Inserting a Node
- Traversing the Tree
- Finding Minimum and Maximum Key Values
- Deleting a Node
- The Efficiency of Binary Search Trees
- Trees Represented as Arrays
- Printing Trees
- Duplicate Keys
- The BinarySearchTreeTester.py Program
- The Huffman Code
- Summary
- Questions
- Experiments
- Programming Projects
Binary trees are one of the fundamental data storage structures used in programming. They provide advantages that the data structures you’ve seen so far cannot. In this chapter you learn why you would want to use trees, how they work, and how to go about creating them.
This chapter is from the book
This chapter is from the book
This chapter is from the book
In This Chapter
Why Use Binary Trees?- Tree Terminology
- An Analogy
- How Do Binary Search Trees Work?
- Finding a Node
- Inserting a Node
- Traversing the Tree
- Finding Minimum and Maximum Key Values
- Deleting a Node
- The Efficiency of Binary Search Trees
- Trees Represented as Arrays
- Printing Trees
- Duplicate Keys
- The BinarySearchTreeTester.py Program
- The Huffman Code
In this chapter we switch from algorithms, the focus of Chapter 7, “Advanced Sorting,” to data structures. Binary trees are one of the fundamental data storage structures used in programming. They provide advantages that the data structures you’ve seen so far cannot. In this chapter you learn why you would want to use trees, how they work, and how to go about creating them.
Why Use Binary Trees?
Why might you want to use a tree? Usually, because it combines the advantages of two other structures: an ordered array and a linked list. You can search a tree quickly, as you can an ordered array, and you can also insert and delete items quickly, as you can with a linked list. Let’s explore these topics a bit before delving into the details of trees.
Slow Insertion in an Ordered Array
Imagine an array in which all the elements are arranged in order—that is, an ordered array—such as you saw in Chapter 2, “Arrays.” As you learned, you can quickly search such an array for a particular value, using a binary search. You check in the center of the array; if the object you’re looking for is greater than what you find there, you narrow your search to the top half of the array; if it’s less, you narrow your search to the bottom half. Applying this process repeatedly finds the object in O(log N) time. You can also quickly traverse an ordered array, visiting each object in sorted order.
On the other hand, if you want to insert a new object into an ordered array, you first need to find where the object will go and then move all the objects with greater keys up one space in the array to make room for it. These multiple moves are time-consuming, requiring, on average, moving half the items (N/2 moves). Deletion involves the same multiple moves and is thus equally slow.
If you’re going to be doing a lot of insertions and deletions, an ordered array is a bad choice.
Slow Searching in a Linked List
As you saw in Chapter 5, “Linked Lists,” you can quickly perform insertions and deletions on a linked list. You can accomplish these operations simply by changing a few references. These two operations require O(1) time (the fastest Big O time).
Unfortunately, finding a specified element in a linked list is not as fast. You must start at the beginning of the list and visit each element until you find the one you’re looking for. Thus, you need to visit an average of N/2 objects, comparing each one’s key with the desired value. This process is slow, requiring O(N) time. (Notice that times considered fast for a sort are slow for the basic data structure operations of insertion, deletion, and search.)
You might think you could speed things up by using an ordered linked list, in which the elements are arranged in order, but this doesn’t help. You still must start at the beginning and visit the elements in order because there’s no way to access a given element without following the chain of references to it. You could abandon the search for an element after finding a gap in the ordered sequence where it should have been, so it would save a little time in identifying missing items. Using an ordered list only helps make traversing the nodes in order quicker and doesn’t help in finding an arbitrary object.
Trees to the Rescue
It would be nice if there were a data structure with the quick insertion and deletion of a linked list, along with the quick searching of an ordered array. Trees provide both of these characteristics and are also one of the most interesting data structures.
What Is a Tree?
A tree consists of nodes connected by edges. Figure 8-1 shows a tree. In such a picture of a tree the nodes are represented as circles, and the edges as lines connecting the circles.
)
FIGURE 8-1 A general (nonbinary) tree
Trees have been studied extensively as abstract mathematical entities, so there’s a large amount of theoretical knowledge about them. A tree is actually an instance of a more general category called a graph. The types and arrangement of edges connecting the nodes distinguish trees and graphs, but you don’t need to worry about the extra issues graphs present. We discuss graphs in Chapter 14, “Graphs,” and Chapter 15, “Weighted Graphs.”
In computer programs, nodes often represent entities such as file folders, files, departments, people, and so on—in other words, the typical records and items stored in any kind of data structure. In an object-oriented programming language, the nodes are objects that represent entities, sometimes in the real world.
The lines (edges) between the nodes represent the way the nodes are related. Roughly speaking, the lines represent convenience: it’s easy (and fast) for a program to get from one node to another if a line connects them. In fact, the only way to get from node to node is to follow a path along the lines. These are essentially the same as the references you saw in linked lists; each node can have some references to other nodes. Algorithms are restricted to going in one direction along edges: from the node with the reference to some other node. Doubly linked nodes are sometimes used to go both directions.
Typically, one node is designated as the root of the tree. Just like the head of a linked list, all the other nodes are reached by following edges from the root. The root node is typically drawn at the top of a diagram, like the one in Figure 8-1. The other nodes are shown below it, and the further down in the diagram, the more edges need to be followed to get to another node. Thus, tree diagrams are small on the top and large on the bottom. This configuration may seem upside-down compared with real trees, at least compared to the parts of real trees above ground; the diagrams are more like tree root systems in a visual sense. This arrangement makes them more like charts used to show family trees with ancestors at the top and descendants below. Generally, programs start an operation at the small part of the tree, the root, and follow the edges out to the broader fringe. It’s (arguably) more natural to think about going from top to bottom, as in reading text, so having the other nodes below the root helps indicate the relative order of the nodes.
There are different kinds of trees, distinguished by the number and type of edges. The tree shown in Figure 8-1 has more than two children per node. (We explain what “children” means in a moment.) In this chapter we discuss a specialized form of tree called a binary tree. Each node in a binary tree has a maximum of two children. More general trees, in which nodes can have more than two children, are called multiway trees. We show examples of multiway trees in Chapter 9, “2-3-4 Trees and External Storage.”