Trees and heaps
導入済み
語彙
| English | 意味 |
|---|---|
| binary search tree/ˈbaɪnəri sɜːtʃ triː/ | A binary tree ordered so keys in the left subtree precede the node and keys in the right follow it. |
| heap/hiːp/ | A tree-based structure satisfying an ordering rule between each parent and its children. |
| min-heap | A heap in which every parent is no greater than its children, placing a minimum at the root. |
English
Order invariant, complete shape
- A binary search tree keeps left subtree below node below right subtree: inserting $50, 30, 70, 20, 40, 60, 80$ builds a perfect tree of height $2$, and the inorder walk reads $20, 30, 40, 50, 60, 70, 80$ — sorted by construction.
- A heap is a complete tree stored in an array: children of index $i$ sit at $2i+1$ and $2i+2$. A min-heap keeps every parent at or below its children, so the minimum lives at index $0$.
{exercise:uni-cs0504-shapes}
実践
In a heap stored as an array, the children of index i sit at —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
The complete shape fixes the mapping: left child 2i+1, right child 2i+2.
English
Height is the cost
- A perfect tree of height $h$ holds $2^{h+1} - 1$ nodes: $7$ at $h = 2$, $15$ at $h = 3$, $31$ at $h = 4$ — so balanced $n$ needs height $\lfloor \log_2 n \rfloor$, and every root-to-leaf walk pays it.
- Skew breaks the deal: inserting sorted keys $1, 2, 3, 4$ makes a chain of height $3 = n - 1$, $O(n)$ search — the reason AVL and red-black trees rotate to stay logarithmic.
{exercise:uni-cs0504-height}
実践
A perfect tree of height 3 holds —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
2 to the h+1 minus 1: 16 minus 1 is 15.
English
Walks and sifts
- BST search $40$: compare $50$ (go left), $30$ (go right), $40$ — found in $3$ comparisons on $7$ nodes. Insert $35$ hangs it left of $40$; inorder still reads sorted.
- Min-heap by inserting $5, 3, 8, 1$: $3$ sifts up over $5$; $1$ sifts up over $5$ then $3$; the array reads $[1, 3, 8, 5]$ — parent at or below children everywhere.
heapq.heapifybuilds a whole array in $O(n)$ by sifting down from the middle.
{exercise:uni-cs0504-sift}
実践
Inserting 5, 3, 8, 1 into an empty min-heap leaves the array —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
3 sifts over 5; 1 sifts over 5 then 3 — parents stay at or below children.