15.1. Binary Trees¶
15.1.1. Introduction¶
Tree structures enable efficient access and efficient update to large collections of data. Binary trees, where each node has at most two children, are widely used and relatively easy to implement. But binary trees are useful for many things besides searching. Just a few examples of applications that trees can speed up include prioritizing jobs through the heap data structure, describing mathematical expressions through expression trees, or organizing the information needed to drive data compression algorithms through Huffman trees.
15.1.2. Binary Tree Terminology¶
A binary tree is made up of a finite set of elements called nodes. This set either is empty or consists of a node called the root together with two binary trees, called the left and right subtrees, which are disjoint from each other and from the root. Disjoint here means that they have no nodes in common.
For a given node, the two nodes directly connected to it are called its children. There is an edge from a node to each of its children, and a node is said to be the parent of its children.
If there is a path from node A to node B, then A is an ancestor of B, and B is a descendant of A. For example, if you can follow edges down from node A to eventually reach node B, then A is an ancestor of B, and B is a descendant of A. Thus, all nodes in the tree are descendants of the root of the tree, while the root is the ancestor of all nodes.
The depth of a node in the tree is the length of the path from the root of the tree to that node. The depth of a node \(M\) in the tree is the length of the path from the root of the tree to \(M\). All nodes of depth \(d\) are at level \(d\) in the tree. The height of a tree is the depth of the deepest node in the tree. A leaf node is any node that has no children.
Note
The tree above has the following properties:
Node A is the root of the tree.
Nodes B and C are children of A.
Nodes A, C, and E are ancestors of G.
Nodes D, G, H, and I are leaves.
The height of this tree is 4.
Two specific forms of binary trees are particularly important and have special names:
A full binary tree is a binary tree in which every node has either zero or two children.
A complete binary tree is a binary tree of height \(d\) where all levels except possibly level \(d\) are completely full. The bottom level has its nodes filled in from the left side. In the figure below, tree (a) on the left is a full binary tree, while tree (b) on the right is a complete binary tree.
Note
Notice that a complete binary tree is not necessarily a full binary tree – tree (a) is full but not complete, while tree (b) is complete but not full. We’ll see complete binary trees in the heap data structure later on.
15.1.3. Binary Tree as a Recursive Data Structure¶
A recursive data structure is a data structure that is partially composed of smaller or simpler instances of the same data structure. For example, linked lists and binary trees can be viewed as recursive data structures. A list is a recursive data structure because a list can be defined as either (1) an empty list or (2) a node followed by a list. A binary tree is typically defined as (1) an empty tree or (2) a node pointing to two binary trees, one its left child and the other one its right child.
The recursive relationships used to define a structure provide a natural model for any recursive algorithm on the structure.
