1. Trees
Definition – Tree
A tree is a non-linear structure of nodes where each node has a single predecessor (parent) but can have many successors (children).
flowchart TD A((A)) --> B((B)) A --> C((C)) B --> D((D)) B --> E((E)) C --> F((F)) C --> G((G)) C --> H((H)) H --> I((I))
Terminology
| Term | Definition | In the example |
|---|---|---|
| Root | node with no parent | A |
| Parent / child | direct predecessor / successor | B is parent of D, E; I is child of H |
| Leaf | node with no children | D, E, F, G, I |
| Internal node | node with children | A, B, C, H |
| Ancestor / descendant | is an ancestor of if there’s a path from to | A is an ancestor of I |
| Path | sequence of nodes passed through from to | A–B–D |
| Path length | number of arcs = number of nodes − 1 | A→D has length 2 |
| Depth of | length of the path root → | depth(F) = 2 |
| Height of | length of the longest path → leaf | height(C) = 2 |
| Height of tree | height of its root | 3 |
| Level | all nodes of depth | level 1 = {B, C} |
| Size | total number of nodes | 9 |
| Degree of a node | number of its children | deg(C) = 3 |
| Degree of a tree | maximum node degree | 3 |
Recursive definitions:
Worked example – heights (bottom-up)
- (leaf) →
- →
- →
- = height of the tree.
2. Binary Trees
Definition – Binary tree
A tree of degree 2: each node has at most a left child and a right child.
Properties
- Maximum number of nodes at level : .
- Maximum size of a binary tree of height : .
Worked example: height → at most nodes ().
⚠️ The slide writes "" but the formula also holds for (one node: ).
Full vs complete binary trees
| Type | Definition |
|---|---|
| Full | every node is either a leaf or has exactly two non-empty children |
| Complete | if the height is , all levels except possibly level are completely full, and the bottom level has its nodes packed to the left |
flowchart TD subgraph Full ["(a) Full"] a1((·)) --> a2((·)) a1 --> a3((·)) a2 --> a4((·)) a2 --> a5((·)) a5 --> a6((·)) a5 --> a7((·)) end subgraph Complete ["(b) Complete"] b1((·)) --> b2((·)) b1 --> b3((·)) b2 --> b4((·)) b2 --> b5((·)) b3 --> b6((·)) b4 --> b7((·)) end
⚠️ Full ≠ complete: a full tree can be very unbalanced, and a complete tree can have a node with one child (the last internal node).
Theorem – Full binary tree
In a non-empty full binary tree, the number of leaves is one more than the number of internal nodes: internal leaves .
Worked example: tree (a) above has internal nodes {root, left child, its right child} = 3 and leaves = 4 ✓.
3. Implementation by Pointers
Each node keeps a pointer to its left child and one to its right child; a missing child → NULL.
template <class Element>
class BTree {
class BNode {
public:
BNode *left; Element data; BNode *right;
BNode(const Element &d) { left = 0; data = d; right = 0; }
bool isLeaf() { return left == NULL && right == NULL; }
};
BNode *root;
public:
BTree() { root = NULL; }
bool isEmpty() const;
void insert(const Element &d);
void remove(const Element &d);
void print() const;
};4. Space Overhead
Let = size of a pointer, = size of the data. Each node uses , so a tree of nodes uses , of which is structure (pointers).
If leaves (≈ half the nodes in a full tree) store no pointers:
5. Binary Tree Traversals
Definition – Traversals
| Traversal | Order |
|---|---|
| Inorder | left subtree (inorder) → root → right subtree (inorder) |
| Preorder | root → left subtree (preorder) → right subtree (preorder) |
| Postorder | left subtree (postorder) → right subtree (postorder) → root |
void Inorder(BNode *r) { if (r) { Inorder(r->left); Visit(r); Inorder(r->right); } }
void Preorder(BNode *r) { if (r) { Visit(r); Preorder(r->left); Preorder(r->right); } }
void Postorder(BNode *r) { if (r) { Postorder(r->left); Postorder(r->right); Visit(r); } }Called from the root; recursion visits every subtree.
Worked example
flowchart TD R((R)) --> A((A)) R --> D((D)) A --> B((B)) A --> C((C)) D --> X[ ] D --> E((E)) style X fill:none,stroke:none
| Traversal | Result |
|---|---|
| Inorder | B – A – C – R – D – E |
| Preorder | R – A – B – C – D – E |
| Postorder | B – C – A – E – D – R |
6. Implementation by Array
Since the degree is 2, cells can be reserved in advance in a sequential array: node 0 at index 0, its children at 1 and 2, etc. (root at 0 → children of at and ).
Worked example
flowchart TD O((O)) --> M((M)) O --> T((T)) M --> C((C)) M --> E((E)) T --> P((P)) T --> U((U))
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| O | M | T | C | E | P | U |
⚠️ If the tree is not complete, the array has empty cells (wasted space). This is why arrays suit complete trees, e.g. heaps.
7. Priority Queues
Definition – Priority queue
Stores objects and, on request, releases the object with the greatest value (highest priority).
- Example: scheduling jobs in a multitasking OS; a job’s priority may change → reordering.
- Implementation: a heap.
8. Heaps
Definition – Heap
A complete binary tree with the heap property:
- Min-heap: every value is less than its children’s values;
- Max-heap: every value is greater than its children’s values.
Values are only partially ordered (no order between siblings). Usually stored as an array.
Array representation (root at index 1)
For a node at position in a heap of size :
| Element | Position |
|---|---|
| Root | 1 |
| Left child | |
| Right child | |
| Father | |
| Is a leaf | |
| Has 2 children | |
| Has 1 child | |
| Last internal node |
Worked example – heap T = [_, 13, 21, 16, 24, 31, 19, 68, 65, 26, 32] ()
flowchart TD n13((13)) --> n21((21)) n13 --> n16((16)) n21 --> n24((24)) n21 --> n31((31)) n16 --> n19((19)) n16 --> n68((68)) n24 --> n65((65)) n24 --> n26((26)) n31 --> n32((32))
- Node 24 is at : father , children , .
- Node 31 at : → exactly one child ().
- Last internal node: ; positions 6–10 are leaves.
template <class Elem> class minHeap {
Elem *tab; int max; int n;
void putHeap();
public:
int Parent(int pos) const { return (pos > 1 && pos <= n) ? pos / 2 : -1; }
int leftChild(int pos) const { return 2 * pos; }
int rightChild(int pos) const { return 2 * pos + 1; }
bool isLeaf(int pos) const { return pos > n / 2 && pos <= n; }
void insert(const Elem val);
Elem deleteMin();
};9. Insertion in a Heap (sift-up)
Algorithm
- Increment and put the new value at (end of the array).
- While the value is smaller than its father (min-heap), swap with the father and move up.
template <class Elem>
void minHeap<Elem>::insert(const Elem val) {
if (n < max) {
int current = ++n;
tab[current] = val;
while (current > 1 && tab[current] < tab[Parent(current)]) {
swap(tab[current], tab[Parent(current)]);
current = Parent(current);
}
}
}Worked example – insert 14
| Step | Position of 14 | Father | Action | Array (1..11) |
|---|---|---|---|---|
| 1 | 11 | 14 < 31 → swap | 13 21 16 24 14 19 68 65 26 32 31 | |
| 2 | 5 | 14 < 21 → swap | 13 14 16 24 21 19 68 65 26 32 31 | |
| 3 | 2 | 14 > 13 → stop | 13 14 16 24 21 19 68 65 26 32 31 |
flowchart TD n13((13)) --> n14((14)) n13 --> n16((16)) n14 --> n24((24)) n14 --> n21((21)) n16 --> n19((19)) n16 --> n68((68)) n24 --> n65((65)) n24 --> n26((26)) n21 --> n32((32)) n21 --> n31((31)) style n14 fill:#fde68a,stroke:#b45309,color:#2a1f33
10. Deletion in a Heap (deleteMin, sift-down)
Algorithm
- Remove the root (the minimum).
- Move the rightmost node of the last level (i.e. ) to the root; decreases.
- Compare it with its children; if it is greater than one of them, swap with the smaller child.
- Repeat until the heap property holds.
template <class Elem>
Elem minHeap<Elem>::deleteMin() {
if (n == 0) return NULL; // empty heap
Elem temp = tab[1];
tab[1] = tab[n--]; // last element to the root
if (n > 1) putHeap();
return temp;
}
template <class Elem>
void minHeap<Elem>::putHeap() {
int pos = 1;
while (!isLeaf(pos)) {
int l = leftChild(pos), r = rightChild(pos);
if (r <= n && tab[r] < tab[l]) l = r; // l = smaller child
if (tab[pos] <= tab[l]) return;
swap(tab[pos], tab[l]);
pos = l;
}
}Worked example – delete the root 2 from [2, 3, 4, 7, 5, 6]
| Step | Array | Action |
|---|---|---|
| 0 | 2 3 4 7 5 6 | remove 2 |
| 1 | 6 3 4 7 5 | last element 6 → root |
| 2 | 3 6 4 7 5 | children 3, 4 → smaller is 3 → swap |
| 3 | 3 5 4 7 6 | children 7, 5 → smaller is 5 → swap; 6 is now a leaf → stop |
flowchart TD a3((3)) --> a5((5)) a3 --> a4((4)) a5 --> a7((7)) a5 --> a6((6))
⚠️ Always swap with the smaller child (min-heap) — swapping with the larger one breaks the heap property. Also,
return NULLonly compiles for pointer/numericElem; and in the slideposis used without being declared (int pos = 1;). “minTas” in the slides is the French name forminHeap.
11. Complexity of Heap Operations
A complete binary tree of nodes has height , and insertion/deletion never do more swaps than the height.
| Operation | Complexity |
|---|---|
| Insert | |
| Delete min (max) | |
| Find min in a min-heap (max in a max-heap) |