← CSC 212 Data Structures and Algorithms
Hierarchical Structures: Binary Search Trees and Balanced Trees
Notes
Introduction to Trees and the Binary Search Property
Non-linear hierarchical data structures allow data representation beyond simple sequential ordering. A tree consists of nodes linked by directed edges, originating from a single root node. A binary tree restricts each node to at most two children, termed the left child and right child. A Binary Search Tree (BST) imposes an invariant ordering rule: for any given node with key k, all values in its left subtree must be strictly less than k, and all values in its right subtree must be strictly greater than k.
Traversal and Algorithmic Complexity
BSTs enable in-order traversal (left, root, right), which visits nodes in ascending sorted order in O(n) time. Pre-order and post-order traversals serve serialization and expression evaluation tasks respectively. In an ideal, perfectly balanced BST, searching, insertion, and deletion operate in O(log n) time because each comparison discards half the remaining search space. However, if keys are inserted in sorted or near-sorted order without intervention, the tree degenerates into a singly linked list. Under this skewed worst-case condition, height h equals n minus one, causing operational complexity to collapse to O(n).
Self-Balancing Mechanisms
To counter worst-case degeneration, balanced tree variants such as AVL trees and Red-Black trees enforce structural invariants through tree rotations. AVL trees maintain a balance factor strictly between negative one and positive one for every node, rebalancing via single or double rotations immediately following insertions or deletions, guaranteeing predictable O(log n) boundaries.
Practical example
Consider the Kenya Revenue Authority (KRA) iTax system database indexing taxpayer identification numbers (such as KRA PINs). When a taxpayer logs into the portal to file annual returns, the authentication microservice must verify their PIN against millions of records stored across national databases.
If the registration module inserts PINs sequentially into an unaugmented BST as businesses register daily, the search tree degenerates into a linear structure. A query for a newly registered taxpayer in Nairobi would necessitate traversing through every antecedent record, taking up to 5,000,000 operations for 5,000,000 records.
By deploying a balanced tree structure (such as a B-Tree or Red-Black Tree), the system guarantees that the tree height never exceeds approximately 1.44 times log2(n). Consequently, validating a PIN across 5,000,000 Kenyan citizens requires no more than 30 comparison operations. This structural efficiency keeps taxpayer validation instantaneous and prevents server timeouts during the high-traffic June 30th tax filing deadline.
Quiz
1. What happens to the search performance of an unaugmented Binary Search Tree if elements are inserted in strictly ascending order?
2. Which traversal sequence on a valid Binary Search Tree processes the stored numeric keys in strictly ascending order?
3. How does a self-balancing AVL tree maintain its O(log n) search guarantee during dynamic insertions?
Sign in to submit and securely grade your quiz.