Algoritmika 2026/27 sügis

HW3. Trees and Balanced Search

Version: 2026-08-31 14:12 EEST

Deadline: Monday, 21.09.2026, 23:59

Purpose

A search tree is correct because of its ordering invariant, but it is efficient only when its shape remains useful. This homework connects traversal, structural measurements, balancing, test-data design, and comparison-based evidence. Optional tasks investigate how a tree can adapt to a changing access distribution.

You may use the HW3 array-based BST starter for ordinary insertion, Collatz input, and small-tree text and graphical visualisation. It is intentionally incomplete: you must implement and test the required search, traversals, invariant checks, measurements, and task-specific algorithms. Its colour field is display metadata and does not make the structure a red-black tree.

Expected workload: approximately 6-8 hours for the five base tasks. Bonus tasks are not included.

AI use in HW3

Default - AI-assisted: Unless a task says otherwise, AI tools may be used for programming assistance, debugging, plotting, language improvement, and understanding technical errors. You remain responsible for testing, understanding, modifying, and explaining everything you submit.

Some tasks mark an independent reasoning, independent design, or independent prediction stage. Complete and record that stage before asking AI about it. AI may then help implement or debug your approach. Tasks marked AI encouraged deliberately allow broader assistance, but their results must still be correct, reproducible, acknowledged, and understood.

At the end of the report write AI assistance: none / minor / substantial. If it was substantial, add one sentence describing its contribution. Prompt transcripts are not normally required.

General requirements

• Submit a report in PDF or HTML and the code/source files separately.
• State whether tree height and path length count edges or nodes, and use the convention consistently.
• Test every operation before measuring it. A drawing alone is not an invariant check.
• Use recorded seeds and identical operation sequences when comparing structures.
• Keep the report concise: approximately 3-5 pages, excluding code and optional appendices.
• Include the required AI-assistance statement and acknowledge important external sources or ideas.

Base tasks

T1. Create and characterise four unbalanced BSTs (1p)

Generate Collatz sequences starting from 7, 9, and 51. Stop before a value would repeat. Insert each sequence into an initially empty unbalanced binary search tree, ignoring a key if it is already present.

For the fourth tree, search a documented interval containing at least 100,000 positive starting integers. Select the starting value that produces the longest Collatz sequence among the values you tested. Define sequence length precisely and report the searched interval and selection method. The fourth sequence must be longer than each of the three given sequences; otherwise extend the interval.

These are ordinary unbalanced BSTs. Do not rotate, rebalance, or otherwise rearrange a tree after insertion.

Implement or adapt and test:

• search and insertion;
• pre-order, in-order, post-order, and breadth-first traversal;
• node count, tree height, width at every depth, and the distribution of successful-search depths.

Show the three final trees compactly. Trace one successful and one unsuccessful search in the tree starting from 51. State the BST invariant precisely and verify it automatically after every insertion.

Repeat the BST construction, invariant checks, all four traversals, and structural measurements for this large sequence. Do not print or draw the entire large tree in the report. Instead, verify the complete traversal outputs in code and report a compact summary: starting value, sequence length, largest reached value, node count, height, maximum width, and the successful-search depth distribution. Compare the large tree with the three small trees.

Deliverable: the three given sequences and the selected fourth starting value, compact drawings of the three small trees, traversal checks for all four trees, structural comparison table, two search traces, invariant checker, documented search for the fourth sequence, and a brief explanation of why in-order traversal has a special property in a BST.

T2. Maximum path sum: local return versus global answer (1p)

Implement the maximum path-sum algorithm for a binary tree whose values may be positive or negative. A path may start and end at any nodes, need not pass through the root, and may not repeat a node.

Create mixed-sign test trees from the three Collatz BSTs in T1 as follows:

1. copy the completed tree without changing its shape or child links;
2. enumerate its nodes in breadth-first order, starting from position 1;
3. replace the value x at every third position by -x and leave the other values unchanged.

Do not reinsert or reorder nodes after changing the signs. The resulting structures are ordinary binary trees and deliberately no longer BSTs: their shape comes from the original Collatz insertion order, while their signed values are labels used for the path-sum problem. This distributes negative values across different levels and branches instead of placing all negative keys in one BST region.

Return both the maximum sum and one corresponding path. Explain the difference between:

• the best one-ended path that a recursive call may pass to its parent; and
• the best complete path found anywhere in the tree.

Independent reasoning: Before consulting AI about the recurrence or solution, write down what information one recursive call must return to its parent and what information must be maintained for the complete tree. Include this initial formulation in the report.

Test the three mixed-sign Collatz trees and at least four small hand-built trees, including an all-negative tree. For trees of at most 12 nodes, validate the result against a deliberately slow method that examines all endpoint pairs.

Deliverable: sign-transformation code and checks, algorithm, reconstructed paths, tests, exhaustive validator, and at most 160 words explaining the recurrence and why the transformed trees are not BSTs.

T3. Trace AVL rebalancing (1p, approachable)

Use this 14-value prefix of the Collatz sequence starting at 59, from 59 through 58:

59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58

Insert the values into an initially empty AVL tree. You may trace carefully by hand or write a program. A complete AVL implementation is not required for the hand-traced solution.

After every insertion, record the tree height and verify both the BST ordering invariant and the AVL condition that every node has balance factor -1, 0, or 1. Whenever rebalancing is required:

• classify the case as LL, LR, RL, or RR;
• show the affected subtree immediately before and after rebalancing;
• count every single rotation, so a double rotation counts as two.

Build an ordinary unbalanced BST from the same 14-key prefix. Show both final trees and compare them by height and mean successful-search depth. Explain briefly why the AVL condition keeps search depth logarithmic.

If you use a program, additionally run both the AVL tree and the ordinary unbalanced BST on the complete 33-value Collatz sequence from 59 through 1. Check the invariants automatically after every insertion. Report final height, mean successful-search depth, the number of rebalancing events of each type, and the total number of single rotations. You do not need to draw the two complete 33-node trees.

Deliverable: compact 14-row insertion/invariant table, all rebalancing traces for the prefix, final 14-node AVL tree, final 14-node unbalanced BST, structural comparison, and at most 120 words of explanation. Programmatic solutions also include the compact full-sequence results.

T4. Change the input, assess the tree (1p, approachable)

This task changes the data order used to construct the tree and then assesses the resulting structure. The tree itself does not adapt after construction.

Use the 25 distinct keys from the complete Collatz sequence starting at 51. Build three ordinary unbalanced BSTs from exactly the same key set, without rotations:

1. the original Collatz order from T1;
2. one random permutation produced with seed 2026;
3. a median-first order: sort the keys, output the median, and then recursively output the medians of the left and right parts. Use the lower median whenever a part has even length.

Before constructing the trees, predict their relative quality. Choose one primary quality measure and justify it briefly: height, mean successful-search depth, or 95th-percentile successful-search depth.

For every tree, verify that inorder traversal returns the same sorted key set. Record height, mean and 95th-percentile successful-search depth, and the total number of key comparisons used during construction. Rank the three trees using your chosen primary measure and explain any disagreement among the measures.

The median-first order may use the complete sorted key set in advance. It is an offline construction order, not a dynamically balanced or self-adjusting tree.

Deliverable: the three insertion orders, prediction, correctness checks, compact three-row comparison table, final ranking, and at most 120 words of interpretation. No timing or new tree implementation is required.

T5. How much can local order damage an unbalanced BST? (1p, experimental)

Use the same unbalanced BST implementation throughout this task. For every experiment start with the same distinct keys 0, ..., n-1. Divide them into consecutive blocks of length L, randomly permute the blocks, and concatenate them while preserving increasing order inside every block. The final block may be shorter.

Thus L=1 gives a random permutation. Larger L values create longer increasing runs, but the complete insertion order is not sorted. This keeps the key set and implementation fixed while changing only local order.

Use:

• n = 1_000 and n = 10_000;
• L = 1, 4, 16, 64, 256;
• five fixed random seeds for every (n, L) pair.

Use iterative insertion and search so that a language recursion limit is not mistaken for an algorithmic limit. Define the root depth as 0 and tree height as the maximum node depth. For every constructed tree:

• verify the BST invariant and verify that an inorder traversal returns exactly 0, ..., n-1;
• count all key comparisons made while constructing the tree;
• search for every inserted key once and record the mean and 95th-percentile number of key comparisons;
• record the tree height.

Independent prediction: Before running the experiment or asking AI to predict its outcome, record how increasing L should affect height, construction work, and search cost. Include the original prediction in the report and explain discrepancies yourself after measuring.

Use L=1 as the baseline. For each n, identify the smallest tested L for which the mean successful-search comparison count, averaged over the five seeds, is at least twice the corresponding baseline; report that no tested value reached the threshold if necessary.

Finally, explain and verify the following relationship for your counting convention: the number of comparisons needed to insert a node equals its final depth, while a successful search for it needs its depth plus one comparisons. Timing is not required in this task.

Deliverable: generator and seeds, correctness checks, a compact table summarising all cases across the five seeds, one plot of search comparisons against L, the two-times-threshold result, and at most 200 words interpreting why short increasing runs change the tree shape and cost.

Bonus tasks

B1. Complete balanced tree implementation (bonus 2p)

Implement full AVL or red-black insertion and deletion from scratch, including an automatic invariant checker. Test all three T4 insertion orders and many additional random and structured update sequences against a set/dictionary reference model. Include deletion of a leaf, a one-child node, a two-child node, and the root. Check the ordering and balancing invariants after every update and report the first failing operation if a test fails.

Deliverable: implementation, invariant checker, reference-model comparison, seeds, and a compact summary of the tested workloads.

B2. How much upward adjustment is enough? (bonus 2p, experimental)

AI encouraged: You may use AI tools for algorithm, implementation, testing, and experimental-design ideas. The fixed generator and operation counts determine whether the resulting method works; you must be able to explain and defend it.

Unlike T4, this task fixes the initial construction and tests a different idea: adapting the tree during the access stream by moving each accessed key zero, one, two, or all possible steps towards the root.

Start every run from the same perfectly balanced BST containing the keys 0, ..., 1022. Construct it directly or insert recursive medians, always choosing the lower median first. With root depth 0, the initial tree must have root 511, contain 1023 nodes, and have height 9. Verify these facts and the ordering invariant.

After every successful search, apply one of these policies:

• k=0: do not rotate;
• k=1: rotate the accessed node towards the root at most once;
• k=2: rotate it towards the root at most twice;
• k=infinity: continue single parent-child rotations until the accessed node becomes the root. This is the move-to-root heuristic, not splaying.

Use a fresh copy of the initial tree for every policy and the exact same pre-generated access stream. Count one key comparison for every visited node and one rotation for every single parent-child rotation. Do not use running time as the primary measurement.

The following generator creates a truncated Zipf distribution. Its shape remains the same inside every phase, but a new random permutation maps probability ranks to keys at each phase boundary. Thus the identities of the hot keys change internally during one stream.

from bisect import bisect_left
from hashlib import sha256
from itertools import accumulate
import random


def changing_zipf_stream(
    n_keys=1023,
    n_queries=100_000,
    phase_length=10_000,
    s=1.2,
    noise=0.05,
    seed=2026,
):
    if (
        n_keys < 1
        or n_queries < 1
        or phase_length < 1
        or s <= 0
        or not 0 <= noise <= 1
    ):
        raise ValueError("Invalid generator parameter")

    rng = random.Random(seed)
    cdf = list(
        accumulate(1.0 / rank**s for rank in range(1, n_keys + 1))
    )
    normalizer = cdf[-1]
    stream = []

    for phase_start in range(0, n_queries, phase_length):
        rank_to_key = list(range(n_keys))
        rng.shuffle(rank_to_key)
        phase_size = min(phase_length, n_queries - phase_start)

        for _ in range(phase_size):
            if rng.random() < noise:
                key = rng.randrange(n_keys)
            else:
                rank = bisect_left(cdf, rng.random() * normalizer)
                key = rank_to_key[rank]
            stream.append(key)

    return stream


def stream_checksum(stream):
    data = ",".join(map(str, stream)).encode("ascii")
    return sha256(data).hexdigest()


stream = changing_zipf_stream()
print("Queries:", len(stream))
print("Checksum:", stream_checksum(stream))

With the default parameters, the checksum must be:

5ff315ca53c28d3cb6db9e2d09c178f0e07efecc96981b89d1cf844255917891

Keep all default parameters except phase_length and test 20, 50, 200, 1000, 10000. Generate each stream once before running the tree policies. For every policy and phase length report total comparisons C, total rotations R, comparisons per query, and rotations per query. Verify the BST invariant at every phase boundary.

First compare the methods as pairs (C, R) and identify any dominated method. Then evaluate C + lambda*R for lambda = 0, 1, 3. Explain why the preferred adjustment policy can change with phase length and with the assumed relative cost of a rotation.

Deliverable: policies, rotation tests, generator checksum for every stream, correctness checks, prediction table written before the experiment, compact results and plots, Pareto comparison, and at most 250 words of interpretation.

Submission checklist

• Tree/path conventions and duplicate-key policy are explicit.
• Ordering and balancing invariants are checked, not inferred from pictures.
• Compared structures receive identical operations.
• Measurements distinguish comparisons, rotations, structure, and running time where time is requested.
• Report and code/source files are uploaded separately.