Tree primer: node, root, leaf, height, search tree, balanced tree

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What is the search cost of a multilevel index with t levels? from Lesson 5.3.3
2. What is ⌈log₆₈ 30000⌉? from Lesson 5.3.3
3. What is the fan-out of an index block? from Lesson 5.3.3

1 · The Hook

A multilevel index is a tree drawn sideways: one top block, which points to some blocks, which point to more. B-trees and B+ trees are trees with strict rules. Before learning those rules, we need the words: root, leaf, height, search tree, balanced.

2 · Predict First

A tree has a root with 3 children, and each of those has 3 children, and so on, for 4 levels in total. How many nodes are at the bottom level? How many nodes altogether?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Bottom level: 3³ = 27 nodes. Total: 1 + 3 + 9 + 27 = 40 nodes.

Vocabulary

• A tree is a set of nodes joined by edges, with one special node, the root, and exactly one path from the root to every node.
• If an edge goes from u down to v, u is v's parent and v is u's child; children of one parent are siblings.
• A node with no children is a leaf; others are internal nodes.
• A node and everything below it is a subtree.
• Level: the root is at level 1, its children at level 2, and so on.
• Height (in this course): the number of levels. A tree with only a root has height 1. (Some books count edges and get height 0; Lesson 5.5.1's GATE notes say how to tell.)

m-ary trees

In an m-ary tree each node has at most m children. With h levels:

• max nodes at level i = m^(i−1);
• max nodes in total = 1 + m + … + m^(h−1) = (m^h − 1) / (m − 1).

Search trees

A binary search tree stores keys so that every key in a node's left subtree is smaller and every key in its right subtree is larger. Search follows one path from the root.

An m-way search tree generalises it: a node holds up to m − 1 sorted keys k₁ < k₂ < … and up to m child pointers P₁ … P_m; keys in subtree Pᵢ lie between k_{i−1} and kᵢ. Searching visits one node per level.

Balanced trees

A tree is balanced if all leaves are at the same level (or nearly so). Balanced search trees guarantee that a search visits at most height nodes, which grows like log_m n. An unbalanced tree can degrade into a chain (inserting sorted keys into a plain binary search tree gives height n).

For disk-based indexes: one node = one block, so height = block accesses. A high fan-out m keeps the height tiny.

4 · Visual

A 3-way search tree with 3 levels; every leaf is at level 3, so it is balanced. Keys left of 20 are smaller than 20, keys between 20 and 35 go to the middle child, and so on.

5 · Worked Examples

Example 1 Easy

In a tree with root R, children A and B, and A's children C and D: name the leaves, the internal nodes and the height.

Solution

Leaves: B, C, D. Internal: R, A. Height: 3 levels.

Example 2 Medium

A 4-ary tree has 3 levels and every node has the maximum number of children. How many nodes, and how many leaves?

Solution

Total (4³ − 1)/(4 − 1) = 63/3 = 21; leaves 4² = 16.

Example 3 GATE

Keys 10, 20, 30, 40, 50 are inserted in that order into an empty binary search tree (no balancing). What is its height, and why is that bad for a disk index?

Solution

Each key becomes the right child of the previous: a chain, height 5. A search may visit every node; for a disk index that means one block access per key. Balanced trees prevent this.

8 · Connect the Dots

Lesson 5.3.3 stacked index levels; this lesson gave tree words for them. Next: the B-tree, a balanced m-way search tree with minimum-fill rules, and the word "order", which GATE uses in two different ways.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Counting

A binary tree (m = 2) with 5 levels, completely full. How many nodes?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Leaves

A full 3-ary tree with 4 levels has how many leaves?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Definitions

A balanced tree is one in which:

1. (A) every node has the same number of keys
2. (B) every internal node is full
3. (C) the root has exactly two children
4. (D) all leaves are at the same level

Q4 · MCQ · 1 mark(s) — m-way

In an m-way search tree, a node holds at most:

1. (A) m keys and m + 1 children
2. (B) m/2 keys
3. (C) m − 1 keys and m children
4. (D) m keys and m children

Q5 · NAT · 2 mark(s) — Counting

A 5-ary tree (each node has at most 5 children) has height 3 (levels). What is the maximum number of nodes?

Numerical answer: ________

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

treenodeedgerootparentchildsiblingleafinternal nodesubtreelevelheight (in levels)m-ary treebinary search treem-way search treebalanced tree