Skip to content
CampusPrep
CS-303 · Data Structure/Quick Revision Short Notes

Data Structure (CS-303) - Unit 3 Short Notes

How unit 3 is examined

Terminology, BST, AVL, heap, B-tree and red-black trees; BST work, AVL rotations and B-tree construction carry the marks.

Tree: Definitions - Height, depth, order, degree etc.

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A tree is a non-linear hierarchical data structure of nodes joined by edges, with one special node called the root and every other node reachable from it by exactly one path.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 448 262" width="448" height="262" role="img" aria-label="A root, B and C are children of A (siblings), D E F G H I are leaves, B C E are internal nodes; A is level 0, B C level 1"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="256" y1="39" x2="80" y2="103"/><line class="e" x1="256" y1="39" x2="344" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="168" y2="167"/><line class="e" x1="168" y1="167" x2="124" y2="231"/><line class="e" x1="168" y1="167" x2="212" y2="231"/><line class="e" x1="344" y1="103" x2="300" y2="167"/><line class="e" x1="344" y1="103" x2="388" y2="167"/><circle class="n" cx="256" cy="39" r="17"/><text class="t" x="256" y="39" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="168" cy="167" r="17"/><text class="t" x="168" y="167" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">H</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">I</text><circle class="n" cx="344" cy="103" r="17"/><text class="t" x="344" y="103" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="388" cy="167" r="17"/><text class="t" x="388" y="167" dy=".35em" text-anchor="middle">G</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">A root, B and C are children of A (siblings), D E F G H I are leaves, B C E are internal nodes; A is level 0, B C level 1</figcaption></figure>

Key points.

  1. The root has no parent; a leaf (terminal node) has no children; every other node is internal (non-terminal).
  2. B is the parent of D and E, and D and E are siblings because they share a parent.
  3. The degree of a node is its number of children; the degree (order) of the tree is the maximum node degree, 2 for a binary tree.
  4. The depth (level) of a node is the number of edges from the root to it, and the height of a node is the longest path down to a leaf; the tree height is the root's height.
  5. A tree with n nodes has n - 1 edges.
  6. A full binary tree has every node with 0 or 2 children; a complete binary tree has every level full except possibly the last, filled from the left.
  7. An expression tree has operands as leaves and operators as internal nodes; a + b * c has root + with children a and *(b, c).

Answer frame. Open with the definition; draw the labelled tree; define each asked term in a sentence using a node of the figure; close with n nodes = n - 1 edges.

Pitfall: Height and depth are different: depth is measured from the root down, height from the node down to its deepest leaf. Asked: [7 marks] (Dec 2020, Nov 2022, Dec 2025) Height, complete binary tree, expression tree, sibling, full binary tree; tree terminologies with diagrams Asked: [7 marks] (Dec 2025) Define height, depth, degree of a node and forest

Binary Search Tree - Operations, Traversal, Search

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A binary search tree (BST) is a binary tree in which, for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger than the node's key.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-02" viewBox="0 0 360 198" width="360" height="198" role="img" aria-label="BST. Inorder 20 30 40 50 60 70 80; preorder 50 30 20 40 70 60 80; postorder 20 40 30 60 80 70 50"><style>#dsfig-u3-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-02 .t{fill:#16181D;font-weight:500}#dsfig-u3-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-02 .dot{fill:#16181D}#dsfig-u3-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-02 .ah{fill:#454C5A}#dsfig-u3-02 .ah.hi{fill:#2340B8}#dsfig-u3-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-02 .e{stroke:#B1B7C3}html.dark #dsfig-u3-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-02 .t{fill:#E6E8ED}html.dark #dsfig-u3-02 .t.inv{fill:#0F1115}html.dark #dsfig-u3-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-02 .dot{fill:#E6E8ED}html.dark #dsfig-u3-02 .ann{fill:#8FA3FF}html.dark #dsfig-u3-02 .lbl{fill:#858D9C}html.dark #dsfig-u3-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-02 .ah{fill:#B1B7C3}html.dark #dsfig-u3-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="168" y1="39" x2="80" y2="103"/><line class="e" x1="168" y1="39" x2="256" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="124" y2="167"/><line class="e" x1="256" y1="103" x2="212" y2="167"/><line class="e" x1="256" y1="103" x2="300" y2="167"/><circle class="n" cx="168" cy="39" r="17"/><text class="t" x="168" y="39" dy=".35em" text-anchor="middle">50</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">20</text><circle class="n" cx="124" cy="167" r="17"/><text class="t" x="124" y="167" dy=".35em" text-anchor="middle">40</text><circle class="n" cx="256" cy="103" r="17"/><text class="t" x="256" y="103" dy=".35em" text-anchor="middle">70</text><circle class="n" cx="212" cy="167" r="17"/><text class="t" x="212" y="167" dy=".35em" text-anchor="middle">60</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">80</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">BST. Inorder 20 30 40 50 60 70 80; preorder 50 30 20 40 70 60 80; postorder 20 40 30 60 80 70 50</figcaption></figure>

Key points.

  1. The BST property holds recursively for every subtree, and duplicates are normally not stored.
  2. Search goes left or right by comparing with each node, so it takes O(h): O(log n) if balanced, O(n) if skewed.
  3. Types: skewed (worst case), complete, self-balancing (AVL, red-black) and threaded.
  4. Insertion searches for the key and attaches a new leaf where the search ends.
  5. Deletion has three cases: a leaf is removed; a node with one child is replaced by that child; a node with two children takes its inorder successor (smallest key of the right subtree), which is then deleted.
  6. Preorder is Root-Left-Right, inorder Left-Root-Right, postorder Left-Right-Root; inorder of a BST is ascending.
  7. A threaded binary tree replaces NULL pointers by threads to the inorder predecessor or successor, so traversal needs no stack or recursion; an unthreaded tree needs recursion or a stack.
  8. Construction: the last postorder (or first preorder) element is the root; find it in inorder, the left part is the left subtree and the right part the right subtree; repeat. Inorder is always needed.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-03" viewBox="0 0 360 262" width="360" height="262" role="img" aria-label="Q17 after inserting 45 26 10 60 70 30 40"><style>#dsfig-u3-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-03 .t{fill:#16181D;font-weight:500}#dsfig-u3-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-03 .dot{fill:#16181D}#dsfig-u3-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-03 .ah{fill:#454C5A}#dsfig-u3-03 .ah.hi{fill:#2340B8}#dsfig-u3-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-03 .e{stroke:#B1B7C3}html.dark #dsfig-u3-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-03 .t{fill:#E6E8ED}html.dark #dsfig-u3-03 .t.inv{fill:#0F1115}html.dark #dsfig-u3-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-03 .dot{fill:#E6E8ED}html.dark #dsfig-u3-03 .ann{fill:#8FA3FF}html.dark #dsfig-u3-03 .lbl{fill:#858D9C}html.dark #dsfig-u3-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-03 .ah{fill:#B1B7C3}html.dark #dsfig-u3-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="212" y1="39" x2="80" y2="103"/><line class="e" x1="212" y1="39" x2="256" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="124" y2="167"/><line class="e" x1="124" y1="167" x2="168" y2="231"/><line class="e" x1="256" y1="103" x2="300" y2="167"/><circle class="n" cx="212" cy="39" r="17"/><text class="t" x="212" y="39" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">26</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="124" cy="167" r="17"/><text class="t" x="124" y="167" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="168" cy="231" r="17"/><text class="t" x="168" y="231" dy=".35em" text-anchor="middle">40</text><circle class="n" cx="256" cy="103" r="17"/><text class="t" x="256" y="103" dy=".35em" text-anchor="middle">60</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">70</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Q17 after inserting 45 26 10 60 70 30 40</figcaption></figure> Delete 10 (leaf). Delete 60 (one child): 70 takes its place. Delete 45 (two children): successor 70 becomes the root, leaving 70(26(,30(,40)),).

Example (inorder DGBAHEICF, postorder GDBHIEFCA). Root A; left inorder DGB with postorder GDB gives root B, then D, then G right of D. Right inorder HEICF with postorder HIEFC gives root C, left E with H, I, and F on the right. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-04" viewBox="0 0 448 262" width="448" height="262" role="img" aria-label="Tree for Dec 2023 and Dec 2020. Also inorder EACKFHDBG with preorder FAEKCDHGB gives F(A(E,K(C,)),D(H,G(B,)))"><style>#dsfig-u3-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-04 .t{fill:#16181D;font-weight:500}#dsfig-u3-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-04 .dot{fill:#16181D}#dsfig-u3-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-04 .ah{fill:#454C5A}#dsfig-u3-04 .ah.hi{fill:#2340B8}#dsfig-u3-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-04 .e{stroke:#B1B7C3}html.dark #dsfig-u3-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-04 .t{fill:#E6E8ED}html.dark #dsfig-u3-04 .t.inv{fill:#0F1115}html.dark #dsfig-u3-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-04 .dot{fill:#E6E8ED}html.dark #dsfig-u3-04 .ann{fill:#8FA3FF}html.dark #dsfig-u3-04 .lbl{fill:#858D9C}html.dark #dsfig-u3-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-04 .ah{fill:#B1B7C3}html.dark #dsfig-u3-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="168" y1="39" x2="124" y2="103"/><line class="e" x1="168" y1="39" x2="344" y2="103"/><line class="e" x1="124" y1="103" x2="36" y2="167"/><line class="e" x1="36" y1="167" x2="80" y2="231"/><line class="e" x1="344" y1="103" x2="256" y2="167"/><line class="e" x1="344" y1="103" x2="388" y2="167"/><line class="e" x1="256" y1="167" x2="212" y2="231"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><circle class="n" cx="168" cy="39" r="17"/><text class="t" x="168" y="39" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="124" cy="103" r="17"/><text class="t" x="124" y="103" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="80" cy="231" r="17"/><text class="t" x="80" y="231" dy=".35em" text-anchor="middle">G</text><circle class="n" cx="344" cy="103" r="17"/><text class="t" x="344" y="103" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="256" cy="167" r="17"/><text class="t" x="256" y="167" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">H</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">I</text><circle class="n" cx="388" cy="167" r="17"/><text class="t" x="388" y="167" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Tree for Dec 2023 and Dec 2020. Also inorder EACKFHDBG with preorder FAEKCDHGB gives F(A(E,K(C,)),D(H,G(B,)))</figcaption></figure>

Expression tree for (a + b * c) + ((d * e + f) * g): root +, left +(a, *(b,c)), right (+((d,e),f), g). Preorder: + + a * b c * + * d e f g. Inorder: a + b * c + d * e + f * g (with brackets). Postorder: a b c * + d e * f + g * +.

void inorder(struct node *t) {
  if (t == NULL) return;
  inorder(t->left); printf("%d ", t->key); inorder(t->right);
}  /* preorder: print first; postorder: print last */

struct node { int key; struct node *left, *right; };
struct node *insert(struct node *t, int k) {
  if (t == NULL) { t = malloc(sizeof *t); t->key = k; t->left = t->right = NULL; }
  else if (k < t->key) t->left = insert(t->left, k);
  else if (k > t->key) t->right = insert(t->right, k);
  return t;
}

struct node *del(struct node *t, int k) {
  if (t == NULL) return NULL;
  if (k < t->key) t->left = del(t->left, k);
  else if (k > t->key) t->right = del(t->right, k);
  else if (t->left == NULL)  { struct node *r = t->right; free(t); return r; }
  else if (t->right == NULL) { struct node *l = t->left; free(t); return l; }
  else { struct node *s = t->right; while (s->left) s = s->left;
         t->key = s->key; t->right = del(t->right, s->key); }
  return t;
}  /* main: root = insert(root, 45); root = del(root, 45); inorder(root); */

Answer frame. Traversal: define BST, draw the sample tree, give the three orders with their rules, note inorder is sorted. Program: node struct, NULL base case, the function, a short main. Construction: state the logic, split inorder step by step, verify by re-traversing.

Asked: [7 marks] (Jun 2023, Jun 2024, Dec 2025) How a binary search tree is traversed? Explain with a suitable example Asked: [7 marks] (Dec 2025) Define a BST; explain in-order, pre-order, post-order algorithms with an example Asked: [7 marks] (Dec 2020, Dec 2023) Construct the tree from inorder DGBAHEICF and postorder GDBHIEFCA; inorder E A C K F H D B G with preorder F A E K C D H G B, state the logic Asked: [7 marks] (Jun 2020, Jun 2024) Recursive preorder, inorder and postorder functions Asked: [7 marks] (Nov 2022, Jun 2024) C program to insert and delete elements in a BST Asked: [7 marks] (Dec 2020) Types of BST; insertion and deletion with example Asked: [7 marks] (Jun 2020) What is a BST, its properties, an example Asked: [7 marks] (Nov 2019) Traversal of a binary tree and threaded binary tree Asked: [7 marks] (Dec 2024) Expression tree for (a + b * c) + ((d * e + f) * g) with all three traversals Asked: [7 marks] (Dec 2024) BST for 45, 26, 10, 60, 70, 30, 40; delete 10, 60, 45 showing each tree

AVL Tree

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. ==An AVL tree is a self-balancing BST in which the balance factor BF = height(left) - height(right) of every node is -1, 0 or +1.==

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-05" viewBox="0 0 1540 198" width="1540" height="198" role="img" aria-label="Four imbalances; each rotation gives the balanced tree at the bottom"><style>#dsfig-u3-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-05 .t{fill:#16181D;font-weight:500}#dsfig-u3-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-05 .dot{fill:#16181D}#dsfig-u3-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-05 .ah{fill:#454C5A}#dsfig-u3-05 .ah.hi{fill:#2340B8}#dsfig-u3-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-05 .e{stroke:#B1B7C3}html.dark #dsfig-u3-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-05 .t{fill:#E6E8ED}html.dark #dsfig-u3-05 .t.inv{fill:#0F1115}html.dark #dsfig-u3-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-05 .dot{fill:#E6E8ED}html.dark #dsfig-u3-05 .ann{fill:#8FA3FF}html.dark #dsfig-u3-05 .lbl{fill:#858D9C}html.dark #dsfig-u3-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-05 .ah{fill:#B1B7C3}html.dark #dsfig-u3-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="206.5" y1="39" x2="129.5" y2="103"/><line class="e" x1="129.5" y1="103" x2="52.5" y2="167"/><rect class="n" x="173" y="24" width="67" height="30" rx="8"/><text class="t" x="206.5" y="39" dy=".35em" text-anchor="middle">LL: 30</text><circle class="n" cx="129.5" cy="103" r="17"/><text class="t" x="129.5" y="103" dy=".35em" text-anchor="middle">20</text><circle class="n" cx="52.5" cy="167" r="17"/><text class="t" x="52.5" y="167" dy=".35em" text-anchor="middle">10</text><line class="e" x1="331.5" y1="39" x2="408.5" y2="103"/><line class="e" x1="408.5" y1="103" x2="485.5" y2="167"/><rect class="n" x="298" y="24" width="67" height="30" rx="8"/><text class="t" x="331.5" y="39" dy=".35em" text-anchor="middle">RR: 10</text><circle class="n" cx="408.5" cy="103" r="17"/><text class="t" x="408.5" y="103" dy=".35em" text-anchor="middle">20</text><circle class="n" cx="485.5" cy="167" r="17"/><text class="t" x="485.5" y="167" dy=".35em" text-anchor="middle">30</text><line class="e" x1="764.5" y1="39" x2="610.5" y2="103"/><line class="e" x1="610.5" y1="103" x2="687.5" y2="167"/><rect class="n" x="731" y="24" width="67" height="30" rx="8"/><text class="t" x="764.5" y="39" dy=".35em" text-anchor="middle">LR: 30</text><circle class="n" cx="610.5" cy="103" r="17"/><text class="t" x="610.5" y="103" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="687.5" cy="167" r="17"/><text class="t" x="687.5" y="167" dy=".35em" text-anchor="middle">20</text><line class="e" x1="889.5" y1="39" x2="1043.5" y2="103"/><line class="e" x1="1043.5" y1="103" x2="966.5" y2="167"/><rect class="n" x="856" y="24" width="67" height="30" rx="8"/><text class="t" x="889.5" y="39" dy=".35em" text-anchor="middle">RL: 10</text><circle class="n" cx="1043.5" cy="103" r="17"/><text class="t" x="1043.5" y="103" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="966.5" cy="167" r="17"/><text class="t" x="966.5" y="167" dy=".35em" text-anchor="middle">20</text><line class="e" x1="1316" y1="39" x2="1192" y2="103"/><line class="e" x1="1316" y1="39" x2="1440" y2="103"/><rect class="n" x="1259" y="24" width="114" height="30" rx="8"/><text class="t" x="1316" y="39" dy=".35em" text-anchor="middle">Balanced: 20</text><circle class="n" cx="1192" cy="103" r="17"/><text class="t" x="1192" y="103" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="1440" cy="103" r="17"/><text class="t" x="1440" y="103" dy=".35em" text-anchor="middle">30</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Four imbalances; each rotation gives the balanced tree at the bottom</figcaption></figure>

Key points.

  1. After an insertion, walk up from the new node to the lowest node whose BF becomes +2 or -2; only that node is rotated.
  2. LL case (new key in left of left child): a single right rotation makes the left child the subtree root.
  3. RR case (new key in right of right child): a single left rotation makes the right child the subtree root.
  4. LR case (new key in right of left child): rotate the left child left, then the node right; RL is the mirror.
  5. Right rotation at y: x = y->left; y->left = x->right; x->right = y; update heights; return x. Left rotation swaps left and right. Each rotation is O(1).
  6. Insertion needs at most one rotation, deletion possibly several; all operations are O(log n) as height is at most 1.44 log n.

Insertions (rotation applied, tree after in brackets).

Keys Rotations in order Final tree
68 5 38 24 18 116 92 82 48 38: LR at 68; 18: RL at 5; 92: RL at 68 38(18(5,24),92(68(48,82),116))
16 23 9 163 64 29 73 83 90 96 64: RL at 23; 29: RL at 16; 83: LR at 163; 90: RR at 64; 96: LR at 163 23(16(9,),83(64(29,73),96(90,163)))
64 1 44 26 13 110 98 85 44: LR at 64; 13: RL at 1; 98: RL at 64 44(13(1,26),98(64(,85),110))
50 25 10 5 7 3 30 20 10: LL at 50; 7: LR at 10; 3: LL at 25 7(5(3,),25(10(,20),50(30,)))
12 30 36 18 25 9 4 2 17 14 20 47 36: RR at 12; 25: RR at 12; 9: LL at 30; 4: LL at 12; 14: RL at 12 18(9(4(2,),14(12,17)),30(25(20,),36(,47)))

Deletion of 18, 2, 30 (Jun 2023). 18 is replaced by inorder successor 20; delete 2 (leaf) leaves 9 with BF -1; 30 is replaced by successor 36. No rotation is needed. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-06" viewBox="0 0 448 262" width="448" height="262" role="img" aria-label="Final AVL tree after deleting 18, 2, 30"><style>#dsfig-u3-06 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-06 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-06 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-06 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-06 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-06 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-06 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-06 .t{fill:#16181D;font-weight:500}#dsfig-u3-06 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-06 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-06 .dot{fill:#16181D}#dsfig-u3-06 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-06 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-06 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-06 .ah{fill:#454C5A}#dsfig-u3-06 .ah.hi{fill:#2340B8}#dsfig-u3-06 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-06 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-06 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-06 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-06 .e{stroke:#B1B7C3}html.dark #dsfig-u3-06 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-06 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-06 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-06 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-06 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-06 .t{fill:#E6E8ED}html.dark #dsfig-u3-06 .t.inv{fill:#0F1115}html.dark #dsfig-u3-06 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-06 .dot{fill:#E6E8ED}html.dark #dsfig-u3-06 .ann{fill:#8FA3FF}html.dark #dsfig-u3-06 .lbl{fill:#858D9C}html.dark #dsfig-u3-06 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-06 .ah{fill:#B1B7C3}html.dark #dsfig-u3-06 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-06 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-06 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-06 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah15" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh15" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="256" y1="39" x2="80" y2="103"/><line class="e" x1="256" y1="39" x2="344" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="168" y2="167"/><line class="e" x1="168" y1="167" x2="124" y2="231"/><line class="e" x1="168" y1="167" x2="212" y2="231"/><line class="e" x1="344" y1="103" x2="300" y2="167"/><line class="e" x1="344" y1="103" x2="388" y2="167"/><circle class="n" cx="256" cy="39" r="17"/><text class="t" x="256" y="39" dy=".35em" text-anchor="middle">20</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">9</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="168" cy="167" r="17"/><text class="t" x="168" y="167" dy=".35em" text-anchor="middle">14</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">12</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">17</text><circle class="n" cx="344" cy="103" r="17"/><text class="t" x="344" y="103" dy=".35em" text-anchor="middle">36</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">25</text><circle class="n" cx="388" cy="167" r="17"/><text class="t" x="388" y="167" dy=".35em" text-anchor="middle">47</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Final AVL tree after deleting 18, 2, 30</figcaption></figure>

Answer frame. Define AVL and BF; draw the four rotation figures; explain LL, RR then LR, RL with the algorithm; for numericals show each insertion, the unbalanced node and rotation name; close with O(log n) height and O(1) rotation.

Pitfall: Rotate at the lowest unbalanced node, and for LR/RL do the two rotations in the right order, otherwise the result is not a valid BST. Asked: [14 marks] (Jun 2023) Insert 12, 30, 36, 18, 25, 9, 4, 2, 17, 14, 20, 47 in an AVL tree and delete 18, 2, 30 Asked: [7 marks] (Nov 2018, Dec 2023) AVL tree by inserting 68, 5, 38, 24, 18, 116, 92, 82, 48; and 16, 23, 9, 163, 64, 29, 73, 83, 90, 96 Asked: [7 marks] (May 2019, Nov 2019) Explain AVL trees; insert 64, 1, 44, 26, 13, 110, 98, 85; and 50, 25, 10, 5, 7, 3, 30, 20 Asked: [7 marks] (Dec 2024, Dec 2025) Algorithms for single and double rotation on an AVL tree Asked: [7 marks] (Dec 2025) What are AVL trees? Explain LL, RR, LR, RL rotations

Heap

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. ==A heap is a complete binary tree stored in an array in which every parent is <= its children (min-heap) or >= its children (max-heap).==

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-07" viewBox="0 0 448 262" width="448" height="262" role="img" aria-label="Min-heap built from 6 15 50 3 33 45 40 80 10; array 3 6 40 10 33 50 45 80 15"><style>#dsfig-u3-07 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-07 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-07 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-07 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-07 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-07 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-07 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-07 .t{fill:#16181D;font-weight:500}#dsfig-u3-07 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-07 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-07 .dot{fill:#16181D}#dsfig-u3-07 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-07 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-07 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-07 .ah{fill:#454C5A}#dsfig-u3-07 .ah.hi{fill:#2340B8}#dsfig-u3-07 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-07 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-07 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-07 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-07 .e{stroke:#B1B7C3}html.dark #dsfig-u3-07 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-07 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-07 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-07 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-07 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-07 .t{fill:#E6E8ED}html.dark #dsfig-u3-07 .t.inv{fill:#0F1115}html.dark #dsfig-u3-07 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-07 .dot{fill:#E6E8ED}html.dark #dsfig-u3-07 .ann{fill:#8FA3FF}html.dark #dsfig-u3-07 .lbl{fill:#858D9C}html.dark #dsfig-u3-07 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-07 .ah{fill:#B1B7C3}html.dark #dsfig-u3-07 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-07 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-07 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-07 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah16" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh16" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="256" y1="39" x2="168" y2="103"/><line class="e" x1="256" y1="39" x2="344" y2="103"/><line class="e" x1="168" y1="103" x2="80" y2="167"/><line class="e" x1="168" y1="103" x2="212" y2="167"/><line class="e" x1="80" y1="167" x2="36" y2="231"/><line class="e" x1="80" y1="167" x2="124" y2="231"/><line class="e" x1="344" y1="103" x2="300" y2="167"/><line class="e" x1="344" y1="103" x2="388" y2="167"/><circle class="n" cx="256" cy="39" r="17"/><text class="t" x="256" y="39" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="168" cy="103" r="17"/><text class="t" x="168" y="103" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="80" cy="167" r="17"/><text class="t" x="80" y="167" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">80</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">15</text><circle class="n" cx="212" cy="167" r="17"/><text class="t" x="212" y="167" dy=".35em" text-anchor="middle">33</text><circle class="n" cx="344" cy="103" r="17"/><text class="t" x="344" y="103" dy=".35em" text-anchor="middle">40</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">50</text><circle class="n" cx="388" cy="167" r="17"/><text class="t" x="388" y="167" dy=".35em" text-anchor="middle">45</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Min-heap built from 6 15 50 3 33 45 40 80 10; array 3 6 40 10 33 50 45 80 15</figcaption></figure>

Key points.

  1. In array form (index from 0) the children of i are 2i+1 and 2i+2 and the parent is (i-1)/2, so no pointers are needed.
  2. Min-heap keeps the smallest key at the root, max-heap the largest.
  3. Insert: place the key at the next free leaf and sift it up while it is smaller than its parent; O(log n).
  4. Delete-root: move the last element to the root and sift it down with the smaller child until the property holds; O(log n).
  5. Heapify restores the property at one node; building a heap of n keys bottom-up is O(n).
  6. Insertion trace for 6 15 50 3 33 45 40 80 10: 6, 15, 50 need no swap; 3 swaps with 15 and then with 6 to reach the root; 33 stays; 45 swaps with 50; 40 swaps with 45; 80 stays; 10 swaps with 15 and stops below 6, giving [3,6,40,10,33,50,45,80,15].

Extract-min example. Remove 3: move 15 to the root, sift down with 6 then 10, result [6,10,40,15,33,50,45,80].

Answer frame. Open with the definition and min/max difference; draw the tree with its array; explain insert, delete, heapify with the example; close with O(log n) and use in heap sort and priority queues.

Asked: [7 marks] (May 2019) What is a MIN-heap? Create the MIN-heap for 6, 15, 50, 3, 33, 45, 40, 80, 10 Asked: [7 marks] (Jun 2023) What is a heap? Explain its operations with an example

Applications and comparison of various types of tree

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Different trees suit different jobs: general trees model hierarchies, BSTs give ordered search, heaps give priority access, and balanced or multiway trees keep search fast.

Key points.

  1. General trees model file systems; expression trees serve compilers.
  2. BST search is O(log n) on average but O(n) if skewed; AVL and red-black guarantee O(log n).
  3. AVL is stricter, so it searches faster; red-black rotates less, so it updates faster.
  4. Heaps serve priority queues; B and B+ trees serve disk indexes.

Introduction to forest

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A forest is a collection of zero or more disjoint trees; removing the root of a tree leaves a forest of its subtrees.

Key points.

  1. A forest with n nodes and t trees has n - t edges.
  2. A forest can be converted into one binary tree: the first child becomes the left link and the next sibling becomes the right link.

multi-way Tree

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A multi-way (m-way) search tree is a search tree in which each node has up to m children and m - 1 sorted keys.

Key points.

  1. A node with k keys has k + 1 children, and keys in child i lie between key i and key i+1.
  2. It generalises the BST (m = 2), and searching picks the correct child by comparing with the keys of the node.
  3. It is not balanced by itself; B-trees add balancing rules.

B tree

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A B-tree of order m is a balanced multiway search tree in which every node has at most m children and m - 1 keys, and all leaves are at the same level.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-08" viewBox="0 0 460 130" width="460" height="130" role="img" aria-label="B-tree of order 5 for 2 8 5 6 13 9 14 12 19 24 18 15 16 20 21 (root 6, 12, 18)"><style>#dsfig-u3-08 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-08 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-08 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-08 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-08 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-08 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-08 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-08 .t{fill:#16181D;font-weight:500}#dsfig-u3-08 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-08 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-08 .dot{fill:#16181D}#dsfig-u3-08 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-08 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-08 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-08 .ah{fill:#454C5A}#dsfig-u3-08 .ah.hi{fill:#2340B8}#dsfig-u3-08 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-08 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-08 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-08 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-08 .e{stroke:#B1B7C3}html.dark #dsfig-u3-08 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-08 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-08 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-08 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-08 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-08 .t{fill:#E6E8ED}html.dark #dsfig-u3-08 .t.inv{fill:#0F1115}html.dark #dsfig-u3-08 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-08 .dot{fill:#E6E8ED}html.dark #dsfig-u3-08 .ann{fill:#8FA3FF}html.dark #dsfig-u3-08 .lbl{fill:#858D9C}html.dark #dsfig-u3-08 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-08 .ah{fill:#B1B7C3}html.dark #dsfig-u3-08 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-08 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-08 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-08 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah17" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh17" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="158" y1="52" x2="44" y2="101"/><line class="e" x1="188" y1="52" x2="120" y2="101"/><line class="e" x1="218" y1="52" x2="226" y2="101"/><line class="e" x1="248" y1="52" x2="362" y2="101"/><rect class="n" x="158" y="22" width="90" height="30" rx="3"/><text class="t" x="173" y="37" dy=".35em" text-anchor="middle">6</text><line class="kd" x1="188" y1="22" x2="188" y2="52"/><text class="t" x="203" y="37" dy=".35em" text-anchor="middle">12</text><line class="kd" x1="218" y1="22" x2="218" y2="52"/><text class="t" x="233" y="37" dy=".35em" text-anchor="middle">18</text><rect class="n" x="14" y="86" width="60" height="30" rx="3"/><text class="t" x="29" y="101" dy=".35em" text-anchor="middle">2</text><line class="kd" x1="44" y1="86" x2="44" y2="116"/><text class="t" x="59" y="101" dy=".35em" text-anchor="middle">5</text><rect class="n" x="90" y="86" width="60" height="30" rx="3"/><text class="t" x="105" y="101" dy=".35em" text-anchor="middle">8</text><line class="kd" x1="120" y1="86" x2="120" y2="116"/><text class="t" x="135" y="101" dy=".35em" text-anchor="middle">9</text><rect class="n" x="166" y="86" width="120" height="30" rx="3"/><text class="t" x="181" y="101" dy=".35em" text-anchor="middle">13</text><line class="kd" x1="196" y1="86" x2="196" y2="116"/><text class="t" x="211" y="101" dy=".35em" text-anchor="middle">14</text><line class="kd" x1="226" y1="86" x2="226" y2="116"/><text class="t" x="241" y="101" dy=".35em" text-anchor="middle">15</text><line class="kd" x1="256" y1="86" x2="256" y2="116"/><text class="t" x="271" y="101" dy=".35em" text-anchor="middle">16</text><rect class="n" x="302" y="86" width="120" height="30" rx="3"/><text class="t" x="317" y="101" dy=".35em" text-anchor="middle">19</text><line class="kd" x1="332" y1="86" x2="332" y2="116"/><text class="t" x="347" y="101" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="362" y1="86" x2="362" y2="116"/><text class="t" x="377" y="101" dy=".35em" text-anchor="middle">21</text><line class="kd" x1="392" y1="86" x2="392" y2="116"/><text class="t" x="407" y="101" dy=".35em" text-anchor="middle">24</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">B-tree of order 5 for 2 8 5 6 13 9 14 12 19 24 18 15 16 20 21 (root 6, 12, 18)</figcaption></figure>

Key points.

  1. Order 5 means at most 5 children and 4 keys per node; every node except the root has at least 3 children, i.e. 2 keys.
  2. The root has at least 2 children unless it is a leaf, and a node with k keys has k + 1 children.
  3. All leaves are on one level, so the tree is height-balanced and search is O(log n).
  4. Insertion goes to a leaf; on the fifth key the node splits, the median moves up to the parent, and a split reaching the root is the only way the height grows.
  5. Each node fits a disk block, so few disk reads are needed; B-trees index databases and file systems.
  6. Trace: 2 8 5 6 fill one node; 13 overflows, median 6 goes up; 12 overflows 8 9 12 13 14, median 12 up; 18 overflows 13 14 18 19 24, median 18 up; 15, 16, 20, 21 fill leaves; duplicate 5 is ignored.

B-tree versus red-black. B-tree is multiway with many keys per node, suited to disk; red-black is binary, balanced by colours, suited to memory.

Threaded versus unthreaded.

Threaded Unthreaded
NULL pointers hold threads to inorder neighbours NULL pointers stay NULL
Inorder traversal without stack or recursion Needs recursion or a stack
Extra bit per pointer marks thread No extra field
NULL links put to use NULL links wasted

Answer frame. Open with the definition and order, state max 4 and min 2 keys; insert step by step drawing the tree after each split and marking the promoted median; close with the final tree. For the short note add the B-tree versus red-black comparison.

Pitfall: In order 5 a node splits on the fifth key, and the median (third key) moves up; do not split at four keys. Asked: [7 marks] (Nov 2018, May 2019) Construct a B-tree of order 5 for 2, 8, 5, 6, 13, 9, 14, 12, 19, 24, 18, 15, 5, 16, 20, 21 Asked: [7 marks] (Jun 2020) Explain briefly: B trees; Red Black trees Asked: [5 marks] (Dec 2023) Difference between threaded and unthreaded binary tree; what is a B-tree?

B+ tree

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A B+ tree is a B-tree variant in which all data records live in the leaves, internal nodes hold only copies of keys as guides, and the leaves are linked in a chain.

Key points.

  1. Internal nodes store only index keys, so the tree is shallower.
  2. Every search reaches a leaf, so all searches cost the same.
  3. Linked leaves make range queries fast.
  4. It is the standard database index.

B* tree

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A B* tree is a B-tree variant in which every node except the root must be at least two-thirds full instead of half full.

Key points.

  1. On overflow, keys first move to a sibling; only when two siblings are full do two nodes split into three.
  2. This gives better space use and fewer splits.
  3. Insertion is more complex than in a B-tree.

red-black tree

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A red-black tree is a self-balancing binary search tree in which every node is coloured red or black so that no path from the root to a leaf is more than twice as long as any other.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-09" viewBox="0 0 580 262" width="580" height="262" role="img" aria-label="Red-black tree after inserting 12 30 36 18 25 9 4 2 17 14 20 47 (highlighted = red, others black)"><style>#dsfig-u3-09 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-09 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-09 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-09 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-09 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-09 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-09 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-09 .t{fill:#16181D;font-weight:500}#dsfig-u3-09 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-09 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-09 .dot{fill:#16181D}#dsfig-u3-09 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-09 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-09 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-09 .ah{fill:#454C5A}#dsfig-u3-09 .ah.hi{fill:#2340B8}#dsfig-u3-09 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-09 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-09 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-09 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-09 .e{stroke:#B1B7C3}html.dark #dsfig-u3-09 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-09 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-09 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-09 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-09 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-09 .t{fill:#E6E8ED}html.dark #dsfig-u3-09 .t.inv{fill:#0F1115}html.dark #dsfig-u3-09 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-09 .dot{fill:#E6E8ED}html.dark #dsfig-u3-09 .ann{fill:#8FA3FF}html.dark #dsfig-u3-09 .lbl{fill:#858D9C}html.dark #dsfig-u3-09 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-09 .ah{fill:#B1B7C3}html.dark #dsfig-u3-09 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-09 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-09 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-09 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah18" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh18" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="300" y1="39" x2="124" y2="103"/><line class="e" x1="300" y1="39" x2="432" y2="103"/><line class="e" x1="124" y1="103" x2="80" y2="167"/><line class="e" x1="124" y1="103" x2="212" y2="167"/><line class="e" x1="80" y1="167" x2="36" y2="231"/><line class="e" x1="212" y1="167" x2="168" y2="231"/><line class="e" x1="212" y1="167" x2="256" y2="231"/><line class="e" x1="432" y1="103" x2="388" y2="167"/><line class="e" x1="432" y1="103" x2="476" y2="167"/><line class="e" x1="388" y1="167" x2="344" y2="231"/><line class="e" x1="476" y1="167" x2="520" y2="231"/><circle class="n" cx="300" cy="39" r="17"/><text class="t" x="300" y="39" dy=".35em" text-anchor="middle">18</text><circle class="n hi" cx="124" cy="103" r="17"/><text class="t" x="124" y="103" dy=".35em" text-anchor="middle">9</text><circle class="n" cx="80" cy="167" r="17"/><text class="t" x="80" y="167" dy=".35em" text-anchor="middle">4</text><circle class="n hi" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="212" cy="167" r="17"/><text class="t" x="212" y="167" dy=".35em" text-anchor="middle">14</text><circle class="n hi" cx="168" cy="231" r="17"/><text class="t" x="168" y="231" dy=".35em" text-anchor="middle">12</text><circle class="n hi" cx="256" cy="231" r="17"/><text class="t" x="256" y="231" dy=".35em" text-anchor="middle">17</text><circle class="n hi" cx="432" cy="103" r="17"/><text class="t" x="432" y="103" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="388" cy="167" r="17"/><text class="t" x="388" y="167" dy=".35em" text-anchor="middle">25</text><circle class="n hi" cx="344" cy="231" r="17"/><text class="t" x="344" y="231" dy=".35em" text-anchor="middle">20</text><circle class="n" cx="476" cy="167" r="17"/><text class="t" x="476" y="167" dy=".35em" text-anchor="middle">36</text><circle class="n hi" cx="520" cy="231" r="17"/><text class="t" x="520" y="231" dy=".35em" text-anchor="middle">47</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Red-black tree after inserting 12 30 36 18 25 9 4 2 17 14 20 47 (highlighted = red, others black)</figcaption></figure>

Key points.

  1. Every node is red or black, and the root is black.
  2. Every leaf (NIL) is black.
  3. A red node cannot have a red child, so no two red nodes are adjacent.
  4. Every path from a node to its descendant NIL leaves contains the same number of black nodes, called the black-height.
  5. So the longest path is at most twice the shortest, height is at most 2 log(n+1), and all operations are O(log n).
  6. Insertion adds a red node; if its parent is red, a red uncle means recolour parent, uncle and grandparent and move up, a black uncle means rotate and recolour.
  7. Deleting a black node leaves a double-black, fixed by recolouring or rotations using the sibling's colour.
  8. Interval tree: a red-black tree keyed on the low end of each interval [low, high], each node also storing the maximum high in its subtree; to find an overlap with [l, h], go left if the left child's max >= l, else right; used in scheduling.

Insertion trace (Nov 2022). 12 black root; 30 red; 36: rotate left at 12; 18: recolour 12, 36 black; 25: rotate left at 12; 9: recolour; 4: rotate right at 12; 2: recolour, then rotate right at 30, root 18; 17: plain; 14: RL at 12; 20, 47: plain.

Deletion. 18: successor 20 takes its place. 2: red leaf removed. 30: successor 36 takes its colour and red 47 turns black. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-10" viewBox="0 0 448 262" width="448" height="262" role="img" aria-label="After deleting 18, 2, 30 (highlighted = red, others black)"><style>#dsfig-u3-10 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-10 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-10 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-10 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-10 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-10 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-10 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-10 .t{fill:#16181D;font-weight:500}#dsfig-u3-10 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-10 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-10 .dot{fill:#16181D}#dsfig-u3-10 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-10 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-10 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-10 .ah{fill:#454C5A}#dsfig-u3-10 .ah.hi{fill:#2340B8}#dsfig-u3-10 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-10 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-10 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-10 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-10 .e{stroke:#B1B7C3}html.dark #dsfig-u3-10 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-10 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-10 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-10 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-10 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-10 .t{fill:#E6E8ED}html.dark #dsfig-u3-10 .t.inv{fill:#0F1115}html.dark #dsfig-u3-10 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-10 .dot{fill:#E6E8ED}html.dark #dsfig-u3-10 .ann{fill:#8FA3FF}html.dark #dsfig-u3-10 .lbl{fill:#858D9C}html.dark #dsfig-u3-10 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-10 .ah{fill:#B1B7C3}html.dark #dsfig-u3-10 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-10 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-10 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-10 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah19" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh19" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="256" y1="39" x2="80" y2="103"/><line class="e" x1="256" y1="39" x2="344" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="168" y2="167"/><line class="e" x1="168" y1="167" x2="124" y2="231"/><line class="e" x1="168" y1="167" x2="212" y2="231"/><line class="e" x1="344" y1="103" x2="300" y2="167"/><line class="e" x1="344" y1="103" x2="388" y2="167"/><circle class="n" cx="256" cy="39" r="17"/><text class="t" x="256" y="39" dy=".35em" text-anchor="middle">20</text><circle class="n hi" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">9</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="168" cy="167" r="17"/><text class="t" x="168" y="167" dy=".35em" text-anchor="middle">14</text><circle class="n hi" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">12</text><circle class="n hi" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">17</text><circle class="n hi" cx="344" cy="103" r="17"/><text class="t" x="344" y="103" dy=".35em" text-anchor="middle">36</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">25</text><circle class="n" cx="388" cy="167" r="17"/><text class="t" x="388" y="167" dy=".35em" text-anchor="middle">47</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">After deleting 18, 2, 30 (highlighted = red, others black)</figcaption></figure>

Answer frame. Open with the definition; list the properties and black-height; explain the balance guarantee, then insertion and deletion fixes; for the 14-mark question show each insertion's case and tree.

Pitfall: A new node is always red; a red root is recoloured black at the end. Asked: [7 marks] (Nov 2019) What are red black trees? Discuss their properties in detail Asked: [7 marks] (May 2019) Describe in detail about interval tree Asked: [14 marks] (Nov 2022) Insert 12, 30, 36, 18, 25, 9, 4, 2, 17, 14, 20, 47 in a red-black tree; delete 18, 2, 30

Last-minute revision

  • Height counts down to the deepest leaf, depth from the root; n nodes have n - 1 edges.
  • BST: left < root < right; inorder gives sorted keys; search, insert and delete are O(h).
  • BST delete: leaf, one child, two children (inorder successor); root is the last postorder or first preorder element.
  • AVL: BF = h(left) - h(right) in {-1, 0, 1}; LL/RR single, LR/RL double rotation, each O(1).
  • Min-heap: complete tree, parent <= children; children of i are 2i+1 and 2i+2.
  • Heap insert sifts up, delete-root sifts down, both O(log n); build heap is O(n).
  • B-tree of order 5: max 4 keys, min 2 keys, all leaves on one level; split on the fifth key.
  • B+ tree: data only in linked leaves; B* tree: nodes 2/3 full.
  • Red-black: root black, red has black children, equal black-height, height <= 2 log(n+1).

Memory hooks

  • Pre, In, Post: the root is First, Middle, Last.
  • AVL: rotation name = path of the new key; two different letters mean a double rotation.
  • B-tree order 5: fifth key splits, median goes up.
  • Red-black: "root black, red has black kids, blacks equal".

Coverage checklist

  • Tree: Definitions - Height, depth, order, degree etc.: Q21, Q22.
  • Binary Search Tree - Operations, Traversal, Search: Q9 to Q18.
  • AVL Tree: Q1 to Q6.
  • Heap: Q19, Q20.
  • Applications and comparison of various types of tree: no past question.
  • Introduction to forest: forest in Q22.
  • multi-way Tree: no past question.
  • B tree: Q7, Q8, Q25.
  • B+ tree: no past question.
  • B* tree: no past question.
  • red-black tree: Q2, Q23, Q24, Q8.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in