Tree Terminology
In previous classes you've probably discussed tree structures.
Let's take this opportunity to review some key terminology so we're all on the same page.
Here's a picture of a tree:
Here are some tree terms you may have encountered. Brainstorm all the definitions you can remember!
|
Node Edge Parent/Child |
Root Leaf Subtree |
Height Binary Tree Balanced Tree |
Our definitions:
- Node
- An element in a tree.
- Edge
- A connection between two nodes. Let's say that \( \mathrm{edge}( A , B ) \) goes from node \( A \) to node \( B \).
- Parent/Child
- In an \( \mathrm{edge}( A , B ) \), \( A \) is the parent (where the edge originates) and \( B \) is the child (where the edge leads).
- Root
- The "top-most" node in a tree; the node with no parent.
- Leaf
- A node with no children.
- Subtree
- A node in a tree and the tree rooted at that node (the node's children and their children etc.).
- Height
- Length of the longest path from the root to a leaf; thus,
- A tree with one node has height 0
- an empty tree has height –1
- Binary Tree
- A tree in which every node has at most two children, a left child and a right child.
- The children are ordered. For a tree with only one child, it matters whether the child is on the left or the right.
- It can be defined recursively as either being an empty tree, or a node with left and right subtrees as children (either of which can be empty).
- Balanced Binary Tree
- A tree where each node is balanced, which means that the heights of its left and right subtrees are similar.
Hay! That seems odd!! Why is the height of an empty tree –1?
-
Well, the height of a tree with a single node is zero (because maximum path length to a leaf is zero, it's already a leaf).
-
You can think of –1 as meaning “Oh no! Go back, go back! Get back to a leaf, you've got too far and you're nowhere now!”.
-
One of the big reasons for this strangeness is that mathematicians usually stop at a single-node tree, with a height of zero—they don't consider empty trees at all!
-
Also, graph theorists often mean something a bit different by the term “tree”. We've put a bit about the mathematical side of things in a deeper dive, below.
Deeper Dive: Graph Theory & Trees
Mathematicians first started thinking about graph theory topics in 1736 with a paper by Leonhard Euler on the Seven Bridges of Königsberg. The specific concept of trees came in a 1857 paper by Arthur Cayley, On the Theory of the Analytical Forms Called Trees. Back in those days, no one saw any use for the concept of an empty tree, and most purely mathematical treatments of trees continue that perspective today.
In fact, although the trees we use as data structures correspond well with Cayley's concept of a tree, today's graph theorists tend to use the term “tree” differently (to mean a “connected acyclic undirected graph”), and use the term arborescence to mean what we think of a tree; namely, a rooted directed graph in which there is a unique path from the root to every other node.
(When logged in, completion status appears here.)