- 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
This chapter is from the book
This chapter is from the book
This chapter is from the book
Tree Terminology
Many terms are used to describe particular aspects of trees. You need to know them so that this discussion is comprehensible. Fortunately, most of these terms are related to real-world trees or to family relationships, so they’re not hard to remember. Figure 8-2 shows many of these terms applied to a binary tree.
)
FIGURE 8-2 Tree terms
Root
The node at the top of the tree is called the root. There is only one root in a tree, labeled A in the figure.
Path
Think of someone walking from node to node along the edges that connect them. The resulting sequence of nodes is called a path. For a collection of nodes and edges to be defined as a tree, there must be one (and only one!) path from the root to any other node. Figure 8-3 shows a nontree. You can see that it violates this rule because there are multiple paths from A to nodes E and F. This is an example of a graph that is not a tree.
){kind=link}
FIGURE 8-3 A nontree
Parent
Any node (except the root) has exactly one edge connecting it to a node above it. The node above it is called the parent of the node. The root node must not have a parent.
Child
Any node may have one or more edges connecting it to nodes below. These nodes below a given node are called its children, or sometimes, branches.
Sibling
Any node other than the root node may have sibling nodes. These nodes have a common parent node.
Leaf
A node that has no children is called a leaf node or simply a leaf. There can be only one root in a tree, but there can be many leaves. In contrast, a node that has children is an internal node.
Subtree
Any node (other than the root) may be considered to be the root of a subtree, which also includes its children, and its children’s children, and so on. If you think in terms of families, a node’s subtree contains all its descendants.
Visiting
A node is visited when program control arrives at the node, usually for the purpose of carrying out some operation on the node, such as checking the value of one of its data fields or displaying it. Merely passing over a node on the path from one node to another is not considered to be visiting the node.
Traversing
To traverse a tree means to visit all the nodes in some specified order. For example, you might visit all the nodes in order of ascending key value. There are other ways to traverse a tree, as we’ll describe later.
Levels
The level of a particular node refers to how many generations the node is from the root. If you assume the root is Level 0, then its children are at Level 1, its grandchildren are at Level 2, and so on. This is also sometimes called the depth of a node.
Keys
You’ve seen that one data field in an object is usually designated as a key value, or simply a key. This value is used to search for the item or perform other operations on it. In tree diagrams, when a circle represents a node holding a data item, the key value of the item is typically shown in the circle.
Binary Trees
If every node in a tree has at most two children, the tree is called a binary tree. In this chapter we focus on binary trees because they are the simplest and the most common.
The two children of each node in a binary tree are called the left child and the right child, corresponding to their positions when you draw a picture of a tree, as shown in Figure 8-2. A node in a binary tree doesn’t necessarily have the maximum of two children; it may have only a left child or only a right child, or it can have no children at all (in which case it’s a leaf).
Binary Search Trees
The kind of binary tree we discuss at the beginning of this chapter is technically called a binary search tree. The keys of the nodes have a particular ordering in search trees. Figure 8-4 shows a binary search tree.
){kind=link}
FIGURE 8-4 A binary search tree