Ontological Layer: Hierarchical Data Organization

Trees & Heaps

Branching Logic and Priority Structures

The Escape from Linearity

Linear structures restrict elements to a single successor. In Realm 05, data gains the power of hierarchy. A single node can branch into multiple descendants, transforming an O(N) search into an O(log N) traversal. By enforcing strict mathematical relationships between parents and children, we create Binary Search Trees for rapid retrieval, Min/Max Heaps for absolute priority, and AVL Trees to combat the inevitable degradation of imbalance.

LINEAR DATA → MULTIPLE DESCENDANTS → HIERARCHY (TREE) → ORDERING RULE (BST) vs PRIORITY RULE (HEAP) → HEIGHT IMBALANCE → ROTATION (AVL) → O(LOG N) EFFICIENCY

The 12 Structural Nodes

Ontological Mapping: From Roots to Multiway Branches

GROUP 01 (A)

Tree Terminology

Root, Parent, Child, Sibling
Internal nodes vs Leaves
Edges, Depth, and Height
Binary restriction (Max 2 children)

GROUP 01 (B)

Tree Traversals

Preorder (Root, L, R)
Inorder (L, Root, R)
Postorder (L, R, Root)
Level-order (Breadth-First)

GROUP 02

Binary Search Trees

Left < Root < Right property
O(h) Search, Insert, Delete
Inorder traversal yields sorted data
Susceptible to skew (O(N) worst case)

GROUP 03 (A)

Max-Heap Concept

Parent ≥ Children property
Maximum element always at Root
Complete binary tree structure
Basis for descending Priority Queues

GROUP 03 (B)

Min-Heap Concept

Parent ≤ Children property
Minimum element always at Root
O(1) access to smallest element
Basis for ascending Priority Queues

GROUP 03 (C)

Array Representation

Level-order mapping to array
Left Child = 2i + 1
Right Child = 2i + 2
Parent = floor((i-1)/2)

GROUP 03 (D)

Heapify Operations

Restoring heap property after Insert/Delete
Sift-Up (Bubble up) for Insertion
Sift-Down (Sink) for Deletion
O(log N) operation time

GROUP 04 (A)

The Balancing Problem

Sequential inserts cause skew
Tree degrades into a Linked List
Search degrades from O(log N) to O(N)
Motivation for self-balancing structures

GROUP 04 (B)

AVL & Balance Factor

Strictly balanced BST
BF = Height(L) - Height(R)
Valid BF range: {-1, 0, 1}
Violation triggers structural rotation

GROUP 04 (C)

AVL Rotations

LL Case → Single Right Rotation
RR Case → Single Left Rotation
LR / RL Cases → Double Rotations
O(1) time to restore global balance

GROUP 04 (D)

B-Trees (Multiway)

Multiple keys per node
Multiple children per node
Massively reduces tree height
Optimized for Disk/Database access

FINAL PROTOCOL

12 — The Hierarchical Laboratory

1. TRACE INORDER(ROOT)

2. CHECK HEAP PROPERTY: P_idx = (i-1)/2

3. DETECT AVL IMBALANCE (BF > 1) -> ROTATE

[1] TRACE TRAVERSAL [2] BUILD BST [3] HEAPIFY ARRAY [4] PERFORM AVL ROTATION [5] ANALYZE COMPLEXITY

Hierarchies introduce a trade-off: organization requires maintenance. Inserting into a BST is fast, but only if you mathematically enforce balance through rotations. A Heap guarantees the highest priority element is always accessible, but requires sift-operations to maintain its structure. Understanding these maintenance costs is the key to algorithmic efficiency.

SIMULATION RUNNING