Data Structures (AD-303) - Unit 3 Short Notes

How unit 3 is examined

Terminology, BSTs with traversals and AVL rotations carry most marks; B-tree, heap, red-black, expression trees and Huffman are asked once each.

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 finite set of nodes with one special node called the root, where the remaining nodes form disjoint subtrees, each itself a tree.</mark>

Key points.

1. Depth of a node is the number of edges from the root to it, so the root has depth 0.
2. Height of a node is the number of edges on the longest path down to a leaf, so a leaf has height 0; tree height is the root's height.
3. Degree of a node is the number of children it has; the degree of a tree is the largest node degree.
4. Order is the maximum number of children any node may have (5 for a B-tree of order 5), fixed for the tree, whereas degree is counted per node.
5. A leaf has degree 0; a forest is a set of disjoint trees, left when the root is deleted.
6. An extended binary tree (2-tree) replaces every null pointer with an external square node, so every original node, leaves included, has exactly 2 children.

<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 316 198" width="316" height="198" role="img" aria-label="A is the root (depth 0, height 2, degree 2); D, E, F are leaves; B has depth 1, height 1, degree 2."><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="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="168" y1="39" x2="80" y2="103"/><line class="e" x1="168" y1="39" x2="212" 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="212" y1="103" x2="256" y2="167"/><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="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="124" cy="167" r="17"/><text class="t" x="124" y="167" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="212" cy="103" r="17"/><text class="t" x="212" 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">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">A is the root (depth 0, height 2, degree 2); D, E, F are leaves; B has depth 1, height 1, degree 2.</figcaption></figure>

Internal and external nodes. An internal node has at least one child; an external node is a leaf, or, in an extended tree, a square box standing for a null position. Extending $A(B(D,E),C(,F))$ makes all $n=6$ nodes internal and adds $n+1=7$ boxes.

<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 624 262" width="624" height="262" role="img" aria-label="Extended tree: circles A-F are internal, boxes x1-x7 external"><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="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="344" y1="39" x2="168" y2="103"/><line class="e" x1="344" y1="39" x2="432" y2="103"/><line class="e" x1="168" y1="103" x2="80" y2="167"/><line class="e" x1="168" y1="103" x2="256" 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="256" y1="167" x2="212" y2="231"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><line class="e" x1="432" y1="103" x2="388" y2="167"/><line class="e" x1="432" y1="103" x2="520" y2="167"/><line class="e" x1="520" y1="167" x2="476" y2="231"/><line class="e" x1="520" y1="167" x2="564" y2="231"/><circle class="n" cx="344" cy="39" r="17"/><text class="t" x="344" y="39" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="168" cy="103" r="17"/><text class="t" x="168" y="103" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="80" cy="167" r="17"/><text class="t" x="80" y="167" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">x1</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">x2</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">x3</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">x4</text><circle class="n" cx="432" cy="103" r="17"/><text class="t" x="432" y="103" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="388" cy="167" r="17"/><text class="t" x="388" y="167" dy=".35em" text-anchor="middle">x5</text><circle class="n" cx="520" cy="167" r="17"/><text class="t" x="520" y="167" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="476" cy="231" r="17"/><text class="t" x="476" y="231" dy=".35em" text-anchor="middle">x6</text><circle class="n" cx="564" cy="231" r="17"/><text class="t" x="564" y="231" dy=".35em" text-anchor="middle">x7</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Extended tree: circles A-F are internal, boxes x1-x7 external</figcaption></figure>

Internal path length $I$ (sum of internal-node depths) $=0+1+1+2+2+2=8$; external path length $E$ (sum of box depths) $=3\times6+2=20$, and $E=I+2n=8+12=20$. Average search cost is $(I+n)/n=14/6\approx2.33$ comparisons if successful, $E/(n+1)=20/7\approx2.86$ if not; Huffman coding minimises weighted $E$.

Proof (induction on $h$). Base: $h=0$ is the root alone, $2^1-1=1$ node. Step: assume $N(h-1)\le2^h-1$; height $h$ means a root plus two subtrees of height $\le h-1$, so $N(h)\le1+2N(h-1)=1+2(2^h-1)=2^{h+1}-1$. Directly, level $i$ holds at most $2^i$ nodes:

$$N=\sum_{i=0}^{h}2^i=1+2+4+\dots+2^h=\frac{2^{h+1}-1}{2-1}=2^{h+1}-1$$

Maximum $=2^{h+1}-1$ (one node when $h=0$).

Answer frame. Open with the definition and a labelled tree; give the two tables; for internal/external nodes define both, draw the extended tree, compute $I$, $E$, search costs; prove the maximum by induction.

Asked: [7 marks] (Jun 2023, Jun 2024, Dec 2025) Differences between (i) height and depth (ii) order and degree Asked: [7 marks] (Dec 2025) Define height, depth, degree of a node and forest Asked: [4 marks] (Dec 2023) Define extended binary tree with example Asked: [7 marks] (Jun 2023, Jun 2024) Show that the maximum number of nodes in a binary tree of height $h$ is $2^{h+1}-1$ Asked: [7 marks] (Dec 2022) Short note on internal trees, explain with example

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>

Key points.

1. Search goes left if the key is smaller and right if larger until a match or null; it costs $O(h)$: $O(\log n)$ balanced, $O(n)$ skewed.
2. Insertion attaches the new node as a leaf where the search ended.
3. Deleting a leaf removes it; deleting a node with one child replaces it by that child.
4. Deleting a node with two children copies in the inorder successor (smallest key of the right subtree) or predecessor, then deletes that node, which has at most one child.
5. Traversals are recursive: inorder is Left-Root-Right, preorder is Root-Left-Right, postorder is Left-Right-Root.
6. Uses: inorder lists a BST in ascending order; preorder copies a tree and gives prefix form; postorder deletes or frees a tree (children first) and gives postfix form.

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

<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 198" width="360" height="198" role="img" aria-label="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-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="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="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">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>

Example (Dec 2023, Dec 2024). Insert 45, 32, 90, 34, 68, 72, 15, 24, 30, 66, 11, 50, 10:

<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 2136 352" width="2136" height="352" role="img" aria-label="Tree after insertions 4, 6, 9, 11, 13 (others add one leaf each)"><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="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><text class="lbl" x="14" y="22">i4</text><line class="e" x1="124" y1="65" x2="36" y2="129"/><line class="e" x1="124" y1="65" x2="168" y2="129"/><line class="e" x1="36" y1="129" x2="80" y2="193"/><circle class="n" cx="124" cy="65" r="17"/><text class="t" x="124" y="65" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="36" cy="129" r="17"/><text class="t" x="36" y="129" dy=".35em" text-anchor="middle">32</text><circle class="n" cx="80" cy="193" r="17"/><text class="t" x="80" y="193" dy=".35em" text-anchor="middle">34</text><circle class="n" cx="168" cy="129" r="17"/><text class="t" x="168" y="129" dy=".35em" text-anchor="middle">90</text><text class="lbl" x="238" y="22">i6</text><line class="e" x1="348" y1="65" x2="260" y2="129"/><line class="e" x1="348" y1="65" x2="480" y2="129"/><line class="e" x1="260" y1="129" x2="304" y2="193"/><line class="e" x1="480" y1="129" x2="392" y2="193"/><line class="e" x1="392" y1="193" x2="436" y2="257"/><circle class="n" cx="348" cy="65" r="17"/><text class="t" x="348" y="65" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="260" cy="129" r="17"/><text class="t" x="260" y="129" dy=".35em" text-anchor="middle">32</text><circle class="n" cx="304" cy="193" r="17"/><text class="t" x="304" y="193" dy=".35em" text-anchor="middle">34</text><circle class="n" cx="480" cy="129" r="17"/><text class="t" x="480" y="129" dy=".35em" text-anchor="middle">90</text><circle class="n" cx="392" cy="193" r="17"/><text class="t" x="392" y="193" dy=".35em" text-anchor="middle">68</text><circle class="n" cx="436" cy="257" r="17"/><text class="t" x="436" y="257" dy=".35em" text-anchor="middle">72</text><text class="lbl" x="550" y="22">i9</text><line class="e" x1="792" y1="65" x2="704" y2="129"/><line class="e" x1="792" y1="65" x2="924" y2="129"/><line class="e" x1="704" y1="129" x2="572" y2="193"/><line class="e" x1="704" y1="129" x2="748" y2="193"/><line class="e" x1="572" y1="193" x2="616" y2="257"/><line class="e" x1="616" y1="257" x2="660" y2="321"/><line class="e" x1="924" y1="129" x2="836" y2="193"/><line class="e" x1="836" y1="193" x2="880" y2="257"/><circle class="n" cx="792" cy="65" r="17"/><text class="t" x="792" y="65" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="704" cy="129" r="17"/><text class="t" x="704" y="129" dy=".35em" text-anchor="middle">32</text><circle class="n" cx="572" cy="193" r="17"/><text class="t" x="572" y="193" dy=".35em" text-anchor="middle">15</text><circle class="n" cx="616" cy="257" r="17"/><text class="t" x="616" y="257" dy=".35em" text-anchor="middle">24</text><circle class="n" cx="660" cy="321" r="17"/><text class="t" x="660" y="321" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="748" cy="193" r="17"/><text class="t" x="748" y="193" dy=".35em" text-anchor="middle">34</text><circle class="n" cx="924" cy="129" r="17"/><text class="t" x="924" y="129" dy=".35em" text-anchor="middle">90</text><circle class="n" cx="836" cy="193" r="17"/><text class="t" x="836" y="193" dy=".35em" text-anchor="middle">68</text><circle class="n" cx="880" cy="257" r="17"/><text class="t" x="880" y="257" dy=".35em" text-anchor="middle">72</text><text class="lbl" x="994" y="22">i11</text><line class="e" x1="1280" y1="65" x2="1192" y2="129"/><line class="e" x1="1280" y1="65" x2="1456" y2="129"/><line class="e" x1="1192" y1="129" x2="1060" y2="193"/><line class="e" x1="1192" y1="129" x2="1236" y2="193"/><line class="e" x1="1060" y1="193" x2="1016" y2="257"/><line class="e" x1="1060" y1="193" x2="1104" y2="257"/><line class="e" x1="1104" y1="257" x2="1148" y2="321"/><line class="e" x1="1456" y1="129" x2="1368" y2="193"/><line class="e" x1="1368" y1="193" x2="1324" y2="257"/><line class="e" x1="1368" y1="193" x2="1412" y2="257"/><circle class="n" cx="1280" cy="65" r="17"/><text class="t" x="1280" y="65" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="1192" cy="129" r="17"/><text class="t" x="1192" y="129" dy=".35em" text-anchor="middle">32</text><circle class="n" cx="1060" cy="193" r="17"/><text class="t" x="1060" y="193" dy=".35em" text-anchor="middle">15</text><circle class="n" cx="1016" cy="257" r="17"/><text class="t" x="1016" y="257" dy=".35em" text-anchor="middle">11</text><circle class="n" cx="1104" cy="257" r="17"/><text class="t" x="1104" y="257" dy=".35em" text-anchor="middle">24</text><circle class="n" cx="1148" cy="321" r="17"/><text class="t" x="1148" y="321" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="1236" cy="193" r="17"/><text class="t" x="1236" y="193" dy=".35em" text-anchor="middle">34</text><circle class="n" cx="1456" cy="129" r="17"/><text class="t" x="1456" y="129" dy=".35em" text-anchor="middle">90</text><circle class="n" cx="1368" cy="193" r="17"/><text class="t" x="1368" y="193" dy=".35em" text-anchor="middle">68</text><circle class="n" cx="1324" cy="257" r="17"/><text class="t" x="1324" y="257" dy=".35em" text-anchor="middle">66</text><circle class="n" cx="1412" cy="257" r="17"/><text class="t" x="1412" y="257" dy=".35em" text-anchor="middle">72</text><text class="lbl" x="1526" y="22">i13</text><line class="e" x1="1856" y1="65" x2="1768" y2="129"/><line class="e" x1="1856" y1="65" x2="2076" y2="129"/><line class="e" x1="1768" y1="129" x2="1636" y2="193"/><line class="e" x1="1768" y1="129" x2="1812" y2="193"/><line class="e" x1="1636" y1="193" x2="1592" y2="257"/><line class="e" x1="1636" y1="193" x2="1680" y2="257"/><line class="e" x1="1592" y1="257" x2="1548" y2="321"/><line class="e" x1="1680" y1="257" x2="1724" y2="321"/><line class="e" x1="2076" y1="129" x2="1988" y2="193"/><line class="e" x1="1988" y1="193" x2="1944" y2="257"/><line class="e" x1="1988" y1="193" x2="2032" y2="257"/><line class="e" x1="1944" y1="257" x2="1900" y2="321"/><circle class="n" cx="1856" cy="65" r="17"/><text class="t" x="1856" y="65" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="1768" cy="129" r="17"/><text class="t" x="1768" y="129" dy=".35em" text-anchor="middle">32</text><circle class="n" cx="1636" cy="193" r="17"/><text class="t" x="1636" y="193" dy=".35em" text-anchor="middle">15</text><circle class="n" cx="1592" cy="257" r="17"/><text class="t" x="1592" y="257" dy=".35em" text-anchor="middle">11</text><circle class="n" cx="1548" cy="321" r="17"/><text class="t" x="1548" y="321" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="1680" cy="257" r="17"/><text class="t" x="1680" y="257" dy=".35em" text-anchor="middle">24</text><circle class="n" cx="1724" cy="321" r="17"/><text class="t" x="1724" y="321" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="1812" cy="193" r="17"/><text class="t" x="1812" y="193" dy=".35em" text-anchor="middle">34</text><circle class="n" cx="2076" cy="129" r="17"/><text class="t" x="2076" y="129" dy=".35em" text-anchor="middle">90</text><circle class="n" cx="1988" cy="193" r="17"/><text class="t" x="1988" y="193" dy=".35em" text-anchor="middle">68</text><circle class="n" cx="1944" cy="257" r="17"/><text class="t" x="1944" y="257" dy=".35em" text-anchor="middle">66</text><circle class="n" cx="1900" cy="321" r="17"/><text class="t" x="1900" y="321" dy=".35em" text-anchor="middle">50</text><circle class="n" cx="2032" cy="257" r="17"/><text class="t" x="2032" y="257" dy=".35em" text-anchor="middle">72</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Tree after insertions 4, 6, 9, 11, 13 (others add one leaf each)</figcaption></figure>

Second variant: insert 45, 26, 10, 60, 70, 30, 40; delete 10 (leaf), 60 (70 replaces it), 45 (successor 70):

<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 1164 288" width="1164" height="288" role="img" aria-label="Second variant: after insertion, then after each deletion"><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="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><text class="lbl" x="14" y="22">built</text><line class="e" x1="212" y1="65" x2="80" y2="129"/><line class="e" x1="212" y1="65" x2="256" y2="129"/><line class="e" x1="80" y1="129" x2="36" y2="193"/><line class="e" x1="80" y1="129" x2="124" y2="193"/><line class="e" x1="124" y1="193" x2="168" y2="257"/><line class="e" x1="256" y1="129" x2="300" y2="193"/><circle class="n" cx="212" cy="65" r="17"/><text class="t" x="212" y="65" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="80" cy="129" r="17"/><text class="t" x="80" y="129" dy=".35em" text-anchor="middle">26</text><circle class="n" cx="36" cy="193" r="17"/><text class="t" x="36" y="193" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="124" cy="193" r="17"/><text class="t" x="124" y="193" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="168" cy="257" r="17"/><text class="t" x="168" y="257" dy=".35em" text-anchor="middle">40</text><circle class="n" cx="256" cy="129" r="17"/><text class="t" x="256" y="129" dy=".35em" text-anchor="middle">60</text><circle class="n" cx="300" cy="193" r="17"/><text class="t" x="300" y="193" dy=".35em" text-anchor="middle">70</text><text class="lbl" x="370" y="22">del10</text><line class="e" x1="524" y1="65" x2="392" y2="129"/><line class="e" x1="524" y1="65" x2="568" y2="129"/><line class="e" x1="392" y1="129" x2="436" y2="193"/><line class="e" x1="436" y1="193" x2="480" y2="257"/><line class="e" x1="568" y1="129" x2="612" y2="193"/><circle class="n" cx="524" cy="65" r="17"/><text class="t" x="524" y="65" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="392" cy="129" r="17"/><text class="t" x="392" y="129" dy=".35em" text-anchor="middle">26</text><circle class="n" cx="436" cy="193" r="17"/><text class="t" x="436" y="193" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="480" cy="257" r="17"/><text class="t" x="480" y="257" dy=".35em" text-anchor="middle">40</text><circle class="n" cx="568" cy="129" r="17"/><text class="t" x="568" y="129" dy=".35em" text-anchor="middle">60</text><circle class="n" cx="612" cy="193" r="17"/><text class="t" x="612" y="193" dy=".35em" text-anchor="middle">70</text><text class="lbl" x="682" y="22">del60</text><line class="e" x1="836" y1="65" x2="704" y2="129"/><line class="e" x1="836" y1="65" x2="880" y2="129"/><line class="e" x1="704" y1="129" x2="748" y2="193"/><line class="e" x1="748" y1="193" x2="792" y2="257"/><circle class="n" cx="836" cy="65" r="17"/><text class="t" x="836" y="65" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="704" cy="129" r="17"/><text class="t" x="704" y="129" dy=".35em" text-anchor="middle">26</text><circle class="n" cx="748" cy="193" r="17"/><text class="t" x="748" y="193" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="792" cy="257" r="17"/><text class="t" x="792" y="257" dy=".35em" text-anchor="middle">40</text><circle class="n" cx="880" cy="129" r="17"/><text class="t" x="880" y="129" dy=".35em" text-anchor="middle">70</text><text class="lbl" x="950" y="22">del45</text><line class="e" x1="1104" y1="65" x2="972" y2="129"/><line class="e" x1="972" y1="129" x2="1016" y2="193"/><line class="e" x1="1016" y1="193" x2="1060" y2="257"/><circle class="n" cx="1104" cy="65" r="17"/><text class="t" x="1104" y="65" dy=".35em" text-anchor="middle">70</text><circle class="n" cx="972" cy="129" r="17"/><text class="t" x="972" y="129" dy=".35em" text-anchor="middle">26</text><circle class="n" cx="1016" cy="193" r="17"/><text class="t" x="1016" y="193" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="1060" cy="257" r="17"/><text class="t" x="1060" y="257" dy=".35em" text-anchor="middle">40</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Second variant: after insertion, then after each deletion</figcaption></figure>

void inorder(struct node *t)   { if (t) { inorder(t->left); printf("%d ", t->data); inorder(t->right); } }
void preorder(struct node *t)  { if (t) { printf("%d ", t->data); preorder(t->left); preorder(t->right); } }
void postorder(struct node *t) { if (t) { postorder(t->left); postorder(t->right); printf("%d ", t->data); } }

Steps: tree from inorder and postorder.

Step 1: The last postorder element is the root.
Step 2: Find it in inorder; keys to its left form the left subtree, keys to its right the right subtree.
Step 3: Split postorder by the same sizes (left part first) and repeat for each subtree.

Root A splits inorder into DGB (root B) and HEICF (root C).

<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="Tree for inorder DGBAHEICF and postorder GDBHIEFCA"><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="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="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 inorder DGBAHEICF and postorder GDBHIEFCA</figcaption></figure>

For inorder DKIBAEGHJFC and postorder KDIEAGBFCJH the root is H; preorder H B I D K G A E J C F.

<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 536 326" width="536" height="326" role="img" aria-label="Tree for the Dec 2023 traversal question"><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="ah20" 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="ahh20" 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="344" y1="39" x2="168" y2="103"/><line class="e" x1="344" y1="39" x2="388" y2="103"/><line class="e" x1="168" y1="103" x2="124" y2="167"/><line class="e" x1="168" y1="103" x2="300" y2="167"/><line class="e" x1="124" y1="167" x2="36" y2="231"/><line class="e" x1="36" y1="231" x2="80" y2="295"/><line class="e" x1="300" y1="167" x2="212" y2="231"/><line class="e" x1="212" y1="231" x2="256" y2="295"/><line class="e" x1="388" y1="103" x2="476" y2="167"/><line class="e" x1="476" y1="167" x2="432" y2="231"/><circle class="n" cx="344" cy="39" r="17"/><text class="t" x="344" y="39" dy=".35em" text-anchor="middle">H</text><circle class="n" cx="168" cy="103" r="17"/><text class="t" x="168" y="103" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="124" cy="167" r="17"/><text class="t" x="124" y="167" dy=".35em" text-anchor="middle">I</text><circle class="n" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="80" cy="295" r="17"/><text class="t" x="80" y="295" dy=".35em" text-anchor="middle">K</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">G</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="256" cy="295" r="17"/><text class="t" x="256" y="295" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="388" cy="103" r="17"/><text class="t" x="388" y="103" dy=".35em" text-anchor="middle">J</text><circle class="n" cx="476" cy="167" r="17"/><text class="t" x="476" y="167" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="432" cy="231" r="17"/><text class="t" x="432" y="231" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Tree for the Dec 2023 traversal question</figcaption></figure>

Expression tree. The lowest-precedence operator applied last is the root; operands are leaves.

<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 624 326" width="624" height="326" role="img" aria-label="Dec 2024 expression tree"><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="ah21" 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="ahh21" 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="520" 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="520" y1="103" x2="432" y2="167"/><line class="e" x1="520" y1="103" x2="564" y2="167"/><line class="e" x1="432" y1="167" x2="344" y2="231"/><line class="e" x1="432" y1="167" x2="476" y2="231"/><line class="e" x1="344" y1="231" x2="300" y2="295"/><line class="e" x1="344" y1="231" x2="388" y2="295"/><circle class="n" cx="256" cy="39" r="17"/><text class="t" x="256" y="39" dy=".35em" text-anchor="middle">+</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">+</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="168" cy="167" r="17"/><text class="t" x="168" y="167" dy=".35em" text-anchor="middle"></text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">c</text><circle class="n" cx="520" cy="103" r="17"/><text class="t" x="520" y="103" dy=".35em" text-anchor="middle"></text><circle class="n" cx="432" cy="167" r="17"/><text class="t" x="432" y="167" dy=".35em" text-anchor="middle">+</text><circle class="n" cx="344" cy="231" r="17"/><text class="t" x="344" y="231" dy=".35em" text-anchor="middle">*</text><circle class="n" cx="300" cy="295" r="17"/><text class="t" x="300" y="295" dy=".35em" text-anchor="middle">d</text><circle class="n" cx="388" cy="295" r="17"/><text class="t" x="388" y="295" dy=".35em" text-anchor="middle">e</text><circle class="n" cx="476" cy="231" r="17"/><text class="t" x="476" y="231" dy=".35em" text-anchor="middle">f</text><circle class="n" cx="564" cy="167" r="17"/><text class="t" x="564" y="167" dy=".35em" text-anchor="middle">g</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Dec 2024 expression tree</figcaption></figure>

Inorder $a+b*c+d*e+f*g$; preorder $+\,+\,a\,*\,b\,c\,*\,+\,*\,d\,e\,f\,g$; postorder $a\,b\,c\,*\,+\,d\,e\,*\,f\,+\,g\,*\,+$.

Steps: build from postfix with a stack. Push each operand as a one-node tree; for an operator pop two trees (first popped is the right child), make them its children and push it; the last tree is the root.

Answer frame. Open with the BST property; redraw the tree after insertions and each deletion, naming the case; add the code; give traversals, outputs, uses; build expression trees with the stack; for construction take the root from postorder, split, recurse.

Asked: [7 marks] (Dec 2022, Dec 2023) Construct a tree from inorder DGBAHEICF and postorder GDBHIEFCA Asked: [7 marks] (Dec 2023, Dec 2024) Explain BST with example; build it from 45, 32, 90, 34, 68, 72, 15, 24, 30, 66, 11, 50, 10, delete 45, 90, 11; algorithm for insertion. Also build from 45, 26, 10, 60, 70, 30, 40 and delete 10, 60, 45 Asked: [7 marks] (Dec 2023) Construct binary tree from postorder K, D, I, E, A, G, B, F, C, J, H and inorder D, K, I, B, A, E, G, H, J, F, C; find its preorder Asked: [7 marks] (Dec 2024) How to insert and delete in a BST; write the insertion code Asked: [14 marks] (Dec 2024) Expression tree for $(a+b*c)+((d*e+f)*g)$ with preorder and postorder outputs Asked: [7 marks] (Dec 2025) Define BST; explain inorder, preorder, postorder algorithms with example

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 binary search tree in which the balance factor $BF=h_L-h_R$ of every node is -1, 0 or +1.==

Key points.

1. A node with $|BF|=2$ is unbalanced and is repaired by a rotation.
2. Insertion is done exactly as in a BST, then heights are updated upward and the lowest unbalanced node is rebalanced.
3. LL (key in the left subtree of the left child) needs one right rotation, and RR, its mirror, one left rotation.
4. LR (right subtree of the left child) needs a left rotation at the child, then a right rotation at the node; RL is the mirror.
5. One rotation (single or double) after an insertion restores balance for the whole tree, and rotations keep the inorder order.
6. Deletion is as in a BST, then walk up from the deleted node updating BFs; at an unbalanced $A$ after a right deletion, its left child $B$ has BF 0 (R0), +1 (R1) or -1 (R-1); L0, L1, L-1 mirror them.
7. R0 and R1 are a right rotation and R-1 an LR rotation; R0 keeps the subtree height, so the walk stops, while R1 and R-1 shrink it, so the walk continues, possibly to the root with $O(\log n)$ rotations.
8. Height is always $O(\log n)$, so search, insertion and deletion cost $O(\log n)$.

Diagram (rotations). $z$ is the lowest unbalanced node, $y$ its child, $x$ its grandchild on the new key's path; T1-T4 keep their left-to-right order.

<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 716 288" width="716" height="288" role="img" aria-label="LL: right rotation at z"><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="ah22" 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="ahh22" 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><text class="lbl" x="14" y="22">LL before</text><line class="e" x1="256" y1="65" x2="168" y2="129"/><line class="e" x1="256" y1="65" x2="300" y2="129"/><line class="e" x1="168" y1="129" x2="80" y2="193"/><line class="e" x1="168" y1="129" x2="212" y2="193"/><line class="e" x1="80" y1="193" x2="36" y2="257"/><line class="e" x1="80" y1="193" x2="124" y2="257"/><circle class="n" cx="256" cy="65" r="17"/><text class="t" x="256" y="65" dy=".35em" text-anchor="middle">z</text><text class="ann" x="275" y="50">+2</text><circle class="n" cx="168" cy="129" r="17"/><text class="t" x="168" y="129" dy=".35em" text-anchor="middle">y</text><text class="ann" x="187" y="114">+1</text><circle class="n" cx="80" cy="193" r="17"/><text class="t" x="80" y="193" dy=".35em" text-anchor="middle">x</text><circle class="n" cx="36" cy="257" r="17"/><text class="t" x="36" y="257" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="124" cy="257" r="17"/><text class="t" x="124" y="257" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="212" cy="193" r="17"/><text class="t" x="212" y="193" dy=".35em" text-anchor="middle">T3</text><circle class="n" cx="300" cy="129" r="17"/><text class="t" x="300" y="129" dy=".35em" text-anchor="middle">T4</text><text class="lbl" x="370" y="22">after</text><line class="e" x1="524" y1="65" x2="436" y2="129"/><line class="e" x1="524" y1="65" x2="612" y2="129"/><line class="e" x1="436" y1="129" x2="392" y2="193"/><line class="e" x1="436" y1="129" x2="480" y2="193"/><line class="e" x1="612" y1="129" x2="568" y2="193"/><line class="e" x1="612" y1="129" x2="656" y2="193"/><circle class="n" cx="524" cy="65" r="17"/><text class="t" x="524" y="65" dy=".35em" text-anchor="middle">y</text><text class="ann" x="543" y="50">0</text><circle class="n" cx="436" cy="129" r="17"/><text class="t" x="436" y="129" dy=".35em" text-anchor="middle">x</text><circle class="n" cx="392" cy="193" r="17"/><text class="t" x="392" y="193" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="480" cy="193" r="17"/><text class="t" x="480" y="193" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="612" cy="129" r="17"/><text class="t" x="612" y="129" dy=".35em" text-anchor="middle">z</text><text class="ann" x="631" y="114">0</text><circle class="n" cx="568" cy="193" r="17"/><text class="t" x="568" y="193" dy=".35em" text-anchor="middle">T3</text><circle class="n" cx="656" cy="193" r="17"/><text class="t" x="656" y="193" dy=".35em" text-anchor="middle">T4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">LL: right rotation at z</figcaption></figure> <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 716 288" width="716" height="288" role="img" aria-label="RR: left rotation at z"><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="ah23" 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="ahh23" 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><text class="lbl" x="14" y="22">RR before</text><line class="e" x1="80" y1="65" x2="36" y2="129"/><line class="e" x1="80" y1="65" x2="168" y2="129"/><line class="e" x1="168" y1="129" x2="124" y2="193"/><line class="e" x1="168" y1="129" x2="256" y2="193"/><line class="e" x1="256" y1="193" x2="212" y2="257"/><line class="e" x1="256" y1="193" x2="300" y2="257"/><circle class="n" cx="80" cy="65" r="17"/><text class="t" x="80" y="65" dy=".35em" text-anchor="middle">z</text><text class="ann" x="99" y="50">-2</text><circle class="n" cx="36" cy="129" r="17"/><text class="t" x="36" y="129" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="168" cy="129" r="17"/><text class="t" x="168" y="129" dy=".35em" text-anchor="middle">y</text><text class="ann" x="187" y="114">-1</text><circle class="n" cx="124" cy="193" r="17"/><text class="t" x="124" y="193" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="256" cy="193" r="17"/><text class="t" x="256" y="193" dy=".35em" text-anchor="middle">x</text><circle class="n" cx="212" cy="257" r="17"/><text class="t" x="212" y="257" dy=".35em" text-anchor="middle">T3</text><circle class="n" cx="300" cy="257" r="17"/><text class="t" x="300" y="257" dy=".35em" text-anchor="middle">T4</text><text class="lbl" x="370" y="22">after</text><line class="e" x1="524" y1="65" x2="436" y2="129"/><line class="e" x1="524" y1="65" x2="612" y2="129"/><line class="e" x1="436" y1="129" x2="392" y2="193"/><line class="e" x1="436" y1="129" x2="480" y2="193"/><line class="e" x1="612" y1="129" x2="568" y2="193"/><line class="e" x1="612" y1="129" x2="656" y2="193"/><circle class="n" cx="524" cy="65" r="17"/><text class="t" x="524" y="65" dy=".35em" text-anchor="middle">y</text><text class="ann" x="543" y="50">0</text><circle class="n" cx="436" cy="129" r="17"/><text class="t" x="436" y="129" dy=".35em" text-anchor="middle">z</text><text class="ann" x="455" y="114">0</text><circle class="n" cx="392" cy="193" r="17"/><text class="t" x="392" y="193" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="480" cy="193" r="17"/><text class="t" x="480" y="193" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="612" cy="129" r="17"/><text class="t" x="612" y="129" dy=".35em" text-anchor="middle">x</text><circle class="n" cx="568" cy="193" r="17"/><text class="t" x="568" y="193" dy=".35em" text-anchor="middle">T3</text><circle class="n" cx="656" cy="193" r="17"/><text class="t" x="656" y="193" dy=".35em" text-anchor="middle">T4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">RR: left rotation at z</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-11" viewBox="0 0 716 288" width="716" height="288" role="img" aria-label="LR: x rises"><style>#dsfig-u3-11 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-11 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-11 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-11 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-11 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-11 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-11 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-11 .t{fill:#16181D;font-weight:500}#dsfig-u3-11 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-11 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-11 .dot{fill:#16181D}#dsfig-u3-11 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-11 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-11 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-11 .ah{fill:#454C5A}#dsfig-u3-11 .ah.hi{fill:#2340B8}#dsfig-u3-11 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-11 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-11 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-11 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-11 .e{stroke:#B1B7C3}html.dark #dsfig-u3-11 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-11 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-11 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-11 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-11 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-11 .t{fill:#E6E8ED}html.dark #dsfig-u3-11 .t.inv{fill:#0F1115}html.dark #dsfig-u3-11 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-11 .dot{fill:#E6E8ED}html.dark #dsfig-u3-11 .ann{fill:#8FA3FF}html.dark #dsfig-u3-11 .lbl{fill:#858D9C}html.dark #dsfig-u3-11 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-11 .ah{fill:#B1B7C3}html.dark #dsfig-u3-11 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-11 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-11 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-11 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah24" 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="ahh24" 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><text class="lbl" x="14" y="22">LR before</text><line class="e" x1="256" y1="65" x2="80" y2="129"/><line class="e" x1="256" y1="65" x2="300" y2="129"/><line class="e" x1="80" y1="129" x2="36" y2="193"/><line class="e" x1="80" y1="129" x2="168" y2="193"/><line class="e" x1="168" y1="193" x2="124" y2="257"/><line class="e" x1="168" y1="193" x2="212" y2="257"/><circle class="n" cx="256" cy="65" r="17"/><text class="t" x="256" y="65" dy=".35em" text-anchor="middle">z</text><text class="ann" x="275" y="50">+2</text><circle class="n" cx="80" cy="129" r="17"/><text class="t" x="80" y="129" dy=".35em" text-anchor="middle">y</text><text class="ann" x="99" y="114">-1</text><circle class="n" cx="36" cy="193" r="17"/><text class="t" x="36" y="193" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="168" cy="193" r="17"/><text class="t" x="168" y="193" dy=".35em" text-anchor="middle">x</text><circle class="n" cx="124" cy="257" r="17"/><text class="t" x="124" y="257" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="212" cy="257" r="17"/><text class="t" x="212" y="257" dy=".35em" text-anchor="middle">T3</text><circle class="n" cx="300" cy="129" r="17"/><text class="t" x="300" y="129" dy=".35em" text-anchor="middle">T4</text><text class="lbl" x="370" y="22">after</text><line class="e" x1="524" y1="65" x2="436" y2="129"/><line class="e" x1="524" y1="65" x2="612" y2="129"/><line class="e" x1="436" y1="129" x2="392" y2="193"/><line class="e" x1="436" y1="129" x2="480" y2="193"/><line class="e" x1="612" y1="129" x2="568" y2="193"/><line class="e" x1="612" y1="129" x2="656" y2="193"/><circle class="n" cx="524" cy="65" r="17"/><text class="t" x="524" y="65" dy=".35em" text-anchor="middle">x</text><text class="ann" x="543" y="50">0</text><circle class="n" cx="436" cy="129" r="17"/><text class="t" x="436" y="129" dy=".35em" text-anchor="middle">y</text><circle class="n" cx="392" cy="193" r="17"/><text class="t" x="392" y="193" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="480" cy="193" r="17"/><text class="t" x="480" y="193" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="612" cy="129" r="17"/><text class="t" x="612" y="129" dy=".35em" text-anchor="middle">z</text><circle class="n" cx="568" cy="193" r="17"/><text class="t" x="568" y="193" dy=".35em" text-anchor="middle">T3</text><circle class="n" cx="656" cy="193" r="17"/><text class="t" x="656" y="193" dy=".35em" text-anchor="middle">T4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">LR: x rises</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-12" viewBox="0 0 716 288" width="716" height="288" role="img" aria-label="RL: x rises"><style>#dsfig-u3-12 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-12 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-12 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-12 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-12 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-12 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-12 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-12 .t{fill:#16181D;font-weight:500}#dsfig-u3-12 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-12 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-12 .dot{fill:#16181D}#dsfig-u3-12 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-12 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-12 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-12 .ah{fill:#454C5A}#dsfig-u3-12 .ah.hi{fill:#2340B8}#dsfig-u3-12 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-12 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-12 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-12 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-12 .e{stroke:#B1B7C3}html.dark #dsfig-u3-12 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-12 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-12 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-12 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-12 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-12 .t{fill:#E6E8ED}html.dark #dsfig-u3-12 .t.inv{fill:#0F1115}html.dark #dsfig-u3-12 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-12 .dot{fill:#E6E8ED}html.dark #dsfig-u3-12 .ann{fill:#8FA3FF}html.dark #dsfig-u3-12 .lbl{fill:#858D9C}html.dark #dsfig-u3-12 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-12 .ah{fill:#B1B7C3}html.dark #dsfig-u3-12 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-12 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-12 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-12 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah25" 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="ahh25" 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><text class="lbl" x="14" y="22">RL before</text><line class="e" x1="80" y1="65" x2="36" y2="129"/><line class="e" x1="80" y1="65" x2="256" y2="129"/><line class="e" x1="256" y1="129" x2="168" y2="193"/><line class="e" x1="256" y1="129" x2="300" y2="193"/><line class="e" x1="168" y1="193" x2="124" y2="257"/><line class="e" x1="168" y1="193" x2="212" y2="257"/><circle class="n" cx="80" cy="65" r="17"/><text class="t" x="80" y="65" dy=".35em" text-anchor="middle">z</text><text class="ann" x="99" y="50">-2</text><circle class="n" cx="36" cy="129" r="17"/><text class="t" x="36" y="129" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="256" cy="129" r="17"/><text class="t" x="256" y="129" dy=".35em" text-anchor="middle">y</text><text class="ann" x="275" y="114">+1</text><circle class="n" cx="168" cy="193" r="17"/><text class="t" x="168" y="193" dy=".35em" text-anchor="middle">x</text><circle class="n" cx="124" cy="257" r="17"/><text class="t" x="124" y="257" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="212" cy="257" r="17"/><text class="t" x="212" y="257" dy=".35em" text-anchor="middle">T3</text><circle class="n" cx="300" cy="193" r="17"/><text class="t" x="300" y="193" dy=".35em" text-anchor="middle">T4</text><text class="lbl" x="370" y="22">after</text><line class="e" x1="524" y1="65" x2="436" y2="129"/><line class="e" x1="524" y1="65" x2="612" y2="129"/><line class="e" x1="436" y1="129" x2="392" y2="193"/><line class="e" x1="436" y1="129" x2="480" y2="193"/><line class="e" x1="612" y1="129" x2="568" y2="193"/><line class="e" x1="612" y1="129" x2="656" y2="193"/><circle class="n" cx="524" cy="65" r="17"/><text class="t" x="524" y="65" dy=".35em" text-anchor="middle">x</text><text class="ann" x="543" y="50">0</text><circle class="n" cx="436" cy="129" r="17"/><text class="t" x="436" y="129" dy=".35em" text-anchor="middle">z</text><circle class="n" cx="392" cy="193" r="17"/><text class="t" x="392" y="193" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="480" cy="193" r="17"/><text class="t" x="480" y="193" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="612" cy="129" r="17"/><text class="t" x="612" y="129" dy=".35em" text-anchor="middle">y</text><circle class="n" cx="568" cy="193" r="17"/><text class="t" x="568" y="193" dy=".35em" text-anchor="middle">T3</text><circle class="n" cx="656" cy="193" r="17"/><text class="t" x="656" y="193" dy=".35em" text-anchor="middle">T4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">RL: x rises</figcaption></figure>

BF update. Recompute $h=1+\max(h_L,h_R)$ bottom-up; an insertion rotation leaves the new root with BF 0 and the old height, but after deletion case R0 (L0) the new root has BF -1 (+1).

Example (Nov 2022 to Jun 2024). Insert 48, 25, 10, 5, 7, 3, 28, 20, 8, 16 (superscripts are BFs):

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-13" viewBox="0 0 364 224" width="364" height="224" role="img" aria-label="Insert 48, 25, 10: LL at 48"><style>#dsfig-u3-13 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-13 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-13 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-13 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-13 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-13 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-13 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-13 .t{fill:#16181D;font-weight:500}#dsfig-u3-13 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-13 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-13 .dot{fill:#16181D}#dsfig-u3-13 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-13 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-13 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-13 .ah{fill:#454C5A}#dsfig-u3-13 .ah.hi{fill:#2340B8}#dsfig-u3-13 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-13 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-13 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-13 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-13 .e{stroke:#B1B7C3}html.dark #dsfig-u3-13 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-13 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-13 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-13 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-13 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-13 .t{fill:#E6E8ED}html.dark #dsfig-u3-13 .t.inv{fill:#0F1115}html.dark #dsfig-u3-13 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-13 .dot{fill:#E6E8ED}html.dark #dsfig-u3-13 .ann{fill:#8FA3FF}html.dark #dsfig-u3-13 .lbl{fill:#858D9C}html.dark #dsfig-u3-13 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-13 .ah{fill:#B1B7C3}html.dark #dsfig-u3-13 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-13 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-13 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-13 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah26" 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="ahh26" 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><text class="lbl" x="14" y="22">before</text><line class="e" x1="124" y1="65" x2="80" y2="129"/><line class="e" x1="80" y1="129" x2="36" y2="193"/><circle class="n" cx="124" cy="65" r="17"/><text class="t" x="124" y="65" dy=".35em" text-anchor="middle">48</text><text class="ann" x="143" y="50">+2</text><circle class="n" cx="80" cy="129" r="17"/><text class="t" x="80" y="129" dy=".35em" text-anchor="middle">25</text><text class="ann" x="99" y="114">+1</text><circle class="n" cx="36" cy="193" r="17"/><text class="t" x="36" y="193" dy=".35em" text-anchor="middle">10</text><text class="ann" x="55" y="178">0</text><text class="lbl" x="194" y="22">after</text><line class="e" x1="260" y1="65" x2="216" y2="129"/><line class="e" x1="260" y1="65" x2="304" y2="129"/><circle class="n" cx="260" cy="65" r="17"/><text class="t" x="260" y="65" dy=".35em" text-anchor="middle">25</text><text class="ann" x="279" y="50">0</text><circle class="n" cx="216" cy="129" r="17"/><text class="t" x="216" y="129" dy=".35em" text-anchor="middle">10</text><text class="ann" x="235" y="114">0</text><circle class="n" cx="304" cy="129" r="17"/><text class="t" x="304" y="129" dy=".35em" text-anchor="middle">48</text><text class="ann" x="323" y="114">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Insert 48, 25, 10: LL at 48</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-14" viewBox="0 0 540 288" width="540" height="288" role="img" aria-label="Insert 5, 7: LR at 10"><style>#dsfig-u3-14 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-14 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-14 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-14 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-14 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-14 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-14 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-14 .t{fill:#16181D;font-weight:500}#dsfig-u3-14 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-14 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-14 .dot{fill:#16181D}#dsfig-u3-14 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-14 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-14 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-14 .ah{fill:#454C5A}#dsfig-u3-14 .ah.hi{fill:#2340B8}#dsfig-u3-14 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-14 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-14 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-14 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-14 .e{stroke:#B1B7C3}html.dark #dsfig-u3-14 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-14 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-14 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-14 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-14 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-14 .t{fill:#E6E8ED}html.dark #dsfig-u3-14 .t.inv{fill:#0F1115}html.dark #dsfig-u3-14 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-14 .dot{fill:#E6E8ED}html.dark #dsfig-u3-14 .ann{fill:#8FA3FF}html.dark #dsfig-u3-14 .lbl{fill:#858D9C}html.dark #dsfig-u3-14 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-14 .ah{fill:#B1B7C3}html.dark #dsfig-u3-14 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-14 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-14 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-14 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah27" 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="ahh27" 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><text class="lbl" x="14" y="22">before</text><line class="e" x1="168" y1="65" x2="124" y2="129"/><line class="e" x1="168" y1="65" x2="212" y2="129"/><line class="e" x1="124" y1="129" x2="36" y2="193"/><line class="e" x1="36" y1="193" x2="80" y2="257"/><circle class="n" cx="168" cy="65" r="17"/><text class="t" x="168" y="65" dy=".35em" text-anchor="middle">25</text><text class="ann" x="187" y="50">+2</text><circle class="n" cx="124" cy="129" r="17"/><text class="t" x="124" y="129" dy=".35em" text-anchor="middle">10</text><text class="ann" x="143" y="114">+2</text><circle class="n" cx="36" cy="193" r="17"/><text class="t" x="36" y="193" dy=".35em" text-anchor="middle">5</text><text class="ann" x="55" y="178">-1</text><circle class="n" cx="80" cy="257" r="17"/><text class="t" x="80" y="257" dy=".35em" text-anchor="middle">7</text><text class="ann" x="99" y="242">0</text><circle class="n" cx="212" cy="129" r="17"/><text class="t" x="212" y="129" dy=".35em" text-anchor="middle">48</text><text class="ann" x="231" y="114">0</text><text class="lbl" x="282" y="22">after</text><line class="e" x1="436" y1="65" x2="348" y2="129"/><line class="e" x1="436" y1="65" x2="480" y2="129"/><line class="e" x1="348" y1="129" x2="304" y2="193"/><line class="e" x1="348" y1="129" x2="392" y2="193"/><circle class="n" cx="436" cy="65" r="17"/><text class="t" x="436" y="65" dy=".35em" text-anchor="middle">25</text><text class="ann" x="455" y="50">+1</text><circle class="n" cx="348" cy="129" r="17"/><text class="t" x="348" y="129" dy=".35em" text-anchor="middle">7</text><text class="ann" x="367" y="114">0</text><circle class="n" cx="304" cy="193" r="17"/><text class="t" x="304" y="193" dy=".35em" text-anchor="middle">5</text><text class="ann" x="323" y="178">0</text><circle class="n" cx="392" cy="193" r="17"/><text class="t" x="392" y="193" dy=".35em" text-anchor="middle">10</text><text class="ann" x="411" y="178">0</text><circle class="n" cx="480" cy="129" r="17"/><text class="t" x="480" y="129" dy=".35em" text-anchor="middle">48</text><text class="ann" x="499" y="114">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Insert 5, 7: LR at 10</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-15" viewBox="0 0 628 288" width="628" height="288" role="img" aria-label="Insert 3: LL at 25 (28, 20, 8 need none)"><style>#dsfig-u3-15 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-15 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-15 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-15 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-15 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-15 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-15 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-15 .t{fill:#16181D;font-weight:500}#dsfig-u3-15 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-15 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-15 .dot{fill:#16181D}#dsfig-u3-15 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-15 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-15 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-15 .ah{fill:#454C5A}#dsfig-u3-15 .ah.hi{fill:#2340B8}#dsfig-u3-15 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-15 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-15 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-15 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-15 .e{stroke:#B1B7C3}html.dark #dsfig-u3-15 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-15 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-15 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-15 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-15 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-15 .t{fill:#E6E8ED}html.dark #dsfig-u3-15 .t.inv{fill:#0F1115}html.dark #dsfig-u3-15 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-15 .dot{fill:#E6E8ED}html.dark #dsfig-u3-15 .ann{fill:#8FA3FF}html.dark #dsfig-u3-15 .lbl{fill:#858D9C}html.dark #dsfig-u3-15 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-15 .ah{fill:#B1B7C3}html.dark #dsfig-u3-15 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-15 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-15 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-15 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah28" 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="ahh28" 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><text class="lbl" x="14" y="22">before</text><line class="e" x1="212" y1="65" x2="124" y2="129"/><line class="e" x1="212" y1="65" x2="256" y2="129"/><line class="e" x1="124" y1="129" x2="80" y2="193"/><line class="e" x1="124" y1="129" x2="168" y2="193"/><line class="e" x1="80" y1="193" x2="36" y2="257"/><circle class="n" cx="212" cy="65" r="17"/><text class="t" x="212" y="65" dy=".35em" text-anchor="middle">25</text><text class="ann" x="231" y="50">+2</text><circle class="n" cx="124" cy="129" r="17"/><text class="t" x="124" y="129" dy=".35em" text-anchor="middle">7</text><text class="ann" x="143" y="114">+1</text><circle class="n" cx="80" cy="193" r="17"/><text class="t" x="80" y="193" dy=".35em" text-anchor="middle">5</text><text class="ann" x="99" y="178">+1</text><circle class="n" cx="36" cy="257" r="17"/><text class="t" x="36" y="257" dy=".35em" text-anchor="middle">3</text><text class="ann" x="55" y="242">0</text><circle class="n" cx="168" cy="193" r="17"/><text class="t" x="168" y="193" dy=".35em" text-anchor="middle">10</text><text class="ann" x="187" y="178">0</text><circle class="n" cx="256" cy="129" r="17"/><text class="t" x="256" y="129" dy=".35em" text-anchor="middle">48</text><text class="ann" x="275" y="114">0</text><text class="lbl" x="326" y="22">after</text><line class="e" x1="436" y1="65" x2="392" y2="129"/><line class="e" x1="436" y1="65" x2="524" y2="129"/><line class="e" x1="392" y1="129" x2="348" y2="193"/><line class="e" x1="524" y1="129" x2="480" y2="193"/><line class="e" x1="524" y1="129" x2="568" y2="193"/><circle class="n" cx="436" cy="65" r="17"/><text class="t" x="436" y="65" dy=".35em" text-anchor="middle">7</text><text class="ann" x="455" y="50">0</text><circle class="n" cx="392" cy="129" r="17"/><text class="t" x="392" y="129" dy=".35em" text-anchor="middle">5</text><text class="ann" x="411" y="114">+1</text><circle class="n" cx="348" cy="193" r="17"/><text class="t" x="348" y="193" dy=".35em" text-anchor="middle">3</text><text class="ann" x="367" y="178">0</text><circle class="n" cx="524" cy="129" r="17"/><text class="t" x="524" y="129" dy=".35em" text-anchor="middle">25</text><text class="ann" x="543" y="114">0</text><circle class="n" cx="480" cy="193" r="17"/><text class="t" x="480" y="193" dy=".35em" text-anchor="middle">10</text><text class="ann" x="499" y="178">0</text><circle class="n" cx="568" cy="193" r="17"/><text class="t" x="568" y="193" dy=".35em" text-anchor="middle">48</text><text class="ann" x="587" y="178">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Insert 3: LL at 25 (28, 20, 8 need none)</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-16" viewBox="0 0 1468 352" width="1468" height="352" role="img" aria-label="Insert 16: RL at 7, right at 25 (middle) then left at 7"><style>#dsfig-u3-16 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-16 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-16 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-16 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-16 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-16 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-16 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-16 .t{fill:#16181D;font-weight:500}#dsfig-u3-16 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-16 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-16 .dot{fill:#16181D}#dsfig-u3-16 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-16 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-16 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-16 .ah{fill:#454C5A}#dsfig-u3-16 .ah.hi{fill:#2340B8}#dsfig-u3-16 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-16 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-16 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-16 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-16 .e{stroke:#B1B7C3}html.dark #dsfig-u3-16 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-16 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-16 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-16 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-16 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-16 .t{fill:#E6E8ED}html.dark #dsfig-u3-16 .t.inv{fill:#0F1115}html.dark #dsfig-u3-16 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-16 .dot{fill:#E6E8ED}html.dark #dsfig-u3-16 .ann{fill:#8FA3FF}html.dark #dsfig-u3-16 .lbl{fill:#858D9C}html.dark #dsfig-u3-16 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-16 .ah{fill:#B1B7C3}html.dark #dsfig-u3-16 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-16 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-16 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-16 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah29" 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="ahh29" 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><text class="lbl" x="14" y="22">before</text><line class="e" x1="124" y1="65" x2="80" y2="129"/><line class="e" x1="124" y1="65" x2="344" y2="129"/><line class="e" x1="80" y1="129" x2="36" y2="193"/><line class="e" x1="344" y1="129" x2="212" y2="193"/><line class="e" x1="344" y1="129" x2="432" y2="193"/><line class="e" x1="212" y1="193" x2="168" y2="257"/><line class="e" x1="212" y1="193" x2="300" y2="257"/><line class="e" x1="300" y1="257" x2="256" y2="321"/><line class="e" x1="432" y1="193" x2="388" y2="257"/><circle class="n" cx="124" cy="65" r="17"/><text class="t" x="124" y="65" dy=".35em" text-anchor="middle">7</text><text class="ann" x="143" y="50">-2</text><circle class="n" cx="80" cy="129" r="17"/><text class="t" x="80" y="129" dy=".35em" text-anchor="middle">5</text><text class="ann" x="99" y="114">+1</text><circle class="n" cx="36" cy="193" r="17"/><text class="t" x="36" y="193" dy=".35em" text-anchor="middle">3</text><text class="ann" x="55" y="178">0</text><circle class="n" cx="344" cy="129" r="17"/><text class="t" x="344" y="129" dy=".35em" text-anchor="middle">25</text><text class="ann" x="363" y="114">+1</text><circle class="n" cx="212" cy="193" r="17"/><text class="t" x="212" y="193" dy=".35em" text-anchor="middle">10</text><text class="ann" x="231" y="178">-1</text><circle class="n" cx="168" cy="257" r="17"/><text class="t" x="168" y="257" dy=".35em" text-anchor="middle">8</text><text class="ann" x="187" y="242">0</text><circle class="n" cx="300" cy="257" r="17"/><text class="t" x="300" y="257" dy=".35em" text-anchor="middle">20</text><text class="ann" x="319" y="242">+1</text><circle class="n" cx="256" cy="321" r="17"/><text class="t" x="256" y="321" dy=".35em" text-anchor="middle">16</text><text class="ann" x="275" y="306">0</text><circle class="n" cx="432" cy="193" r="17"/><text class="t" x="432" y="193" dy=".35em" text-anchor="middle">48</text><text class="ann" x="451" y="178">+1</text><circle class="n" cx="388" cy="257" r="17"/><text class="t" x="388" y="257" dy=".35em" text-anchor="middle">28</text><text class="ann" x="407" y="242">0</text><text class="lbl" x="502" y="22">middle</text><line class="e" x1="612" y1="65" x2="568" y2="129"/><line class="e" x1="612" y1="65" x2="700" y2="129"/><line class="e" x1="568" y1="129" x2="524" y2="193"/><line class="e" x1="700" y1="129" x2="656" y2="193"/><line class="e" x1="700" y1="129" x2="832" y2="193"/><line class="e" x1="832" y1="193" x2="788" y2="257"/><line class="e" x1="832" y1="193" x2="920" y2="257"/><line class="e" x1="788" y1="257" x2="744" y2="321"/><line class="e" x1="920" y1="257" x2="876" y2="321"/><circle class="n" cx="612" cy="65" r="17"/><text class="t" x="612" y="65" dy=".35em" text-anchor="middle">7</text><text class="ann" x="631" y="50">-2</text><circle class="n" cx="568" cy="129" r="17"/><text class="t" x="568" y="129" dy=".35em" text-anchor="middle">5</text><text class="ann" x="587" y="114">+1</text><circle class="n" cx="524" cy="193" r="17"/><text class="t" x="524" y="193" dy=".35em" text-anchor="middle">3</text><text class="ann" x="543" y="178">0</text><circle class="n" cx="700" cy="129" r="17"/><text class="t" x="700" y="129" dy=".35em" text-anchor="middle">10</text><text class="ann" x="719" y="114">-2</text><circle class="n" cx="656" cy="193" r="17"/><text class="t" x="656" y="193" dy=".35em" text-anchor="middle">8</text><text class="ann" x="675" y="178">0</text><circle class="n" cx="832" cy="193" r="17"/><text class="t" x="832" y="193" dy=".35em" text-anchor="middle">25</text><text class="ann" x="851" y="178">0</text><circle class="n" cx="788" cy="257" r="17"/><text class="t" x="788" y="257" dy=".35em" text-anchor="middle">20</text><text class="ann" x="807" y="242">+1</text><circle class="n" cx="744" cy="321" r="17"/><text class="t" x="744" y="321" dy=".35em" text-anchor="middle">16</text><text class="ann" x="763" y="306">0</text><circle class="n" cx="920" cy="257" r="17"/><text class="t" x="920" y="257" dy=".35em" text-anchor="middle">48</text><text class="ann" x="939" y="242">+1</text><circle class="n" cx="876" cy="321" r="17"/><text class="t" x="876" y="321" dy=".35em" text-anchor="middle">28</text><text class="ann" x="895" y="306">0</text><text class="lbl" x="990" y="22">final</text><line class="e" x1="1188" y1="65" x2="1100" y2="129"/><line class="e" x1="1188" y1="65" x2="1320" y2="129"/><line class="e" x1="1100" y1="129" x2="1056" y2="193"/><line class="e" x1="1100" y1="129" x2="1144" y2="193"/><line class="e" x1="1056" y1="193" x2="1012" y2="257"/><line class="e" x1="1320" y1="129" x2="1276" y2="193"/><line class="e" x1="1320" y1="129" x2="1408" y2="193"/><line class="e" x1="1276" y1="193" x2="1232" y2="257"/><line class="e" x1="1408" y1="193" x2="1364" y2="257"/><circle class="n" cx="1188" cy="65" r="17"/><text class="t" x="1188" y="65" dy=".35em" text-anchor="middle">10</text><text class="ann" x="1207" y="50">0</text><circle class="n" cx="1100" cy="129" r="17"/><text class="t" x="1100" y="129" dy=".35em" text-anchor="middle">7</text><text class="ann" x="1119" y="114">+1</text><circle class="n" cx="1056" cy="193" r="17"/><text class="t" x="1056" y="193" dy=".35em" text-anchor="middle">5</text><text class="ann" x="1075" y="178">+1</text><circle class="n" cx="1012" cy="257" r="17"/><text class="t" x="1012" y="257" dy=".35em" text-anchor="middle">3</text><text class="ann" x="1031" y="242">0</text><circle class="n" cx="1144" cy="193" r="17"/><text class="t" x="1144" y="193" dy=".35em" text-anchor="middle">8</text><text class="ann" x="1163" y="178">0</text><circle class="n" cx="1320" cy="129" r="17"/><text class="t" x="1320" y="129" dy=".35em" text-anchor="middle">25</text><text class="ann" x="1339" y="114">0</text><circle class="n" cx="1276" cy="193" r="17"/><text class="t" x="1276" y="193" dy=".35em" text-anchor="middle">20</text><text class="ann" x="1295" y="178">+1</text><circle class="n" cx="1232" cy="257" r="17"/><text class="t" x="1232" y="257" dy=".35em" text-anchor="middle">16</text><text class="ann" x="1251" y="242">0</text><circle class="n" cx="1408" cy="193" r="17"/><text class="t" x="1408" y="193" dy=".35em" text-anchor="middle">48</text><text class="ann" x="1427" y="178">+1</text><circle class="n" cx="1364" cy="257" r="17"/><text class="t" x="1364" y="257" dy=".35em" text-anchor="middle">28</text><text class="ann" x="1383" y="242">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Insert 16: RL at 7, right at 25 (middle) then left at 7</figcaption></figure>

Example (Nov 2022, Dec 2023, Jun 2024). Insert the 18 keys 485 to 35 in the given order. Each tree follows its key and any rotation, with all BFs; labels give the key, case and node that hit $\pm2$.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-17" viewBox="0 0 636 224" width="636" height="224" role="img" aria-label="485 to 745"><style>#dsfig-u3-17 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-17 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-17 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-17 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-17 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-17 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-17 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-17 .t{fill:#16181D;font-weight:500}#dsfig-u3-17 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-17 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-17 .dot{fill:#16181D}#dsfig-u3-17 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-17 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-17 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-17 .ah{fill:#454C5A}#dsfig-u3-17 .ah.hi{fill:#2340B8}#dsfig-u3-17 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-17 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-17 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-17 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-17 .e{stroke:#B1B7C3}html.dark #dsfig-u3-17 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-17 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-17 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-17 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-17 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-17 .t{fill:#E6E8ED}html.dark #dsfig-u3-17 .t.inv{fill:#0F1115}html.dark #dsfig-u3-17 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-17 .dot{fill:#E6E8ED}html.dark #dsfig-u3-17 .ann{fill:#8FA3FF}html.dark #dsfig-u3-17 .lbl{fill:#858D9C}html.dark #dsfig-u3-17 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-17 .ah{fill:#B1B7C3}html.dark #dsfig-u3-17 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-17 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-17 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-17 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah30" 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="ahh30" 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><text class="lbl" x="14" y="22">+485</text><circle class="n" cx="36" cy="65" r="17"/><text class="t" x="36" y="65" dy=".35em" text-anchor="middle">485</text><text class="ann" x="55" y="50">0</text><text class="lbl" x="106" y="22">+575</text><line class="e" x1="128" y1="65" x2="172" y2="129"/><circle class="n" cx="128" cy="65" r="17"/><text class="t" x="128" y="65" dy=".35em" text-anchor="middle">485</text><text class="ann" x="147" y="50">-1</text><circle class="n" cx="172" cy="129" r="17"/><text class="t" x="172" y="129" dy=".35em" text-anchor="middle">575</text><text class="ann" x="191" y="114">0</text><text class="lbl" x="242" y="22">+655 RR 485</text><line class="e" x1="308" y1="65" x2="264" y2="129"/><line class="e" x1="308" y1="65" x2="352" y2="129"/><circle class="n" cx="308" cy="65" r="17"/><text class="t" x="308" y="65" dy=".35em" text-anchor="middle">575</text><text class="ann" x="327" y="50">0</text><circle class="n" cx="264" cy="129" r="17"/><text class="t" x="264" y="129" dy=".35em" text-anchor="middle">485</text><text class="ann" x="283" y="114">0</text><circle class="n" cx="352" cy="129" r="17"/><text class="t" x="352" y="129" dy=".35em" text-anchor="middle">655</text><text class="ann" x="371" y="114">0</text><text class="lbl" x="422" y="22">+745</text><line class="e" x1="488" y1="65" x2="444" y2="129"/><line class="e" x1="488" y1="65" x2="532" y2="129"/><line class="e" x1="532" y1="129" x2="576" y2="193"/><circle class="n" cx="488" cy="65" r="17"/><text class="t" x="488" y="65" dy=".35em" text-anchor="middle">575</text><text class="ann" x="507" y="50">-1</text><circle class="n" cx="444" cy="129" r="17"/><text class="t" x="444" y="129" dy=".35em" text-anchor="middle">485</text><text class="ann" x="463" y="114">0</text><circle class="n" cx="532" cy="129" r="17"/><text class="t" x="532" y="129" dy=".35em" text-anchor="middle">655</text><text class="ann" x="551" y="114">-1</text><circle class="n" cx="576" cy="193" r="17"/><text class="t" x="576" y="193" dy=".35em" text-anchor="middle">745</text><text class="ann" x="595" y="178">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">485 to 745</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-18" viewBox="0 0 940 288" width="940" height="288" role="img" aria-label="830 to 100"><style>#dsfig-u3-18 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-18 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-18 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-18 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-18 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-18 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-18 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-18 .t{fill:#16181D;font-weight:500}#dsfig-u3-18 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-18 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-18 .dot{fill:#16181D}#dsfig-u3-18 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-18 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-18 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-18 .ah{fill:#454C5A}#dsfig-u3-18 .ah.hi{fill:#2340B8}#dsfig-u3-18 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-18 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-18 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-18 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-18 .e{stroke:#B1B7C3}html.dark #dsfig-u3-18 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-18 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-18 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-18 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-18 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-18 .t{fill:#E6E8ED}html.dark #dsfig-u3-18 .t.inv{fill:#0F1115}html.dark #dsfig-u3-18 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-18 .dot{fill:#E6E8ED}html.dark #dsfig-u3-18 .ann{fill:#8FA3FF}html.dark #dsfig-u3-18 .lbl{fill:#858D9C}html.dark #dsfig-u3-18 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-18 .ah{fill:#B1B7C3}html.dark #dsfig-u3-18 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-18 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-18 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-18 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah31" 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="ahh31" 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><text class="lbl" x="14" y="22">+830 RR 655</text><line class="e" x1="80" y1="65" x2="36" y2="129"/><line class="e" x1="80" y1="65" x2="168" y2="129"/><line class="e" x1="168" y1="129" x2="124" y2="193"/><line class="e" x1="168" y1="129" x2="212" y2="193"/><circle class="n" cx="80" cy="65" r="17"/><text class="t" x="80" y="65" dy=".35em" text-anchor="middle">575</text><text class="ann" x="99" y="50">-1</text><circle class="n" cx="36" cy="129" r="17"/><text class="t" x="36" y="129" dy=".35em" text-anchor="middle">485</text><text class="ann" x="55" y="114">0</text><circle class="n" cx="168" cy="129" r="17"/><text class="t" x="168" y="129" dy=".35em" text-anchor="middle">745</text><text class="ann" x="187" y="114">0</text><circle class="n" cx="124" cy="193" r="17"/><text class="t" x="124" y="193" dy=".35em" text-anchor="middle">655</text><text class="ann" x="143" y="178">0</text><circle class="n" cx="212" cy="193" r="17"/><text class="t" x="212" y="193" dy=".35em" text-anchor="middle">830</text><text class="ann" x="231" y="178">0</text><text class="lbl" x="282" y="22">+910 RR 575</text><line class="e" x1="436" y1="65" x2="348" y2="129"/><line class="e" x1="436" y1="65" x2="480" y2="129"/><line class="e" x1="348" y1="129" x2="304" y2="193"/><line class="e" x1="348" y1="129" x2="392" y2="193"/><line class="e" x1="480" y1="129" x2="524" y2="193"/><circle class="n" cx="436" cy="65" r="17"/><text class="t" x="436" y="65" dy=".35em" text-anchor="middle">745</text><text class="ann" x="455" y="50">0</text><circle class="n" cx="348" cy="129" r="17"/><text class="t" x="348" y="129" dy=".35em" text-anchor="middle">575</text><text class="ann" x="367" y="114">0</text><circle class="n" cx="304" cy="193" r="17"/><text class="t" x="304" y="193" dy=".35em" text-anchor="middle">485</text><text class="ann" x="323" y="178">0</text><circle class="n" cx="392" cy="193" r="17"/><text class="t" x="392" y="193" dy=".35em" text-anchor="middle">655</text><text class="ann" x="411" y="178">0</text><circle class="n" cx="480" cy="129" r="17"/><text class="t" x="480" y="129" dy=".35em" text-anchor="middle">830</text><text class="ann" x="499" y="114">-1</text><circle class="n" cx="524" cy="193" r="17"/><text class="t" x="524" y="193" dy=".35em" text-anchor="middle">910</text><text class="ann" x="543" y="178">0</text><text class="lbl" x="594" y="22">+100</text><line class="e" x1="792" y1="65" x2="704" y2="129"/><line class="e" x1="792" y1="65" x2="836" y2="129"/><line class="e" x1="704" y1="129" x2="660" y2="193"/><line class="e" x1="704" y1="129" x2="748" y2="193"/><line class="e" x1="660" y1="193" x2="616" y2="257"/><line class="e" x1="836" y1="129" x2="880" y2="193"/><circle class="n" cx="792" cy="65" r="17"/><text class="t" x="792" y="65" dy=".35em" text-anchor="middle">745</text><text class="ann" x="811" y="50">+1</text><circle class="n" cx="704" cy="129" r="17"/><text class="t" x="704" y="129" dy=".35em" text-anchor="middle">575</text><text class="ann" x="723" y="114">+1</text><circle class="n" cx="660" cy="193" r="17"/><text class="t" x="660" y="193" dy=".35em" text-anchor="middle">485</text><text class="ann" x="679" y="178">+1</text><circle class="n" cx="616" cy="257" r="17"/><text class="t" x="616" y="257" dy=".35em" text-anchor="middle">100</text><text class="ann" x="635" y="242">0</text><circle class="n" cx="748" cy="193" r="17"/><text class="t" x="748" y="193" dy=".35em" text-anchor="middle">655</text><text class="ann" x="767" y="178">0</text><circle class="n" cx="836" cy="129" r="17"/><text class="t" x="836" y="129" dy=".35em" text-anchor="middle">830</text><text class="ann" x="855" y="114">-1</text><circle class="n" cx="880" cy="193" r="17"/><text class="t" x="880" y="193" dy=".35em" text-anchor="middle">910</text><text class="ann" x="899" y="178">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">830 to 100</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-19" viewBox="0 0 1336 288" width="1336" height="288" role="img" aria-label="110 to 130"><style>#dsfig-u3-19 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-19 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-19 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-19 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-19 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-19 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-19 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-19 .t{fill:#16181D;font-weight:500}#dsfig-u3-19 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-19 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-19 .dot{fill:#16181D}#dsfig-u3-19 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-19 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-19 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-19 .ah{fill:#454C5A}#dsfig-u3-19 .ah.hi{fill:#2340B8}#dsfig-u3-19 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-19 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-19 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-19 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-19 .e{stroke:#B1B7C3}html.dark #dsfig-u3-19 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-19 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-19 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-19 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-19 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-19 .t{fill:#E6E8ED}html.dark #dsfig-u3-19 .t.inv{fill:#0F1115}html.dark #dsfig-u3-19 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-19 .dot{fill:#E6E8ED}html.dark #dsfig-u3-19 .ann{fill:#8FA3FF}html.dark #dsfig-u3-19 .lbl{fill:#858D9C}html.dark #dsfig-u3-19 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-19 .ah{fill:#B1B7C3}html.dark #dsfig-u3-19 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-19 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-19 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-19 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah32" 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="ahh32" 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><text class="lbl" x="14" y="22">+110 LR 485</text><line class="e" x1="256" y1="65" x2="168" y2="129"/><line class="e" x1="256" y1="65" x2="300" y2="129"/><line class="e" x1="168" y1="129" x2="80" y2="193"/><line class="e" x1="168" y1="129" x2="212" y2="193"/><line class="e" x1="80" y1="193" x2="36" y2="257"/><line class="e" x1="80" y1="193" x2="124" y2="257"/><line class="e" x1="300" y1="129" x2="344" y2="193"/><circle class="n" cx="256" cy="65" r="17"/><text class="t" x="256" y="65" dy=".35em" text-anchor="middle">745</text><text class="ann" x="275" y="50">+1</text><circle class="n" cx="168" cy="129" r="17"/><text class="t" x="168" y="129" dy=".35em" text-anchor="middle">575</text><text class="ann" x="187" y="114">+1</text><circle class="n" cx="80" cy="193" r="17"/><text class="t" x="80" y="193" dy=".35em" text-anchor="middle">110</text><text class="ann" x="99" y="178">0</text><circle class="n" cx="36" cy="257" r="17"/><text class="t" x="36" y="257" dy=".35em" text-anchor="middle">100</text><text class="ann" x="55" y="242">0</text><circle class="n" cx="124" cy="257" r="17"/><text class="t" x="124" y="257" dy=".35em" text-anchor="middle">485</text><text class="ann" x="143" y="242">0</text><circle class="n" cx="212" cy="193" r="17"/><text class="t" x="212" y="193" dy=".35em" text-anchor="middle">655</text><text class="ann" x="231" y="178">0</text><circle class="n" cx="300" cy="129" r="17"/><text class="t" x="300" y="129" dy=".35em" text-anchor="middle">830</text><text class="ann" x="319" y="114">-1</text><circle class="n" cx="344" cy="193" r="17"/><text class="t" x="344" y="193" dy=".35em" text-anchor="middle">910</text><text class="ann" x="363" y="178">0</text><text class="lbl" x="414" y="22">+520 LR 575</text><line class="e" x1="700" y1="65" x2="524" y2="129"/><line class="e" x1="700" y1="65" x2="744" y2="129"/><line class="e" x1="524" y1="129" x2="480" y2="193"/><line class="e" x1="524" y1="129" x2="612" y2="193"/><line class="e" x1="480" y1="193" x2="436" y2="257"/><line class="e" x1="612" y1="193" x2="568" y2="257"/><line class="e" x1="612" y1="193" x2="656" y2="257"/><line class="e" x1="744" y1="129" x2="788" y2="193"/><circle class="n" cx="700" cy="65" r="17"/><text class="t" x="700" y="65" dy=".35em" text-anchor="middle">745</text><text class="ann" x="719" y="50">+1</text><circle class="n" cx="524" cy="129" r="17"/><text class="t" x="524" y="129" dy=".35em" text-anchor="middle">485</text><text class="ann" x="543" y="114">0</text><circle class="n" cx="480" cy="193" r="17"/><text class="t" x="480" y="193" dy=".35em" text-anchor="middle">110</text><text class="ann" x="499" y="178">+1</text><circle class="n" cx="436" cy="257" r="17"/><text class="t" x="436" y="257" dy=".35em" text-anchor="middle">100</text><text class="ann" x="455" y="242">0</text><circle class="n" cx="612" cy="193" r="17"/><text class="t" x="612" y="193" dy=".35em" text-anchor="middle">575</text><text class="ann" x="631" y="178">0</text><circle class="n" cx="568" cy="257" r="17"/><text class="t" x="568" y="257" dy=".35em" text-anchor="middle">520</text><text class="ann" x="587" y="242">0</text><circle class="n" cx="656" cy="257" r="17"/><text class="t" x="656" y="257" dy=".35em" text-anchor="middle">655</text><text class="ann" x="675" y="242">0</text><circle class="n" cx="744" cy="129" r="17"/><text class="t" x="744" y="129" dy=".35em" text-anchor="middle">830</text><text class="ann" x="763" y="114">-1</text><circle class="n" cx="788" cy="193" r="17"/><text class="t" x="788" y="193" dy=".35em" text-anchor="middle">910</text><text class="ann" x="807" y="178">0</text><text class="lbl" x="858" y="22">+130</text><line class="e" x1="1188" y1="65" x2="1012" y2="129"/><line class="e" x1="1188" y1="65" x2="1232" y2="129"/><line class="e" x1="1012" y1="129" x2="924" y2="193"/><line class="e" x1="1012" y1="129" x2="1100" y2="193"/><line class="e" x1="924" y1="193" x2="880" y2="257"/><line class="e" x1="924" y1="193" x2="968" y2="257"/><line class="e" x1="1100" y1="193" x2="1056" y2="257"/><line class="e" x1="1100" y1="193" x2="1144" y2="257"/><line class="e" x1="1232" y1="129" x2="1276" y2="193"/><circle class="n" cx="1188" cy="65" r="17"/><text class="t" x="1188" y="65" dy=".35em" text-anchor="middle">745</text><text class="ann" x="1207" y="50">+1</text><circle class="n" cx="1012" cy="129" r="17"/><text class="t" x="1012" y="129" dy=".35em" text-anchor="middle">485</text><text class="ann" x="1031" y="114">0</text><circle class="n" cx="924" cy="193" r="17"/><text class="t" x="924" y="193" dy=".35em" text-anchor="middle">110</text><text class="ann" x="943" y="178">0</text><circle class="n" cx="880" cy="257" r="17"/><text class="t" x="880" y="257" dy=".35em" text-anchor="middle">100</text><text class="ann" x="899" y="242">0</text><circle class="n" cx="968" cy="257" r="17"/><text class="t" x="968" y="257" dy=".35em" text-anchor="middle">130</text><text class="ann" x="987" y="242">0</text><circle class="n" cx="1100" cy="193" r="17"/><text class="t" x="1100" y="193" dy=".35em" text-anchor="middle">575</text><text class="ann" x="1119" y="178">0</text><circle class="n" cx="1056" cy="257" r="17"/><text class="t" x="1056" y="257" dy=".35em" text-anchor="middle">520</text><text class="ann" x="1075" y="242">0</text><circle class="n" cx="1144" cy="257" r="17"/><text class="t" x="1144" y="257" dy=".35em" text-anchor="middle">655</text><text class="ann" x="1163" y="242">0</text><circle class="n" cx="1232" cy="129" r="17"/><text class="t" x="1232" y="129" dy=".35em" text-anchor="middle">830</text><text class="ann" x="1251" y="114">-1</text><circle class="n" cx="1276" cy="193" r="17"/><text class="t" x="1276" y="193" dy=".35em" text-anchor="middle">910</text><text class="ann" x="1295" y="178">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">110 to 130</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-20" viewBox="0 0 1112 288" width="1112" height="288" role="img" aria-label="340 and 450"><style>#dsfig-u3-20 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-20 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-20 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-20 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-20 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-20 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-20 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-20 .t{fill:#16181D;font-weight:500}#dsfig-u3-20 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-20 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-20 .dot{fill:#16181D}#dsfig-u3-20 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-20 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-20 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-20 .ah{fill:#454C5A}#dsfig-u3-20 .ah.hi{fill:#2340B8}#dsfig-u3-20 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-20 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-20 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-20 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-20 .e{stroke:#B1B7C3}html.dark #dsfig-u3-20 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-20 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-20 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-20 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-20 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-20 .t{fill:#E6E8ED}html.dark #dsfig-u3-20 .t.inv{fill:#0F1115}html.dark #dsfig-u3-20 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-20 .dot{fill:#E6E8ED}html.dark #dsfig-u3-20 .ann{fill:#8FA3FF}html.dark #dsfig-u3-20 .lbl{fill:#858D9C}html.dark #dsfig-u3-20 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-20 .ah{fill:#B1B7C3}html.dark #dsfig-u3-20 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-20 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-20 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-20 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah33" 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="ahh33" 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><text class="lbl" x="14" y="22">+340 LL 745</text><line class="e" x1="212" y1="65" x2="80" y2="129"/><line class="e" x1="212" y1="65" x2="388" y2="129"/><line class="e" x1="80" y1="129" x2="36" y2="193"/><line class="e" x1="80" y1="129" x2="124" y2="193"/><line class="e" x1="124" y1="193" x2="168" y2="257"/><line class="e" x1="388" y1="129" x2="300" y2="193"/><line class="e" x1="388" y1="129" x2="432" y2="193"/><line class="e" x1="300" y1="193" x2="256" y2="257"/><line class="e" x1="300" y1="193" x2="344" y2="257"/><line class="e" x1="432" y1="193" x2="476" y2="257"/><circle class="n" cx="212" cy="65" r="17"/><text class="t" x="212" y="65" dy=".35em" text-anchor="middle">485</text><text class="ann" x="231" y="50">0</text><circle class="n" cx="80" cy="129" r="17"/><text class="t" x="80" y="129" dy=".35em" text-anchor="middle">110</text><text class="ann" x="99" y="114">-1</text><circle class="n" cx="36" cy="193" r="17"/><text class="t" x="36" y="193" dy=".35em" text-anchor="middle">100</text><text class="ann" x="55" y="178">0</text><circle class="n" cx="124" cy="193" r="17"/><text class="t" x="124" y="193" dy=".35em" text-anchor="middle">130</text><text class="ann" x="143" y="178">-1</text><circle class="n" cx="168" cy="257" r="17"/><text class="t" x="168" y="257" dy=".35em" text-anchor="middle">340</text><text class="ann" x="187" y="242">0</text><circle class="n" cx="388" cy="129" r="17"/><text class="t" x="388" y="129" dy=".35em" text-anchor="middle">745</text><text class="ann" x="407" y="114">0</text><circle class="n" cx="300" cy="193" r="17"/><text class="t" x="300" y="193" dy=".35em" text-anchor="middle">575</text><text class="ann" x="319" y="178">0</text><circle class="n" cx="256" cy="257" r="17"/><text class="t" x="256" y="257" dy=".35em" text-anchor="middle">520</text><text class="ann" x="275" y="242">0</text><circle class="n" cx="344" cy="257" r="17"/><text class="t" x="344" y="257" dy=".35em" text-anchor="middle">655</text><text class="ann" x="363" y="242">0</text><circle class="n" cx="432" cy="193" r="17"/><text class="t" x="432" y="193" dy=".35em" text-anchor="middle">830</text><text class="ann" x="451" y="178">-1</text><circle class="n" cx="476" cy="257" r="17"/><text class="t" x="476" y="257" dy=".35em" text-anchor="middle">910</text><text class="ann" x="495" y="242">0</text><text class="lbl" x="546" y="22">+450 RR 130</text><line class="e" x1="788" y1="65" x2="612" y2="129"/><line class="e" x1="788" y1="65" x2="964" y2="129"/><line class="e" x1="612" y1="129" x2="568" y2="193"/><line class="e" x1="612" y1="129" x2="700" y2="193"/><line class="e" x1="700" y1="193" x2="656" y2="257"/><line class="e" x1="700" y1="193" x2="744" y2="257"/><line class="e" x1="964" y1="129" x2="876" y2="193"/><line class="e" x1="964" y1="129" x2="1008" y2="193"/><line class="e" x1="876" y1="193" x2="832" y2="257"/><line class="e" x1="876" y1="193" x2="920" y2="257"/><line class="e" x1="1008" y1="193" x2="1052" y2="257"/><circle class="n" cx="788" cy="65" r="17"/><text class="t" x="788" y="65" dy=".35em" text-anchor="middle">485</text><text class="ann" x="807" y="50">0</text><circle class="n" cx="612" cy="129" r="17"/><text class="t" x="612" y="129" dy=".35em" text-anchor="middle">110</text><text class="ann" x="631" y="114">-1</text><circle class="n" cx="568" cy="193" r="17"/><text class="t" x="568" y="193" dy=".35em" text-anchor="middle">100</text><text class="ann" x="587" y="178">0</text><circle class="n" cx="700" cy="193" r="17"/><text class="t" x="700" y="193" dy=".35em" text-anchor="middle">340</text><text class="ann" x="719" y="178">0</text><circle class="n" cx="656" cy="257" r="17"/><text class="t" x="656" y="257" dy=".35em" text-anchor="middle">130</text><text class="ann" x="675" y="242">0</text><circle class="n" cx="744" cy="257" r="17"/><text class="t" x="744" y="257" dy=".35em" text-anchor="middle">450</text><text class="ann" x="763" y="242">0</text><circle class="n" cx="964" cy="129" r="17"/><text class="t" x="964" y="129" dy=".35em" text-anchor="middle">745</text><text class="ann" x="983" y="114">0</text><circle class="n" cx="876" cy="193" r="17"/><text class="t" x="876" y="193" dy=".35em" text-anchor="middle">575</text><text class="ann" x="895" y="178">0</text><circle class="n" cx="832" cy="257" r="17"/><text class="t" x="832" y="257" dy=".35em" text-anchor="middle">520</text><text class="ann" x="851" y="242">0</text><circle class="n" cx="920" cy="257" r="17"/><text class="t" x="920" y="257" dy=".35em" text-anchor="middle">655</text><text class="ann" x="939" y="242">0</text><circle class="n" cx="1008" cy="193" r="17"/><text class="t" x="1008" y="193" dy=".35em" text-anchor="middle">830</text><text class="ann" x="1027" y="178">-1</text><circle class="n" cx="1052" cy="257" r="17"/><text class="t" x="1052" y="257" dy=".35em" text-anchor="middle">910</text><text class="ann" x="1071" y="242">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">340 and 450</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-21" viewBox="0 0 1288 352" width="1288" height="352" role="img" aria-label="365 and 525"><style>#dsfig-u3-21 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-21 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-21 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-21 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-21 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-21 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-21 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-21 .t{fill:#16181D;font-weight:500}#dsfig-u3-21 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-21 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-21 .dot{fill:#16181D}#dsfig-u3-21 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-21 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-21 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-21 .ah{fill:#454C5A}#dsfig-u3-21 .ah.hi{fill:#2340B8}#dsfig-u3-21 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-21 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-21 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-21 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-21 .e{stroke:#B1B7C3}html.dark #dsfig-u3-21 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-21 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-21 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-21 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-21 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-21 .t{fill:#E6E8ED}html.dark #dsfig-u3-21 .t.inv{fill:#0F1115}html.dark #dsfig-u3-21 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-21 .dot{fill:#E6E8ED}html.dark #dsfig-u3-21 .ann{fill:#8FA3FF}html.dark #dsfig-u3-21 .lbl{fill:#858D9C}html.dark #dsfig-u3-21 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-21 .ah{fill:#B1B7C3}html.dark #dsfig-u3-21 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-21 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-21 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-21 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah34" 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="ahh34" 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><text class="lbl" x="14" y="22">+365 RR 110</text><line class="e" x1="300" y1="65" x2="168" y2="129"/><line class="e" x1="300" y1="65" x2="476" y2="129"/><line class="e" x1="168" y1="129" x2="80" y2="193"/><line class="e" x1="168" y1="129" x2="256" y2="193"/><line class="e" x1="80" y1="193" x2="36" y2="257"/><line class="e" x1="80" y1="193" x2="124" y2="257"/><line class="e" x1="256" y1="193" x2="212" y2="257"/><line class="e" x1="476" y1="129" x2="388" y2="193"/><line class="e" x1="476" y1="129" x2="520" y2="193"/><line class="e" x1="388" y1="193" x2="344" y2="257"/><line class="e" x1="388" y1="193" x2="432" y2="257"/><line class="e" x1="520" y1="193" x2="564" y2="257"/><circle class="n" cx="300" cy="65" r="17"/><text class="t" x="300" y="65" dy=".35em" text-anchor="middle">485</text><text class="ann" x="319" y="50">0</text><circle class="n" cx="168" cy="129" r="17"/><text class="t" x="168" y="129" dy=".35em" text-anchor="middle">340</text><text class="ann" x="187" y="114">0</text><circle class="n" cx="80" cy="193" r="17"/><text class="t" x="80" y="193" dy=".35em" text-anchor="middle">110</text><text class="ann" x="99" y="178">0</text><circle class="n" cx="36" cy="257" r="17"/><text class="t" x="36" y="257" dy=".35em" text-anchor="middle">100</text><text class="ann" x="55" y="242">0</text><circle class="n" cx="124" cy="257" r="17"/><text class="t" x="124" y="257" dy=".35em" text-anchor="middle">130</text><text class="ann" x="143" y="242">0</text><circle class="n" cx="256" cy="193" r="17"/><text class="t" x="256" y="193" dy=".35em" text-anchor="middle">450</text><text class="ann" x="275" y="178">+1</text><circle class="n" cx="212" cy="257" r="17"/><text class="t" x="212" y="257" dy=".35em" text-anchor="middle">365</text><text class="ann" x="231" y="242">0</text><circle class="n" cx="476" cy="129" r="17"/><text class="t" x="476" y="129" dy=".35em" text-anchor="middle">745</text><text class="ann" x="495" y="114">0</text><circle class="n" cx="388" cy="193" r="17"/><text class="t" x="388" y="193" dy=".35em" text-anchor="middle">575</text><text class="ann" x="407" y="178">0</text><circle class="n" cx="344" cy="257" r="17"/><text class="t" x="344" y="257" dy=".35em" text-anchor="middle">520</text><text class="ann" x="363" y="242">0</text><circle class="n" cx="432" cy="257" r="17"/><text class="t" x="432" y="257" dy=".35em" text-anchor="middle">655</text><text class="ann" x="451" y="242">0</text><circle class="n" cx="520" cy="193" r="17"/><text class="t" x="520" y="193" dy=".35em" text-anchor="middle">830</text><text class="ann" x="539" y="178">-1</text><circle class="n" cx="564" cy="257" r="17"/><text class="t" x="564" y="257" dy=".35em" text-anchor="middle">910</text><text class="ann" x="583" y="242">0</text><text class="lbl" x="634" y="22">+525</text><line class="e" x1="920" y1="65" x2="788" y2="129"/><line class="e" x1="920" y1="65" x2="1140" y2="129"/><line class="e" x1="788" y1="129" x2="700" y2="193"/><line class="e" x1="788" y1="129" x2="876" y2="193"/><line class="e" x1="700" y1="193" x2="656" y2="257"/><line class="e" x1="700" y1="193" x2="744" y2="257"/><line class="e" x1="876" y1="193" x2="832" y2="257"/><line class="e" x1="1140" y1="129" x2="1052" y2="193"/><line class="e" x1="1140" y1="129" x2="1184" y2="193"/><line class="e" x1="1052" y1="193" x2="964" y2="257"/><line class="e" x1="1052" y1="193" x2="1096" y2="257"/><line class="e" x1="964" y1="257" x2="1008" y2="321"/><line class="e" x1="1184" y1="193" x2="1228" y2="257"/><circle class="n" cx="920" cy="65" r="17"/><text class="t" x="920" y="65" dy=".35em" text-anchor="middle">485</text><text class="ann" x="939" y="50">-1</text><circle class="n" cx="788" cy="129" r="17"/><text class="t" x="788" y="129" dy=".35em" text-anchor="middle">340</text><text class="ann" x="807" y="114">0</text><circle class="n" cx="700" cy="193" r="17"/><text class="t" x="700" y="193" dy=".35em" text-anchor="middle">110</text><text class="ann" x="719" y="178">0</text><circle class="n" cx="656" cy="257" r="17"/><text class="t" x="656" y="257" dy=".35em" text-anchor="middle">100</text><text class="ann" x="675" y="242">0</text><circle class="n" cx="744" cy="257" r="17"/><text class="t" x="744" y="257" dy=".35em" text-anchor="middle">130</text><text class="ann" x="763" y="242">0</text><circle class="n" cx="876" cy="193" r="17"/><text class="t" x="876" y="193" dy=".35em" text-anchor="middle">450</text><text class="ann" x="895" y="178">+1</text><circle class="n" cx="832" cy="257" r="17"/><text class="t" x="832" y="257" dy=".35em" text-anchor="middle">365</text><text class="ann" x="851" y="242">0</text><circle class="n" cx="1140" cy="129" r="17"/><text class="t" x="1140" y="129" dy=".35em" text-anchor="middle">745</text><text class="ann" x="1159" y="114">+1</text><circle class="n" cx="1052" cy="193" r="17"/><text class="t" x="1052" y="193" dy=".35em" text-anchor="middle">575</text><text class="ann" x="1071" y="178">+1</text><circle class="n" cx="964" cy="257" r="17"/><text class="t" x="964" y="257" dy=".35em" text-anchor="middle">520</text><text class="ann" x="983" y="242">-1</text><circle class="n" cx="1008" cy="321" r="17"/><text class="t" x="1008" y="321" dy=".35em" text-anchor="middle">525</text><text class="ann" x="1027" y="306">0</text><circle class="n" cx="1096" cy="257" r="17"/><text class="t" x="1096" y="257" dy=".35em" text-anchor="middle">655</text><text class="ann" x="1115" y="242">0</text><circle class="n" cx="1184" cy="193" r="17"/><text class="t" x="1184" y="193" dy=".35em" text-anchor="middle">830</text><text class="ann" x="1203" y="178">-1</text><circle class="n" cx="1228" cy="257" r="17"/><text class="t" x="1228" y="257" dy=".35em" text-anchor="middle">910</text><text class="ann" x="1247" y="242">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">365 and 525</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-22" viewBox="0 0 2260 352" width="2260" height="352" role="img" aria-label="204, 155, 130 (duplicate, ignored), 35: final tree"><style>#dsfig-u3-22 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-22 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-22 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-22 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-22 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-22 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-22 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-22 .t{fill:#16181D;font-weight:500}#dsfig-u3-22 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-22 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-22 .dot{fill:#16181D}#dsfig-u3-22 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-22 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-22 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-22 .ah{fill:#454C5A}#dsfig-u3-22 .ah.hi{fill:#2340B8}#dsfig-u3-22 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-22 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-22 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-22 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-22 .e{stroke:#B1B7C3}html.dark #dsfig-u3-22 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-22 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-22 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-22 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-22 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-22 .t{fill:#E6E8ED}html.dark #dsfig-u3-22 .t.inv{fill:#0F1115}html.dark #dsfig-u3-22 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-22 .dot{fill:#E6E8ED}html.dark #dsfig-u3-22 .ann{fill:#8FA3FF}html.dark #dsfig-u3-22 .lbl{fill:#858D9C}html.dark #dsfig-u3-22 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-22 .ah{fill:#B1B7C3}html.dark #dsfig-u3-22 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-22 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-22 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-22 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah35" 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="ahh35" 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><text class="lbl" x="14" y="22">+204</text><line class="e" x1="344" y1="65" x2="212" y2="129"/><line class="e" x1="344" y1="65" x2="564" y2="129"/><line class="e" x1="212" y1="129" x2="80" y2="193"/><line class="e" x1="212" y1="129" x2="300" y2="193"/><line class="e" x1="80" y1="193" x2="36" y2="257"/><line class="e" x1="80" y1="193" x2="124" y2="257"/><line class="e" x1="124" y1="257" x2="168" y2="321"/><line class="e" x1="300" y1="193" x2="256" y2="257"/><line class="e" x1="564" y1="129" x2="476" y2="193"/><line class="e" x1="564" y1="129" x2="608" y2="193"/><line class="e" x1="476" y1="193" x2="388" y2="257"/><line class="e" x1="476" y1="193" x2="520" y2="257"/><line class="e" x1="388" y1="257" x2="432" y2="321"/><line class="e" x1="608" y1="193" x2="652" y2="257"/><circle class="n" cx="344" cy="65" r="17"/><text class="t" x="344" y="65" dy=".35em" text-anchor="middle">485</text><text class="ann" x="363" y="50">0</text><circle class="n" cx="212" cy="129" r="17"/><text class="t" x="212" y="129" dy=".35em" text-anchor="middle">340</text><text class="ann" x="231" y="114">+1</text><circle class="n" cx="80" cy="193" r="17"/><text class="t" x="80" y="193" dy=".35em" text-anchor="middle">110</text><text class="ann" x="99" y="178">-1</text><circle class="n" cx="36" cy="257" r="17"/><text class="t" x="36" y="257" dy=".35em" text-anchor="middle">100</text><text class="ann" x="55" y="242">0</text><circle class="n" cx="124" cy="257" r="17"/><text class="t" x="124" y="257" dy=".35em" text-anchor="middle">130</text><text class="ann" x="143" y="242">-1</text><circle class="n" cx="168" cy="321" r="17"/><text class="t" x="168" y="321" dy=".35em" text-anchor="middle">204</text><text class="ann" x="187" y="306">0</text><circle class="n" cx="300" cy="193" r="17"/><text class="t" x="300" y="193" dy=".35em" text-anchor="middle">450</text><text class="ann" x="319" y="178">+1</text><circle class="n" cx="256" cy="257" r="17"/><text class="t" x="256" y="257" dy=".35em" text-anchor="middle">365</text><text class="ann" x="275" y="242">0</text><circle class="n" cx="564" cy="129" r="17"/><text class="t" x="564" y="129" dy=".35em" text-anchor="middle">745</text><text class="ann" x="583" y="114">+1</text><circle class="n" cx="476" cy="193" r="17"/><text class="t" x="476" y="193" dy=".35em" text-anchor="middle">575</text><text class="ann" x="495" y="178">+1</text><circle class="n" cx="388" cy="257" r="17"/><text class="t" x="388" y="257" dy=".35em" text-anchor="middle">520</text><text class="ann" x="407" y="242">-1</text><circle class="n" cx="432" cy="321" r="17"/><text class="t" x="432" y="321" dy=".35em" text-anchor="middle">525</text><text class="ann" x="451" y="306">0</text><circle class="n" cx="520" cy="257" r="17"/><text class="t" x="520" y="257" dy=".35em" text-anchor="middle">655</text><text class="ann" x="539" y="242">0</text><circle class="n" cx="608" cy="193" r="17"/><text class="t" x="608" y="193" dy=".35em" text-anchor="middle">830</text><text class="ann" x="627" y="178">-1</text><circle class="n" cx="652" cy="257" r="17"/><text class="t" x="652" y="257" dy=".35em" text-anchor="middle">910</text><text class="ann" x="671" y="242">0</text><text class="lbl" x="722" y="22">+155 RL 130</text><line class="e" x1="1096" y1="65" x2="964" y2="129"/><line class="e" x1="1096" y1="65" x2="1316" y2="129"/><line class="e" x1="964" y1="129" x2="788" y2="193"/><line class="e" x1="964" y1="129" x2="1052" y2="193"/><line class="e" x1="788" y1="193" x2="744" y2="257"/><line class="e" x1="788" y1="193" x2="876" y2="257"/><line class="e" x1="876" y1="257" x2="832" y2="321"/><line class="e" x1="876" y1="257" x2="920" y2="321"/><line class="e" x1="1052" y1="193" x2="1008" y2="257"/><line class="e" x1="1316" y1="129" x2="1228" y2="193"/><line class="e" x1="1316" y1="129" x2="1360" y2="193"/><line class="e" x1="1228" y1="193" x2="1140" y2="257"/><line class="e" x1="1228" y1="193" x2="1272" y2="257"/><line class="e" x1="1140" y1="257" x2="1184" y2="321"/><line class="e" x1="1360" y1="193" x2="1404" y2="257"/><circle class="n" cx="1096" cy="65" r="17"/><text class="t" x="1096" y="65" dy=".35em" text-anchor="middle">485</text><text class="ann" x="1115" y="50">0</text><circle class="n" cx="964" cy="129" r="17"/><text class="t" x="964" y="129" dy=".35em" text-anchor="middle">340</text><text class="ann" x="983" y="114">+1</text><circle class="n" cx="788" cy="193" r="17"/><text class="t" x="788" y="193" dy=".35em" text-anchor="middle">110</text><text class="ann" x="807" y="178">-1</text><circle class="n" cx="744" cy="257" r="17"/><text class="t" x="744" y="257" dy=".35em" text-anchor="middle">100</text><text class="ann" x="763" y="242">0</text><circle class="n" cx="876" cy="257" r="17"/><text class="t" x="876" y="257" dy=".35em" text-anchor="middle">155</text><text class="ann" x="895" y="242">0</text><circle class="n" cx="832" cy="321" r="17"/><text class="t" x="832" y="321" dy=".35em" text-anchor="middle">130</text><text class="ann" x="851" y="306">0</text><circle class="n" cx="920" cy="321" r="17"/><text class="t" x="920" y="321" dy=".35em" text-anchor="middle">204</text><text class="ann" x="939" y="306">0</text><circle class="n" cx="1052" cy="193" r="17"/><text class="t" x="1052" y="193" dy=".35em" text-anchor="middle">450</text><text class="ann" x="1071" y="178">+1</text><circle class="n" cx="1008" cy="257" r="17"/><text class="t" x="1008" y="257" dy=".35em" text-anchor="middle">365</text><text class="ann" x="1027" y="242">0</text><circle class="n" cx="1316" cy="129" r="17"/><text class="t" x="1316" y="129" dy=".35em" text-anchor="middle">745</text><text class="ann" x="1335" y="114">+1</text><circle class="n" cx="1228" cy="193" r="17"/><text class="t" x="1228" y="193" dy=".35em" text-anchor="middle">575</text><text class="ann" x="1247" y="178">+1</text><circle class="n" cx="1140" cy="257" r="17"/><text class="t" x="1140" y="257" dy=".35em" text-anchor="middle">520</text><text class="ann" x="1159" y="242">-1</text><circle class="n" cx="1184" cy="321" r="17"/><text class="t" x="1184" y="321" dy=".35em" text-anchor="middle">525</text><text class="ann" x="1203" y="306">0</text><circle class="n" cx="1272" cy="257" r="17"/><text class="t" x="1272" y="257" dy=".35em" text-anchor="middle">655</text><text class="ann" x="1291" y="242">0</text><circle class="n" cx="1360" cy="193" r="17"/><text class="t" x="1360" y="193" dy=".35em" text-anchor="middle">830</text><text class="ann" x="1379" y="178">-1</text><circle class="n" cx="1404" cy="257" r="17"/><text class="t" x="1404" y="257" dy=".35em" text-anchor="middle">910</text><text class="ann" x="1423" y="242">0</text><text class="lbl" x="1474" y="22">+35</text><line class="e" x1="1892" y1="65" x2="1760" y2="129"/><line class="e" x1="1892" y1="65" x2="2112" y2="129"/><line class="e" x1="1760" y1="129" x2="1584" y2="193"/><line class="e" x1="1760" y1="129" x2="1848" y2="193"/><line class="e" x1="1584" y1="193" x2="1540" y2="257"/><line class="e" x1="1584" y1="193" x2="1672" y2="257"/><line class="e" x1="1540" y1="257" x2="1496" y2="321"/><line class="e" x1="1672" y1="257" x2="1628" y2="321"/><line class="e" x1="1672" y1="257" x2="1716" y2="321"/><line class="e" x1="1848" y1="193" x2="1804" y2="257"/><line class="e" x1="2112" y1="129" x2="2024" y2="193"/><line class="e" x1="2112" y1="129" x2="2156" y2="193"/><line class="e" x1="2024" y1="193" x2="1936" y2="257"/><line class="e" x1="2024" y1="193" x2="2068" y2="257"/><line class="e" x1="1936" y1="257" x2="1980" y2="321"/><line class="e" x1="2156" y1="193" x2="2200" y2="257"/><circle class="n" cx="1892" cy="65" r="17"/><text class="t" x="1892" y="65" dy=".35em" text-anchor="middle">485</text><text class="ann" x="1911" y="50">0</text><circle class="n" cx="1760" cy="129" r="17"/><text class="t" x="1760" y="129" dy=".35em" text-anchor="middle">340</text><text class="ann" x="1779" y="114">+1</text><circle class="n" cx="1584" cy="193" r="17"/><text class="t" x="1584" y="193" dy=".35em" text-anchor="middle">110</text><text class="ann" x="1603" y="178">0</text><circle class="n" cx="1540" cy="257" r="17"/><text class="t" x="1540" y="257" dy=".35em" text-anchor="middle">100</text><text class="ann" x="1559" y="242">+1</text><circle class="n" cx="1496" cy="321" r="17"/><text class="t" x="1496" y="321" dy=".35em" text-anchor="middle">35</text><text class="ann" x="1515" y="306">0</text><circle class="n" cx="1672" cy="257" r="17"/><text class="t" x="1672" y="257" dy=".35em" text-anchor="middle">155</text><text class="ann" x="1691" y="242">0</text><circle class="n" cx="1628" cy="321" r="17"/><text class="t" x="1628" y="321" dy=".35em" text-anchor="middle">130</text><text class="ann" x="1647" y="306">0</text><circle class="n" cx="1716" cy="321" r="17"/><text class="t" x="1716" y="321" dy=".35em" text-anchor="middle">204</text><text class="ann" x="1735" y="306">0</text><circle class="n" cx="1848" cy="193" r="17"/><text class="t" x="1848" y="193" dy=".35em" text-anchor="middle">450</text><text class="ann" x="1867" y="178">+1</text><circle class="n" cx="1804" cy="257" r="17"/><text class="t" x="1804" y="257" dy=".35em" text-anchor="middle">365</text><text class="ann" x="1823" y="242">0</text><circle class="n" cx="2112" cy="129" r="17"/><text class="t" x="2112" y="129" dy=".35em" text-anchor="middle">745</text><text class="ann" x="2131" y="114">+1</text><circle class="n" cx="2024" cy="193" r="17"/><text class="t" x="2024" y="193" dy=".35em" text-anchor="middle">575</text><text class="ann" x="2043" y="178">+1</text><circle class="n" cx="1936" cy="257" r="17"/><text class="t" x="1936" y="257" dy=".35em" text-anchor="middle">520</text><text class="ann" x="1955" y="242">-1</text><circle class="n" cx="1980" cy="321" r="17"/><text class="t" x="1980" y="321" dy=".35em" text-anchor="middle">525</text><text class="ann" x="1999" y="306">0</text><circle class="n" cx="2068" cy="257" r="17"/><text class="t" x="2068" y="257" dy=".35em" text-anchor="middle">655</text><text class="ann" x="2087" y="242">0</text><circle class="n" cx="2156" cy="193" r="17"/><text class="t" x="2156" y="193" dy=".35em" text-anchor="middle">830</text><text class="ann" x="2175" y="178">-1</text><circle class="n" cx="2200" cy="257" r="17"/><text class="t" x="2200" y="257" dy=".35em" text-anchor="middle">910</text><text class="ann" x="2219" y="242">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">204, 155, 130 (duplicate, ignored), 35: final tree</figcaption></figure>

Second variant: insert 14, 17, 11, 7, 53, 4, 13, 12, 8, 60, 19, 16, 20.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-23" viewBox="0 0 904 224" width="904" height="224" role="img" aria-label="14 to 53, no rotation"><style>#dsfig-u3-23 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-23 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-23 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-23 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-23 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-23 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-23 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-23 .t{fill:#16181D;font-weight:500}#dsfig-u3-23 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-23 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-23 .dot{fill:#16181D}#dsfig-u3-23 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-23 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-23 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-23 .ah{fill:#454C5A}#dsfig-u3-23 .ah.hi{fill:#2340B8}#dsfig-u3-23 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-23 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-23 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-23 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-23 .e{stroke:#B1B7C3}html.dark #dsfig-u3-23 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-23 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-23 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-23 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-23 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-23 .t{fill:#E6E8ED}html.dark #dsfig-u3-23 .t.inv{fill:#0F1115}html.dark #dsfig-u3-23 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-23 .dot{fill:#E6E8ED}html.dark #dsfig-u3-23 .ann{fill:#8FA3FF}html.dark #dsfig-u3-23 .lbl{fill:#858D9C}html.dark #dsfig-u3-23 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-23 .ah{fill:#B1B7C3}html.dark #dsfig-u3-23 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-23 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-23 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-23 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah36" 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="ahh36" 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><text class="lbl" x="14" y="22">+14</text><circle class="n" cx="36" cy="65" r="17"/><text class="t" x="36" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="55" y="50">0</text><text class="lbl" x="106" y="22">+17</text><line class="e" x1="128" y1="65" x2="172" y2="129"/><circle class="n" cx="128" cy="65" r="17"/><text class="t" x="128" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="147" y="50">-1</text><circle class="n" cx="172" cy="129" r="17"/><text class="t" x="172" y="129" dy=".35em" text-anchor="middle">17</text><text class="ann" x="191" y="114">0</text><text class="lbl" x="242" y="22">+11</text><line class="e" x1="308" y1="65" x2="264" y2="129"/><line class="e" x1="308" y1="65" x2="352" y2="129"/><circle class="n" cx="308" cy="65" r="17"/><text class="t" x="308" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="327" y="50">0</text><circle class="n" cx="264" cy="129" r="17"/><text class="t" x="264" y="129" dy=".35em" text-anchor="middle">11</text><text class="ann" x="283" y="114">0</text><circle class="n" cx="352" cy="129" r="17"/><text class="t" x="352" y="129" dy=".35em" text-anchor="middle">17</text><text class="ann" x="371" y="114">0</text><text class="lbl" x="422" y="22">+7</text><line class="e" x1="532" y1="65" x2="488" y2="129"/><line class="e" x1="532" y1="65" x2="576" y2="129"/><line class="e" x1="488" y1="129" x2="444" y2="193"/><circle class="n" cx="532" cy="65" r="17"/><text class="t" x="532" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="551" y="50">+1</text><circle class="n" cx="488" cy="129" r="17"/><text class="t" x="488" y="129" dy=".35em" text-anchor="middle">11</text><text class="ann" x="507" y="114">+1</text><circle class="n" cx="444" cy="193" r="17"/><text class="t" x="444" y="193" dy=".35em" text-anchor="middle">7</text><text class="ann" x="463" y="178">0</text><circle class="n" cx="576" cy="129" r="17"/><text class="t" x="576" y="129" dy=".35em" text-anchor="middle">17</text><text class="ann" x="595" y="114">0</text><text class="lbl" x="646" y="22">+53</text><line class="e" x1="756" y1="65" x2="712" y2="129"/><line class="e" x1="756" y1="65" x2="800" y2="129"/><line class="e" x1="712" y1="129" x2="668" y2="193"/><line class="e" x1="800" y1="129" x2="844" y2="193"/><circle class="n" cx="756" cy="65" r="17"/><text class="t" x="756" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="775" y="50">0</text><circle class="n" cx="712" cy="129" r="17"/><text class="t" x="712" y="129" dy=".35em" text-anchor="middle">11</text><text class="ann" x="731" y="114">+1</text><circle class="n" cx="668" cy="193" r="17"/><text class="t" x="668" y="193" dy=".35em" text-anchor="middle">7</text><text class="ann" x="687" y="178">0</text><circle class="n" cx="800" cy="129" r="17"/><text class="t" x="800" y="129" dy=".35em" text-anchor="middle">17</text><text class="ann" x="819" y="114">-1</text><circle class="n" cx="844" cy="193" r="17"/><text class="t" x="844" y="193" dy=".35em" text-anchor="middle">53</text><text class="ann" x="863" y="178">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">14 to 53, no rotation</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-24" viewBox="0 0 1072 288" width="1072" height="288" role="img" aria-label="4 to 12"><style>#dsfig-u3-24 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-24 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-24 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-24 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-24 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-24 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-24 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-24 .t{fill:#16181D;font-weight:500}#dsfig-u3-24 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-24 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-24 .dot{fill:#16181D}#dsfig-u3-24 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-24 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-24 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-24 .ah{fill:#454C5A}#dsfig-u3-24 .ah.hi{fill:#2340B8}#dsfig-u3-24 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-24 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-24 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-24 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-24 .e{stroke:#B1B7C3}html.dark #dsfig-u3-24 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-24 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-24 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-24 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-24 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-24 .t{fill:#E6E8ED}html.dark #dsfig-u3-24 .t.inv{fill:#0F1115}html.dark #dsfig-u3-24 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-24 .dot{fill:#E6E8ED}html.dark #dsfig-u3-24 .ann{fill:#8FA3FF}html.dark #dsfig-u3-24 .lbl{fill:#858D9C}html.dark #dsfig-u3-24 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-24 .ah{fill:#B1B7C3}html.dark #dsfig-u3-24 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-24 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-24 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-24 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah37" 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="ahh37" 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><text class="lbl" x="14" y="22">+4 LL 11</text><line class="e" x1="168" y1="65" x2="80" y2="129"/><line class="e" x1="168" y1="65" x2="212" y2="129"/><line class="e" x1="80" y1="129" x2="36" y2="193"/><line class="e" x1="80" y1="129" x2="124" y2="193"/><line class="e" x1="212" y1="129" x2="256" y2="193"/><circle class="n" cx="168" cy="65" r="17"/><text class="t" x="168" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="187" y="50">0</text><circle class="n" cx="80" cy="129" r="17"/><text class="t" x="80" y="129" dy=".35em" text-anchor="middle">7</text><text class="ann" x="99" y="114">0</text><circle class="n" cx="36" cy="193" r="17"/><text class="t" x="36" y="193" dy=".35em" text-anchor="middle">4</text><text class="ann" x="55" y="178">0</text><circle class="n" cx="124" cy="193" r="17"/><text class="t" x="124" y="193" dy=".35em" text-anchor="middle">11</text><text class="ann" x="143" y="178">0</text><circle class="n" cx="212" cy="129" r="17"/><text class="t" x="212" y="129" dy=".35em" text-anchor="middle">17</text><text class="ann" x="231" y="114">-1</text><circle class="n" cx="256" cy="193" r="17"/><text class="t" x="256" y="193" dy=".35em" text-anchor="middle">53</text><text class="ann" x="275" y="178">0</text><text class="lbl" x="326" y="22">+13</text><line class="e" x1="524" y1="65" x2="392" y2="129"/><line class="e" x1="524" y1="65" x2="568" y2="129"/><line class="e" x1="392" y1="129" x2="348" y2="193"/><line class="e" x1="392" y1="129" x2="436" y2="193"/><line class="e" x1="436" y1="193" x2="480" y2="257"/><line class="e" x1="568" y1="129" x2="612" y2="193"/><circle class="n" cx="524" cy="65" r="17"/><text class="t" x="524" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="543" y="50">+1</text><circle class="n" cx="392" cy="129" r="17"/><text class="t" x="392" y="129" dy=".35em" text-anchor="middle">7</text><text class="ann" x="411" y="114">-1</text><circle class="n" cx="348" cy="193" r="17"/><text class="t" x="348" y="193" dy=".35em" text-anchor="middle">4</text><text class="ann" x="367" y="178">0</text><circle class="n" cx="436" cy="193" r="17"/><text class="t" x="436" y="193" dy=".35em" text-anchor="middle">11</text><text class="ann" x="455" y="178">-1</text><circle class="n" cx="480" cy="257" r="17"/><text class="t" x="480" y="257" dy=".35em" text-anchor="middle">13</text><text class="ann" x="499" y="242">0</text><circle class="n" cx="568" cy="129" r="17"/><text class="t" x="568" y="129" dy=".35em" text-anchor="middle">17</text><text class="ann" x="587" y="114">-1</text><circle class="n" cx="612" cy="193" r="17"/><text class="t" x="612" y="193" dy=".35em" text-anchor="middle">53</text><text class="ann" x="631" y="178">0</text><text class="lbl" x="682" y="22">+12 RL 11</text><line class="e" x1="924" y1="65" x2="748" y2="129"/><line class="e" x1="924" y1="65" x2="968" y2="129"/><line class="e" x1="748" y1="129" x2="704" y2="193"/><line class="e" x1="748" y1="129" x2="836" y2="193"/><line class="e" x1="836" y1="193" x2="792" y2="257"/><line class="e" x1="836" y1="193" x2="880" y2="257"/><line class="e" x1="968" y1="129" x2="1012" y2="193"/><circle class="n" cx="924" cy="65" r="17"/><text class="t" x="924" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="943" y="50">+1</text><circle class="n" cx="748" cy="129" r="17"/><text class="t" x="748" y="129" dy=".35em" text-anchor="middle">7</text><text class="ann" x="767" y="114">-1</text><circle class="n" cx="704" cy="193" r="17"/><text class="t" x="704" y="193" dy=".35em" text-anchor="middle">4</text><text class="ann" x="723" y="178">0</text><circle class="n" cx="836" cy="193" r="17"/><text class="t" x="836" y="193" dy=".35em" text-anchor="middle">12</text><text class="ann" x="855" y="178">0</text><circle class="n" cx="792" cy="257" r="17"/><text class="t" x="792" y="257" dy=".35em" text-anchor="middle">11</text><text class="ann" x="811" y="242">0</text><circle class="n" cx="880" cy="257" r="17"/><text class="t" x="880" y="257" dy=".35em" text-anchor="middle">13</text><text class="ann" x="899" y="242">0</text><circle class="n" cx="968" cy="129" r="17"/><text class="t" x="968" y="129" dy=".35em" text-anchor="middle">17</text><text class="ann" x="987" y="114">-1</text><circle class="n" cx="1012" cy="193" r="17"/><text class="t" x="1012" y="193" dy=".35em" text-anchor="middle">53</text><text class="ann" x="1031" y="178">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">4 to 12</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-25" viewBox="0 0 1468 288" width="1468" height="288" role="img" aria-label="8 to 19"><style>#dsfig-u3-25 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-25 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-25 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-25 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-25 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-25 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-25 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-25 .t{fill:#16181D;font-weight:500}#dsfig-u3-25 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-25 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-25 .dot{fill:#16181D}#dsfig-u3-25 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-25 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-25 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-25 .ah{fill:#454C5A}#dsfig-u3-25 .ah.hi{fill:#2340B8}#dsfig-u3-25 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-25 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-25 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-25 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-25 .e{stroke:#B1B7C3}html.dark #dsfig-u3-25 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-25 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-25 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-25 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-25 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-25 .t{fill:#E6E8ED}html.dark #dsfig-u3-25 .t.inv{fill:#0F1115}html.dark #dsfig-u3-25 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-25 .dot{fill:#E6E8ED}html.dark #dsfig-u3-25 .ann{fill:#8FA3FF}html.dark #dsfig-u3-25 .lbl{fill:#858D9C}html.dark #dsfig-u3-25 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-25 .ah{fill:#B1B7C3}html.dark #dsfig-u3-25 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-25 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-25 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-25 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah38" 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="ahh38" 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><text class="lbl" x="14" y="22">+8 RL 7</text><line class="e" x1="300" y1="65" x2="168" y2="129"/><line class="e" x1="300" y1="65" x2="344" y2="129"/><line class="e" x1="168" y1="129" x2="80" y2="193"/><line class="e" x1="168" y1="129" x2="212" y2="193"/><line class="e" x1="80" y1="193" x2="36" y2="257"/><line class="e" x1="80" y1="193" x2="124" y2="257"/><line class="e" x1="212" y1="193" x2="256" y2="257"/><line class="e" x1="344" y1="129" x2="388" y2="193"/><circle class="n" cx="300" cy="65" r="17"/><text class="t" x="300" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="319" y="50">+1</text><circle class="n" cx="168" cy="129" r="17"/><text class="t" x="168" y="129" dy=".35em" text-anchor="middle">11</text><text class="ann" x="187" y="114">0</text><circle class="n" cx="80" cy="193" r="17"/><text class="t" x="80" y="193" dy=".35em" text-anchor="middle">7</text><text class="ann" x="99" y="178">0</text><circle class="n" cx="36" cy="257" r="17"/><text class="t" x="36" y="257" dy=".35em" text-anchor="middle">4</text><text class="ann" x="55" y="242">0</text><circle class="n" cx="124" cy="257" r="17"/><text class="t" x="124" y="257" dy=".35em" text-anchor="middle">8</text><text class="ann" x="143" y="242">0</text><circle class="n" cx="212" cy="193" r="17"/><text class="t" x="212" y="193" dy=".35em" text-anchor="middle">12</text><text class="ann" x="231" y="178">-1</text><circle class="n" cx="256" cy="257" r="17"/><text class="t" x="256" y="257" dy=".35em" text-anchor="middle">13</text><text class="ann" x="275" y="242">0</text><circle class="n" cx="344" cy="129" r="17"/><text class="t" x="344" y="129" dy=".35em" text-anchor="middle">17</text><text class="ann" x="363" y="114">-1</text><circle class="n" cx="388" cy="193" r="17"/><text class="t" x="388" y="193" dy=".35em" text-anchor="middle">53</text><text class="ann" x="407" y="178">0</text><text class="lbl" x="458" y="22">+60 RR 17</text><line class="e" x1="744" y1="65" x2="612" y2="129"/><line class="e" x1="744" y1="65" x2="832" y2="129"/><line class="e" x1="612" y1="129" x2="524" y2="193"/><line class="e" x1="612" y1="129" x2="656" y2="193"/><line class="e" x1="524" y1="193" x2="480" y2="257"/><line class="e" x1="524" y1="193" x2="568" y2="257"/><line class="e" x1="656" y1="193" x2="700" y2="257"/><line class="e" x1="832" y1="129" x2="788" y2="193"/><line class="e" x1="832" y1="129" x2="876" y2="193"/><circle class="n" cx="744" cy="65" r="17"/><text class="t" x="744" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="763" y="50">+1</text><circle class="n" cx="612" cy="129" r="17"/><text class="t" x="612" y="129" dy=".35em" text-anchor="middle">11</text><text class="ann" x="631" y="114">0</text><circle class="n" cx="524" cy="193" r="17"/><text class="t" x="524" y="193" dy=".35em" text-anchor="middle">7</text><text class="ann" x="543" y="178">0</text><circle class="n" cx="480" cy="257" r="17"/><text class="t" x="480" y="257" dy=".35em" text-anchor="middle">4</text><text class="ann" x="499" y="242">0</text><circle class="n" cx="568" cy="257" r="17"/><text class="t" x="568" y="257" dy=".35em" text-anchor="middle">8</text><text class="ann" x="587" y="242">0</text><circle class="n" cx="656" cy="193" r="17"/><text class="t" x="656" y="193" dy=".35em" text-anchor="middle">12</text><text class="ann" x="675" y="178">-1</text><circle class="n" cx="700" cy="257" r="17"/><text class="t" x="700" y="257" dy=".35em" text-anchor="middle">13</text><text class="ann" x="719" y="242">0</text><circle class="n" cx="832" cy="129" r="17"/><text class="t" x="832" y="129" dy=".35em" text-anchor="middle">53</text><text class="ann" x="851" y="114">0</text><circle class="n" cx="788" cy="193" r="17"/><text class="t" x="788" y="193" dy=".35em" text-anchor="middle">17</text><text class="ann" x="807" y="178">0</text><circle class="n" cx="876" cy="193" r="17"/><text class="t" x="876" y="193" dy=".35em" text-anchor="middle">60</text><text class="ann" x="895" y="178">0</text><text class="lbl" x="946" y="22">+19</text><line class="e" x1="1232" y1="65" x2="1100" y2="129"/><line class="e" x1="1232" y1="65" x2="1364" y2="129"/><line class="e" x1="1100" y1="129" x2="1012" y2="193"/><line class="e" x1="1100" y1="129" x2="1144" y2="193"/><line class="e" x1="1012" y1="193" x2="968" y2="257"/><line class="e" x1="1012" y1="193" x2="1056" y2="257"/><line class="e" x1="1144" y1="193" x2="1188" y2="257"/><line class="e" x1="1364" y1="129" x2="1276" y2="193"/><line class="e" x1="1364" y1="129" x2="1408" y2="193"/><line class="e" x1="1276" y1="193" x2="1320" y2="257"/><circle class="n" cx="1232" cy="65" r="17"/><text class="t" x="1232" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="1251" y="50">0</text><circle class="n" cx="1100" cy="129" r="17"/><text class="t" x="1100" y="129" dy=".35em" text-anchor="middle">11</text><text class="ann" x="1119" y="114">0</text><circle class="n" cx="1012" cy="193" r="17"/><text class="t" x="1012" y="193" dy=".35em" text-anchor="middle">7</text><text class="ann" x="1031" y="178">0</text><circle class="n" cx="968" cy="257" r="17"/><text class="t" x="968" y="257" dy=".35em" text-anchor="middle">4</text><text class="ann" x="987" y="242">0</text><circle class="n" cx="1056" cy="257" r="17"/><text class="t" x="1056" y="257" dy=".35em" text-anchor="middle">8</text><text class="ann" x="1075" y="242">0</text><circle class="n" cx="1144" cy="193" r="17"/><text class="t" x="1144" y="193" dy=".35em" text-anchor="middle">12</text><text class="ann" x="1163" y="178">-1</text><circle class="n" cx="1188" cy="257" r="17"/><text class="t" x="1188" y="257" dy=".35em" text-anchor="middle">13</text><text class="ann" x="1207" y="242">0</text><circle class="n" cx="1364" cy="129" r="17"/><text class="t" x="1364" y="129" dy=".35em" text-anchor="middle">53</text><text class="ann" x="1383" y="114">+1</text><circle class="n" cx="1276" cy="193" r="17"/><text class="t" x="1276" y="193" dy=".35em" text-anchor="middle">17</text><text class="ann" x="1295" y="178">-1</text><circle class="n" cx="1320" cy="257" r="17"/><text class="t" x="1320" y="257" dy=".35em" text-anchor="middle">19</text><text class="ann" x="1339" y="242">0</text><circle class="n" cx="1408" cy="193" r="17"/><text class="t" x="1408" y="193" dy=".35em" text-anchor="middle">60</text><text class="ann" x="1427" y="178">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">8 to 19</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-26" viewBox="0 0 1200 288" width="1200" height="288" role="img" aria-label="16, then 20: final tree"><style>#dsfig-u3-26 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-26 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-26 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-26 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-26 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-26 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-26 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-26 .t{fill:#16181D;font-weight:500}#dsfig-u3-26 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-26 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-26 .dot{fill:#16181D}#dsfig-u3-26 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-26 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-26 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-26 .ah{fill:#454C5A}#dsfig-u3-26 .ah.hi{fill:#2340B8}#dsfig-u3-26 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-26 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-26 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-26 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-26 .e{stroke:#B1B7C3}html.dark #dsfig-u3-26 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-26 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-26 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-26 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-26 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-26 .t{fill:#E6E8ED}html.dark #dsfig-u3-26 .t.inv{fill:#0F1115}html.dark #dsfig-u3-26 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-26 .dot{fill:#E6E8ED}html.dark #dsfig-u3-26 .ann{fill:#8FA3FF}html.dark #dsfig-u3-26 .lbl{fill:#858D9C}html.dark #dsfig-u3-26 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-26 .ah{fill:#B1B7C3}html.dark #dsfig-u3-26 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-26 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-26 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-26 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah39" 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="ahh39" 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><text class="lbl" x="14" y="22">+16</text><line class="e" x1="300" y1="65" x2="168" y2="129"/><line class="e" x1="300" y1="65" x2="476" y2="129"/><line class="e" x1="168" y1="129" x2="80" y2="193"/><line class="e" x1="168" y1="129" x2="212" y2="193"/><line class="e" x1="80" y1="193" x2="36" y2="257"/><line class="e" x1="80" y1="193" x2="124" y2="257"/><line class="e" x1="212" y1="193" x2="256" y2="257"/><line class="e" x1="476" y1="129" x2="388" y2="193"/><line class="e" x1="476" y1="129" x2="520" y2="193"/><line class="e" x1="388" y1="193" x2="344" y2="257"/><line class="e" x1="388" y1="193" x2="432" y2="257"/><circle class="n" cx="300" cy="65" r="17"/><text class="t" x="300" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="319" y="50">0</text><circle class="n" cx="168" cy="129" r="17"/><text class="t" x="168" y="129" dy=".35em" text-anchor="middle">11</text><text class="ann" x="187" y="114">0</text><circle class="n" cx="80" cy="193" r="17"/><text class="t" x="80" y="193" dy=".35em" text-anchor="middle">7</text><text class="ann" x="99" y="178">0</text><circle class="n" cx="36" cy="257" r="17"/><text class="t" x="36" y="257" dy=".35em" text-anchor="middle">4</text><text class="ann" x="55" y="242">0</text><circle class="n" cx="124" cy="257" r="17"/><text class="t" x="124" y="257" dy=".35em" text-anchor="middle">8</text><text class="ann" x="143" y="242">0</text><circle class="n" cx="212" cy="193" r="17"/><text class="t" x="212" y="193" dy=".35em" text-anchor="middle">12</text><text class="ann" x="231" y="178">-1</text><circle class="n" cx="256" cy="257" r="17"/><text class="t" x="256" y="257" dy=".35em" text-anchor="middle">13</text><text class="ann" x="275" y="242">0</text><circle class="n" cx="476" cy="129" r="17"/><text class="t" x="476" y="129" dy=".35em" text-anchor="middle">53</text><text class="ann" x="495" y="114">+1</text><circle class="n" cx="388" cy="193" r="17"/><text class="t" x="388" y="193" dy=".35em" text-anchor="middle">17</text><text class="ann" x="407" y="178">0</text><circle class="n" cx="344" cy="257" r="17"/><text class="t" x="344" y="257" dy=".35em" text-anchor="middle">16</text><text class="ann" x="363" y="242">0</text><circle class="n" cx="432" cy="257" r="17"/><text class="t" x="432" y="257" dy=".35em" text-anchor="middle">19</text><text class="ann" x="451" y="242">0</text><circle class="n" cx="520" cy="193" r="17"/><text class="t" x="520" y="193" dy=".35em" text-anchor="middle">60</text><text class="ann" x="539" y="178">0</text><text class="lbl" x="590" y="22">+20 LR 53</text><line class="e" x1="876" y1="65" x2="744" y2="129"/><line class="e" x1="876" y1="65" x2="1008" y2="129"/><line class="e" x1="744" y1="129" x2="656" y2="193"/><line class="e" x1="744" y1="129" x2="788" y2="193"/><line class="e" x1="656" y1="193" x2="612" y2="257"/><line class="e" x1="656" y1="193" x2="700" y2="257"/><line class="e" x1="788" y1="193" x2="832" y2="257"/><line class="e" x1="1008" y1="129" x2="964" y2="193"/><line class="e" x1="1008" y1="129" x2="1096" y2="193"/><line class="e" x1="964" y1="193" x2="920" y2="257"/><line class="e" x1="1096" y1="193" x2="1052" y2="257"/><line class="e" x1="1096" y1="193" x2="1140" y2="257"/><circle class="n" cx="876" cy="65" r="17"/><text class="t" x="876" y="65" dy=".35em" text-anchor="middle">14</text><text class="ann" x="895" y="50">0</text><circle class="n" cx="744" cy="129" r="17"/><text class="t" x="744" y="129" dy=".35em" text-anchor="middle">11</text><text class="ann" x="763" y="114">0</text><circle class="n" cx="656" cy="193" r="17"/><text class="t" x="656" y="193" dy=".35em" text-anchor="middle">7</text><text class="ann" x="675" y="178">0</text><circle class="n" cx="612" cy="257" r="17"/><text class="t" x="612" y="257" dy=".35em" text-anchor="middle">4</text><text class="ann" x="631" y="242">0</text><circle class="n" cx="700" cy="257" r="17"/><text class="t" x="700" y="257" dy=".35em" text-anchor="middle">8</text><text class="ann" x="719" y="242">0</text><circle class="n" cx="788" cy="193" r="17"/><text class="t" x="788" y="193" dy=".35em" text-anchor="middle">12</text><text class="ann" x="807" y="178">-1</text><circle class="n" cx="832" cy="257" r="17"/><text class="t" x="832" y="257" dy=".35em" text-anchor="middle">13</text><text class="ann" x="851" y="242">0</text><circle class="n" cx="1008" cy="129" r="17"/><text class="t" x="1008" y="129" dy=".35em" text-anchor="middle">19</text><text class="ann" x="1027" y="114">0</text><circle class="n" cx="964" cy="193" r="17"/><text class="t" x="964" y="193" dy=".35em" text-anchor="middle">17</text><text class="ann" x="983" y="178">+1</text><circle class="n" cx="920" cy="257" r="17"/><text class="t" x="920" y="257" dy=".35em" text-anchor="middle">16</text><text class="ann" x="939" y="242">0</text><circle class="n" cx="1096" cy="193" r="17"/><text class="t" x="1096" y="193" dy=".35em" text-anchor="middle">53</text><text class="ann" x="1115" y="178">0</text><circle class="n" cx="1052" cy="257" r="17"/><text class="t" x="1052" y="257" dy=".35em" text-anchor="middle">20</text><text class="ann" x="1071" y="242">0</text><circle class="n" cx="1140" cy="257" r="17"/><text class="t" x="1140" y="257" dy=".35em" text-anchor="middle">60</text><text class="ann" x="1159" y="242">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">16, then 20: final tree</figcaption></figure>

Deletion example. Deleting 40, right of $A$ = 30, leaves BF +2; $B$ = 20.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-27" viewBox="0 0 1172 224" width="1172" height="224" role="img" aria-label="R0, R1 right rotation; R-1 LR"><style>#dsfig-u3-27 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-27 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-27 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-27 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-27 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-27 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-27 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-27 .t{fill:#16181D;font-weight:500}#dsfig-u3-27 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-27 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-27 .dot{fill:#16181D}#dsfig-u3-27 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-27 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-27 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-27 .ah{fill:#454C5A}#dsfig-u3-27 .ah.hi{fill:#2340B8}#dsfig-u3-27 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-27 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-27 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-27 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-27 .e{stroke:#B1B7C3}html.dark #dsfig-u3-27 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-27 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-27 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-27 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-27 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-27 .t{fill:#E6E8ED}html.dark #dsfig-u3-27 .t.inv{fill:#0F1115}html.dark #dsfig-u3-27 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-27 .dot{fill:#E6E8ED}html.dark #dsfig-u3-27 .ann{fill:#8FA3FF}html.dark #dsfig-u3-27 .lbl{fill:#858D9C}html.dark #dsfig-u3-27 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-27 .ah{fill:#B1B7C3}html.dark #dsfig-u3-27 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-27 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-27 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-27 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah40" 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="ahh40" 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><text class="lbl" x="14" y="22">R0</text><line class="e" x1="168" y1="65" x2="80" y2="129"/><line class="e" x1="80" y1="129" x2="36" y2="193"/><line class="e" x1="80" y1="129" x2="124" y2="193"/><circle class="n" cx="168" cy="65" r="17"/><text class="t" x="168" y="65" dy=".35em" text-anchor="middle">30</text><text class="ann" x="187" y="50">+2</text><circle class="n" cx="80" cy="129" r="17"/><text class="t" x="80" y="129" dy=".35em" text-anchor="middle">20</text><text class="ann" x="99" y="114">0</text><circle class="n" cx="36" cy="193" r="17"/><text class="t" x="36" y="193" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="124" cy="193" r="17"/><text class="t" x="124" y="193" dy=".35em" text-anchor="middle">25</text><text class="lbl" x="238" y="22">after</text><line class="e" x1="304" y1="65" x2="260" y2="129"/><line class="e" x1="304" y1="65" x2="392" y2="129"/><line class="e" x1="392" y1="129" x2="348" y2="193"/><circle class="n" cx="304" cy="65" r="17"/><text class="t" x="304" y="65" dy=".35em" text-anchor="middle">20</text><text class="ann" x="323" y="50">-1</text><circle class="n" cx="260" cy="129" r="17"/><text class="t" x="260" y="129" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="392" cy="129" r="17"/><text class="t" x="392" y="129" dy=".35em" text-anchor="middle">30</text><text class="ann" x="411" y="114">+1</text><circle class="n" cx="348" cy="193" r="17"/><text class="t" x="348" y="193" dy=".35em" text-anchor="middle">25</text><text class="lbl" x="462" y="22">R1</text><line class="e" x1="572" y1="65" x2="528" y2="129"/><line class="e" x1="528" y1="129" x2="484" y2="193"/><circle class="n" cx="572" cy="65" r="17"/><text class="t" x="572" y="65" dy=".35em" text-anchor="middle">30</text><text class="ann" x="591" y="50">+2</text><circle class="n" cx="528" cy="129" r="17"/><text class="t" x="528" y="129" dy=".35em" text-anchor="middle">20</text><text class="ann" x="547" y="114">+1</text><circle class="n" cx="484" cy="193" r="17"/><text class="t" x="484" y="193" dy=".35em" text-anchor="middle">10</text><text class="lbl" x="642" y="22">after</text><line class="e" x1="708" y1="65" x2="664" y2="129"/><line class="e" x1="708" y1="65" x2="752" y2="129"/><circle class="n" cx="708" cy="65" r="17"/><text class="t" x="708" y="65" dy=".35em" text-anchor="middle">20</text><text class="ann" x="727" y="50">0</text><circle class="n" cx="664" cy="129" r="17"/><text class="t" x="664" y="129" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="752" cy="129" r="17"/><text class="t" x="752" y="129" dy=".35em" text-anchor="middle">30</text><text class="ann" x="771" y="114">0</text><text class="lbl" x="822" y="22">R-1</text><line class="e" x1="932" y1="65" x2="844" y2="129"/><line class="e" x1="844" y1="129" x2="888" y2="193"/><circle class="n" cx="932" cy="65" r="17"/><text class="t" x="932" y="65" dy=".35em" text-anchor="middle">30</text><text class="ann" x="951" y="50">+2</text><circle class="n" cx="844" cy="129" r="17"/><text class="t" x="844" y="129" dy=".35em" text-anchor="middle">20</text><text class="ann" x="863" y="114">-1</text><circle class="n" cx="888" cy="193" r="17"/><text class="t" x="888" y="193" dy=".35em" text-anchor="middle">25</text><text class="lbl" x="1002" y="22">after</text><line class="e" x1="1068" y1="65" x2="1024" y2="129"/><line class="e" x1="1068" y1="65" x2="1112" y2="129"/><circle class="n" cx="1068" cy="65" r="17"/><text class="t" x="1068" y="65" dy=".35em" text-anchor="middle">25</text><text class="ann" x="1087" y="50">0</text><circle class="n" cx="1024" cy="129" r="17"/><text class="t" x="1024" y="129" dy=".35em" text-anchor="middle">20</text><circle class="n" cx="1112" cy="129" r="17"/><text class="t" x="1112" y="129" dy=".35em" text-anchor="middle">30</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">R0, R1 right rotation; R-1 LR</figcaption></figure>

L0, L1 (left rotation) and L-1 (RL) are the mirrors. R0 keeps height 2 and stops the walk; R1 and R-1 drop it to 1 and continue it.

Answer frame. Open with the definition and BF rule; draw LL, RR, LR, RL with $z$, $y$, $x$, T1-T4; redraw the tree with BFs after each key, naming case and node; for deletion give the upward walk and R0, R1, R-1; close with height $O(\log n)$.

Pitfall: Rotate at the lowest unbalanced node on the path from the new key, not the root, and re-check BFs after each key.

Asked: [7 marks] (Dec 2022, Nov 2022, Dec 2023, Jun 2024) Explain AVL tree; insert 48, 25, 10, 5, 7, 3, 28, 20, 8, 16 Asked: [7 marks] (Nov 2022, Dec 2023, Jun 2024) Draw an AVL tree for 485, 575, 655, 745, 830, 910, 100, 110, 520, 130, 340, 450, 365, 525, 204, 155, 130, 35; define AVL, explain rotations, construct for 14, 17, 11, 7, 53, 4, 13, 12, 8, 60, 19, 16, 20 Asked: [7 marks] (Dec 2024) Illustrate insertion and deletion in an AVL tree with examples 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">Low weight</span>

Definition. <mark>A binary heap is a complete binary tree in which every node is at least as large as its children (max-heap) or at most as large (min-heap).</mark>

Key points.

1. It is stored in an array where the children of index $i$ are $2i+1$ and $2i+2$, and the maximum sits at index 0, read in $O(1)$.
2. Insert places the key at the next free leaf and moves it up while it beats its parent, in $O(\log n)$: 40 into [30,20,25] gives [40,30,25,20].
3. Heapify$(i)$ swaps node $i$ with its larger child while it is smaller, repeating at that child, and costs $O(\log n)$.
4. Delete-max removes the root, moves the last element to the root and heapifies it, costing $O(\log n)$.
5. Build-heap heapifies indices $\lfloor n/2\rfloor-1$ down to 0 in $O(n)$: at most $\lceil n/2^{h+1}\rceil$ nodes at height $h$ each sink $\le h$ levels, costing $\sum_{h}\frac{n}{2^{h+1}}\,h=\frac{n}{2}\sum_{h}\frac{h}{2^h}\le\frac{n}{2}\cdot2=n$, since $\sum_{h\ge0}h/2^h=2$.

Example (build max-heap). [5,3,17,10,84,19,6,22,9], $n=9$, so heapify $i=3,2,1,0$:

Example (delete-max). Removing 84 moves the last key 9 to the root, which sinks past 22 and then 10: 22,10,19,9,3,17,6,5.

Asked: [7 marks] (Dec 2022) Explain analysis of heap operations with 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">Low weight</span>

Definition. <mark>An expression tree is a binary tree whose leaves are operands and whose internal nodes are operators, so that its postorder gives postfix and its preorder gives prefix.</mark>

Key points.

1. For $(3a-b)^2(4c+2d)^3$ the root is *, each side is rooted at ^, and products such as $3a$ are * with children 3 and a.
2. Uses: BST for searching, AVL and red-black for guaranteed $O(\log n)$, heap for priority queues, B-tree for databases, Huffman tree for compression.
3. A tree is stored in memory either as an array (children of $i$ at $2i+1$, $2i+2$, parent at $\lfloor(i-1)/2\rfloor$; direct access, no pointers, but space wasted on skewed trees, fixed size, costly insertion and deletion as elements shift) or as linked nodes (left, right pointers; dynamic, extra pointer memory).

The full tree fills all 7 slots (parent of index 4 is $\lfloor3/2\rfloor=1$, key 30); the skewed 3-node tree wastes 4 of 7 slots, as height $h$ needs $2^{h+1}-1$.

struct node { int data; struct node *left, *right; };
root -> [ * | 50 | * ]
          /          \
  [ * | 30 | * ]    [ * | 70 | * ]
     /       \         /       \
[N|20|N] [N|40|N] [N|60|N] [N|80|N]      N = NULL

4. A Huffman tree is a full binary tree whose leaves carry the symbol weights and whose weighted external path length $\sum w_i l_i$ is minimum, so the root-to-leaf paths give optimal prefix codes.
5. Algorithm: put every symbol with its frequency in a min-heap; repeatedly remove the two smallest, merge them under a new node of their total weight and insert it until one tree remains; label left edges 0, right edges 1. "data structures" has t 3; a, s, r, u 2; d, space, c, e 1.

Ties: leaves before merged nodes, leaves in occurrence order (d, a, t, sp, s, r, u, c, e), merged nodes by creation; the first removed is the left child.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-28" viewBox="0 0 621.8 424" width="621.8" height="424" role="img" aria-label="Huffman tree; internal nodes show weights (4as is a+s), left edge 0, right edge 1"><style>#dsfig-u3-28 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-28 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-28 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-28 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-28 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-28 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-28 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-28 .t{fill:#16181D;font-weight:500}#dsfig-u3-28 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-28 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-28 .dot{fill:#16181D}#dsfig-u3-28 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-28 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-28 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-28 .ah{fill:#454C5A}#dsfig-u3-28 .ah.hi{fill:#2340B8}#dsfig-u3-28 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-28 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-28 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-28 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-28 .e{stroke:#B1B7C3}html.dark #dsfig-u3-28 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-28 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-28 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-28 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-28 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-28 .t{fill:#E6E8ED}html.dark #dsfig-u3-28 .t.inv{fill:#0F1115}html.dark #dsfig-u3-28 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-28 .dot{fill:#E6E8ED}html.dark #dsfig-u3-28 .ann{fill:#8FA3FF}html.dark #dsfig-u3-28 .lbl{fill:#858D9C}html.dark #dsfig-u3-28 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-28 .ah{fill:#B1B7C3}html.dark #dsfig-u3-28 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-28 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-28 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-28 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah41" 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="ahh41" 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><path class="e" d="M255.2,48.5 L117.2,117.5"/><path class="e" d="M288.3,50.1 L393.7,115.9"/><path class="e" d="M89.3,141.6 L50.9,196.4"/><path class="e" d="M111.1,141.6 L149.5,196.4"/><path class="e" d="M153.3,229.6 L133.1,280.4"/><path class="e" d="M167.5,229.6 L187.7,280.4"/><path class="e" d="M395.7,138.8 L329.3,199.2"/><path class="e" d="M423.2,139.4 L482.4,198.6"/><path class="e" d="M308.1,229.6 L287.9,280.4"/><path class="e" d="M322.3,229.6 L342.5,280.4"/><path class="e" d="M486,228.3 L454,281.7"/><path class="e" d="M505.6,228.3 L537.6,281.7"/><path class="e" d="M437.1,315.6 L416.9,366.4"/><path class="e" d="M451.3,315.6 L471.5,366.4"/><path class="e" d="M540.3,315.6 L520.1,366.4"/><path class="e" d="M554.5,315.6 L574.7,366.4"/><g class="wl"><rect x="176.6" y="74" width="19.2" height="18" rx="9"/><text class="t" x="186.2" y="83" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="331.4" y="74" width="19.2" height="18" rx="9"/><text class="t" x="341" y="83" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="60.5" y="160" width="19.2" height="18" rx="9"/><text class="t" x="70.1" y="169" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="120.7" y="160" width="19.2" height="18" rx="9"/><text class="t" x="130.3" y="169" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="133.6" y="246" width="19.2" height="18" rx="9"/><text class="t" x="143.2" y="255" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="168" y="246" width="19.2" height="18" rx="9"/><text class="t" x="177.6" y="255" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="352.9" y="160" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="169" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="443.2" y="160" width="19.2" height="18" rx="9"/><text class="t" x="452.8" y="169" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="288.4" y="246" width="19.2" height="18" rx="9"/><text class="t" x="298" y="255" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="322.8" y="246" width="19.2" height="18" rx="9"/><text class="t" x="332.4" y="255" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="460.4" y="246" width="19.2" height="18" rx="9"/><text class="t" x="470" y="255" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="512" y="246" width="19.2" height="18" rx="9"/><text class="t" x="521.6" y="255" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="417.4" y="332" width="19.2" height="18" rx="9"/><text class="t" x="427" y="341" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="451.8" y="332" width="19.2" height="18" rx="9"/><text class="t" x="461.4" y="341" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="520.6" y="332" width="19.2" height="18" rx="9"/><text class="t" x="530.2" y="341" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="555" y="332" width="19.2" height="18" rx="9"/><text class="t" x="564.6" y="341" dy=".35em" text-anchor="middle">1</text></g><circle class="n" cx="272.2" cy="40" r="18"/><text class="t" x="272.2" y="40" dy=".35em" text-anchor="middle">15</text><circle class="n" cx="100.2" cy="126" r="18"/><text class="t" x="100.2" y="126" dy=".35em" text-anchor="middle">7</text><circle class="n" cx="409.8" cy="126" r="18"/><text class="t" x="409.8" y="126" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">t</text><circle class="n" cx="160.4" cy="212" r="18"/><text class="t" x="160.4" y="212" dy=".35em" text-anchor="middle">4as</text><circle class="n" cx="315.2" cy="212" r="18"/><text class="t" x="315.2" y="212" dy=".35em" text-anchor="middle">4ru</text><circle class="n" cx="495.8" cy="212" r="18"/><text class="t" x="495.8" y="212" dy=".35em" text-anchor="middle">4dc</text><circle class="n" cx="126" cy="298" r="18"/><text class="t" x="126" y="298" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="194.8" cy="298" r="18"/><text class="t" x="194.8" y="298" dy=".35em" text-anchor="middle">s</text><circle class="n" cx="280.8" cy="298" r="18"/><text class="t" x="280.8" y="298" dy=".35em" text-anchor="middle">r</text><circle class="n" cx="349.6" cy="298" r="18"/><text class="t" x="349.6" y="298" dy=".35em" text-anchor="middle">u</text><circle class="n" cx="444.2" cy="298" r="18"/><text class="t" x="444.2" y="298" dy=".35em" text-anchor="middle">2ds</text><circle class="n" cx="547.4" cy="298" r="18"/><text class="t" x="547.4" y="298" dy=".35em" text-anchor="middle">2ce</text><circle class="n" cx="409.8" cy="384" r="18"/><text class="t" x="409.8" y="384" dy=".35em" text-anchor="middle">d</text><circle class="n" cx="478.6" cy="384" r="18"/><text class="t" x="478.6" y="384" dy=".35em" text-anchor="middle">sp</text><circle class="n" cx="513" cy="384" r="18"/><text class="t" x="513" y="384" dy=".35em" text-anchor="middle">c</text><circle class="n" cx="581.8" cy="384" r="18"/><text class="t" x="581.8" y="384" dy=".35em" text-anchor="middle">e</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Huffman tree; internal nodes show weights (4as is a+s), left edge 0, right edge 1</figcaption></figure>

Codes: t 00, a 010, s 011, r 100, u 101, d 1100, space 1101, c 1110, e 1111; total $6+24+16=$ 46 bits, against $15\times8=$ 120 bits in 8-bit code (62% saved); any tie rule gives 46.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-29" viewBox="0 0 800 326" width="800" height="326" role="img" aria-label="Expression tree for (3a - b)^2 (4c + 2d)^3"><style>#dsfig-u3-29 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-29 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-29 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-29 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-29 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-29 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-29 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-29 .t{fill:#16181D;font-weight:500}#dsfig-u3-29 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-29 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-29 .dot{fill:#16181D}#dsfig-u3-29 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-29 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-29 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-29 .ah{fill:#454C5A}#dsfig-u3-29 .ah.hi{fill:#2340B8}#dsfig-u3-29 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-29 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-29 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-29 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-29 .e{stroke:#B1B7C3}html.dark #dsfig-u3-29 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-29 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-29 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-29 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-29 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-29 .t{fill:#E6E8ED}html.dark #dsfig-u3-29 .t.inv{fill:#0F1115}html.dark #dsfig-u3-29 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-29 .dot{fill:#E6E8ED}html.dark #dsfig-u3-29 .ann{fill:#8FA3FF}html.dark #dsfig-u3-29 .lbl{fill:#858D9C}html.dark #dsfig-u3-29 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-29 .ah{fill:#B1B7C3}html.dark #dsfig-u3-29 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-29 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-29 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-29 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah42" 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="ahh42" 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="344" y1="39" x2="256" y2="103"/><line class="e" x1="344" y1="39" x2="696" y2="103"/><line class="e" x1="256" y1="103" x2="168" y2="167"/><line class="e" x1="256" y1="103" x2="300" y2="167"/><line class="e" x1="168" y1="167" x2="80" y2="231"/><line class="e" x1="168" y1="167" x2="212" y2="231"/><line class="e" x1="80" y1="231" x2="36" y2="295"/><line class="e" x1="80" y1="231" x2="124" y2="295"/><line class="e" x1="696" y1="103" x2="520" y2="167"/><line class="e" x1="696" y1="103" x2="740" y2="167"/><line class="e" x1="520" y1="167" x2="432" y2="231"/><line class="e" x1="520" y1="167" x2="608" y2="231"/><line class="e" x1="432" y1="231" x2="388" y2="295"/><line class="e" x1="432" y1="231" x2="476" y2="295"/><line class="e" x1="608" y1="231" x2="564" y2="295"/><line class="e" x1="608" y1="231" x2="652" y2="295"/><circle class="n" cx="344" cy="39" r="17"/><text class="t" x="344" y="39" dy=".35em" text-anchor="middle"></text><circle class="n" cx="256" cy="103" r="17"/><text class="t" x="256" y="103" dy=".35em" text-anchor="middle">^</text><circle class="n" cx="168" cy="167" r="17"/><text class="t" x="168" y="167" dy=".35em" text-anchor="middle">-</text><circle class="n" cx="80" cy="231" r="17"/><text class="t" x="80" y="231" dy=".35em" text-anchor="middle"></text><circle class="n" cx="36" cy="295" r="17"/><text class="t" x="36" y="295" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="124" cy="295" r="17"/><text class="t" x="124" y="295" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="696" cy="103" r="17"/><text class="t" x="696" y="103" dy=".35em" text-anchor="middle">^</text><circle class="n" cx="520" cy="167" r="17"/><text class="t" x="520" y="167" dy=".35em" text-anchor="middle">+</text><circle class="n" cx="432" cy="231" r="17"/><text class="t" x="432" y="231" dy=".35em" text-anchor="middle"></text><circle class="n" cx="388" cy="295" r="17"/><text class="t" x="388" y="295" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="476" cy="295" r="17"/><text class="t" x="476" y="295" dy=".35em" text-anchor="middle">c</text><circle class="n" cx="608" cy="231" r="17"/><text class="t" x="608" y="231" dy=".35em" text-anchor="middle"></text><circle class="n" cx="564" cy="295" r="17"/><text class="t" x="564" y="295" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="652" cy="295" r="17"/><text class="t" x="652" y="295" dy=".35em" text-anchor="middle">d</text><circle class="n" cx="740" cy="167" r="17"/><text class="t" x="740" y="167" dy=".35em" text-anchor="middle">3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Expression tree for (3a - b)^2 (4c + 2d)^3</figcaption></figure>

Asked: [7 marks] (Dec 2023) Construct an expression tree for $(3a-b)^2(4c+2d)^3$ Asked: [7 marks] (Dec 2023) How a tree is stored in memory; advantages and disadvantages of array representation Asked: [7 marks] (Dec 2023) Define Huffman tree, algorithm, construct for "data structures" with optimal codes

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. <mark>A forest is a set of zero or more disjoint trees.</mark>

Key points.

1. Removing the root of a tree leaves a forest of its subtrees.
2. A forest converts to one binary tree: left pointer to the first child, right pointer to the next sibling.
3. Forest traversals follow the corresponding binary tree.

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. <mark>An m-way tree is a tree in which each node holds up to m-1 sorted keys and has up to m children.</mark>

Key points.

1. A node with $k$ keys has $k+1$ children, and subtree keys lie between adjacent keys.
2. Search picks the child whose key range contains the target.
3. It is not balanced by itself; B-trees add balance 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">Low 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, every non-root node has at least $\lceil m/2\rceil$ children, and all leaves are on one level.</mark>

Key points.

1. For order 5 a node holds at most 4 keys and 5 children, and non-root nodes hold at least 2 keys.
2. Keys go into the correct leaf in sorted order; when a node reaches 5 keys it splits: the middle (3rd) key moves up to the parent and the remaining keys form two nodes.
3. A split that overfills the parent splits it too; a root split adds a level.

Example (Jun 2023). Insert 78, 21, 11, 97, 85, 74, 63, 45, 42, 57, 20, 16, 19, 32, 30, 31:

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-30" viewBox="0 0 476 130" width="476" height="130" role="img" aria-label="Final B-tree of order 5 containing all 16 keys"><style>#dsfig-u3-30 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-30 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-30 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-30 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-30 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-30 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-30 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-30 .t{fill:#16181D;font-weight:500}#dsfig-u3-30 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-30 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-30 .dot{fill:#16181D}#dsfig-u3-30 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-30 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-30 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-30 .ah{fill:#454C5A}#dsfig-u3-30 .ah.hi{fill:#2340B8}#dsfig-u3-30 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-30 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-30 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-30 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-30 .e{stroke:#B1B7C3}html.dark #dsfig-u3-30 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-30 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-30 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-30 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-30 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-30 .t{fill:#E6E8ED}html.dark #dsfig-u3-30 .t.inv{fill:#0F1115}html.dark #dsfig-u3-30 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-30 .dot{fill:#E6E8ED}html.dark #dsfig-u3-30 .ann{fill:#8FA3FF}html.dark #dsfig-u3-30 .lbl{fill:#858D9C}html.dark #dsfig-u3-30 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-30 .ah{fill:#B1B7C3}html.dark #dsfig-u3-30 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-30 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-30 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-30 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah43" 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="ahh43" 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="173.5" y1="52" x2="59" y2="101"/><line class="e" x1="203.5" y1="52" x2="150" y2="101"/><line class="e" x1="233.5" y1="52" x2="226" y2="101"/><line class="e" x1="263.5" y1="52" x2="317" y2="101"/><line class="e" x1="293.5" y1="52" x2="408" y2="101"/><rect class="n" x="173.5" y="22" width="120" height="30" rx="3"/><text class="t" x="188.5" y="37" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="203.5" y1="22" x2="203.5" y2="52"/><text class="t" x="218.5" y="37" dy=".35em" text-anchor="middle">31</text><line class="kd" x1="233.5" y1="22" x2="233.5" y2="52"/><text class="t" x="248.5" y="37" dy=".35em" text-anchor="middle">45</text><line class="kd" x1="263.5" y1="22" x2="263.5" y2="52"/><text class="t" x="278.5" y="37" dy=".35em" text-anchor="middle">78</text><rect class="n" x="14" y="86" width="90" height="30" rx="3"/><text class="t" x="29" y="101" dy=".35em" text-anchor="middle">11</text><line class="kd" x1="44" y1="86" x2="44" y2="116"/><text class="t" x="59" y="101" dy=".35em" text-anchor="middle">16</text><line class="kd" x1="74" y1="86" x2="74" y2="116"/><text class="t" x="89" y="101" dy=".35em" text-anchor="middle">19</text><rect class="n" x="120" y="86" width="60" height="30" rx="3"/><text class="t" x="135" y="101" dy=".35em" text-anchor="middle">21</text><line class="kd" x1="150" y1="86" x2="150" y2="116"/><text class="t" x="165" y="101" dy=".35em" text-anchor="middle">30</text><rect class="n" x="196" y="86" width="60" height="30" rx="3"/><text class="t" x="211" y="101" dy=".35em" text-anchor="middle">32</text><line class="kd" x1="226" y1="86" x2="226" y2="116"/><text class="t" x="241" y="101" dy=".35em" text-anchor="middle">42</text><rect class="n" x="272" y="86" width="90" height="30" rx="3"/><text class="t" x="287" y="101" dy=".35em" text-anchor="middle">57</text><line class="kd" x1="302" y1="86" x2="302" y2="116"/><text class="t" x="317" y="101" dy=".35em" text-anchor="middle">63</text><line class="kd" x1="332" y1="86" x2="332" y2="116"/><text class="t" x="347" y="101" dy=".35em" text-anchor="middle">74</text><rect class="n" x="378" y="86" width="60" height="30" rx="3"/><text class="t" x="393" y="101" dy=".35em" text-anchor="middle">85</text><line class="kd" x1="408" y1="86" x2="408" y2="116"/><text class="t" x="423" y="101" dy=".35em" text-anchor="middle">97</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Final B-tree of order 5 containing all 16 keys</figcaption></figure>

Answer frame. Open with the order-5 properties; redraw at each split; close with the final tree.

Asked: [7 marks] (Jun 2023) Construct a B-tree of order 5 for 78, 21, 11, 97, 85, 74, 63, 45, 42, 57, 20, 16, 19, 32, 30, 31

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. <mark>A B+ tree is a B-tree variant in which all data records are stored in leaf nodes and internal nodes hold only index keys.</mark>

Key points.

1. Leaves are linked in sequence, so range and sequential scans are fast.
2. Every search reaches a leaf, so cost is uniform.
3. Internal nodes hold no data, so more keys fit per node and the tree is shallower.

B* tree and 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">Low weight</span>

Definition. <mark>A red-black tree is a self-balancing binary search tree in which every node is coloured red or black and the colouring rules keep the longest path at most twice the shortest.</mark>

Key points.

1. The root is black and every NIL leaf is black.
2. A red node cannot have a red child, so no two consecutive red nodes appear on a path.
3. Every path from a node to its descendant NIL leaves contains the same number of black nodes, the black-height.
4. Search, insertion and deletion take $O(\log n)$, with rebalancing by recolouring and rotations.
5. A B* tree is a B-tree that keeps nodes at least two-thirds full by sharing keys with a sibling before splitting.
6. A new key is a red leaf; under a red parent, a red uncle means recolour (parent, uncle black, grandparent red, repeat upward), a black uncle one or two rotations plus recolouring.
7. Deleting a black node leaves an extra black, fixed by recolouring or at most 3 rotations; being looser than AVL ($2\log_2(n+1)$ against $1.44\log_2n$ height), it rotates less.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-31" viewBox="0 0 536 262" width="536" height="262" role="img" aria-label="Red-black tree after inserting 10, 20, 30, 15, 13, with NIL leaves; black-height 2"><style>#dsfig-u3-31 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-31 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-31 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-31 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-31 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-31 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-31 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-31 .t{fill:#16181D;font-weight:500}#dsfig-u3-31 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-31 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-31 .dot{fill:#16181D}#dsfig-u3-31 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-31 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-31 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-31 .ah{fill:#454C5A}#dsfig-u3-31 .ah.hi{fill:#2340B8}#dsfig-u3-31 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-31 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-31 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-31 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-31 .e{stroke:#B1B7C3}html.dark #dsfig-u3-31 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-31 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-31 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-31 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-31 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-31 .t{fill:#E6E8ED}html.dark #dsfig-u3-31 .t.inv{fill:#0F1115}html.dark #dsfig-u3-31 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-31 .dot{fill:#E6E8ED}html.dark #dsfig-u3-31 .ann{fill:#8FA3FF}html.dark #dsfig-u3-31 .lbl{fill:#858D9C}html.dark #dsfig-u3-31 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-31 .ah{fill:#B1B7C3}html.dark #dsfig-u3-31 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-31 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-31 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-31 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah44" 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="ahh44" 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="344" y1="39" x2="168" y2="103"/><line class="e" x1="344" y1="39" x2="432" y2="103"/><line class="e" x1="168" y1="103" x2="80" y2="167"/><line class="e" x1="168" y1="103" x2="256" 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="256" y1="167" x2="212" y2="231"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><line class="e" x1="432" y1="103" x2="388" y2="167"/><line class="e" x1="432" y1="103" x2="476" y2="167"/><circle class="n rb-b" cx="344" cy="39" r="17"/><text class="t inv" x="344" y="39" dy=".35em" text-anchor="middle">20</text><circle class="n rb-b" cx="168" cy="103" r="17"/><text class="t inv" x="168" y="103" dy=".35em" text-anchor="middle">13</text><circle class="n rb-r" cx="80" cy="167" r="17"/><text class="t inv" x="80" y="167" dy=".35em" text-anchor="middle">10</text><circle class="n rb-b" cx="36" cy="231" r="17"/><text class="t inv" x="36" y="231" dy=".35em" text-anchor="middle">NIL</text><circle class="n rb-b" cx="124" cy="231" r="17"/><text class="t inv" x="124" y="231" dy=".35em" text-anchor="middle">NIL</text><circle class="n rb-r" cx="256" cy="167" r="17"/><text class="t inv" x="256" y="167" dy=".35em" text-anchor="middle">15</text><circle class="n rb-b" cx="212" cy="231" r="17"/><text class="t inv" x="212" y="231" dy=".35em" text-anchor="middle">NIL</text><circle class="n rb-b" cx="300" cy="231" r="17"/><text class="t inv" x="300" y="231" dy=".35em" text-anchor="middle">NIL</text><circle class="n rb-b" cx="432" cy="103" r="17"/><text class="t inv" x="432" y="103" dy=".35em" text-anchor="middle">30</text><circle class="n rb-b" cx="388" cy="167" r="17"/><text class="t inv" x="388" y="167" dy=".35em" text-anchor="middle">NIL</text><circle class="n rb-b" cx="476" cy="167" r="17"/><text class="t inv" x="476" y="167" dy=".35em" text-anchor="middle">NIL</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Red-black tree after inserting 10, 20, 30, 15, 13, with NIL leaves; black-height 2</figcaption></figure>

Asked: [7 marks] (Dec 2022) Explain Red Black Trees and discuss their properties

Last-minute revision

• Maximum nodes in a binary tree of height $h$ is $2^{h+1}-1$.
• BST inorder is ascending; two-child deletion uses the inorder successor.
• AVL: $BF=h_L-h_R\in\{-1,0,+1\}$; LL, RR, LR, RL.
• Heap: children $2i+1$, $2i+2$; insert, delete $O(\log n)$; build $O(n)$.
• B-tree of order 5: at most 4 keys; 5 keys split, middle goes up.
• Red-black: root black, no red-red, equal black-height.
• Huffman "data structures": 46 bits against 120.
• Extended tree: $n$ internal, $n+1$ external; $E=I+2n$.

Memory hooks

• Height goes down, depth goes up to the root.
• AVL rotation name is the path of the new key: LL, RR, then zig-zag LR, RL.
• Postorder's last is the root, inorder splits the sides.

Coverage checklist

• Definitions - Height, depth, order, degree etc: differences, definitions, extended tree, internal nodes, maximum nodes.
• Binary Search Tree - Operations, Traversal, Search: BST builds, code, traversals, expression tree.
• AVL Tree: all four AVL questions.
• Heap: heap operations.
• Applications and comparison of various types of tree: expression tree, memory, Huffman.
• Introduction to forest: definition.
• multi-way Tree: definition.
• B tree: order 5 construction.
• B+ tree: definition.
• B* tree and red-black tree: red-black properties.