Binary Tree
- Tags
- math
A Tree where every node has at most 2 sub-nodes.
Properties of a Binary Search Tree
Table 1:
Operations on the binary tree data structure.
| Method | Description |
|---|---|
x.key | The value of the node x. |
x.left | A pointer to the root of the left sub-tree of x. |
x.right | A pointer to the root of the right sub-tree of x. |
The [see page 14, height] of a binary tree is always at most \( \log n \). A binary tree of height \( h \) has [see page 12, no more] than \( 2^h \) leaves.
Proving Properties on Binary Trees
We can [see page 7, prove] statements about binary trees recursively (inductively) by:
- Base case: Showing the statement holds for the smallest tree (such as an empty tree).
- Induction step: Any larger tree has a root and 2 (possibly empty) sub-trees. Assuming the statement holds for both sub-trees, show it then holds for the whole tree.
See an [see page 8, example] here.