Hakupuita

Hakupuita (Finnish for “search trees”) are data structures used in computer science to store items so that they can be located quickly by a search key. Each node contains a key and, often, associated data, and nodes are connected to form a hierarchical structure in which the keys in a subtree fall within a defined range. In a binary search tree, for example, the left subtree contains keys less than the node’s key while the right subtree contains keys greater than the node’s key.

Operations commonly supported by hakupuita include search, insertion, and deletion. Performance depends on the tree’s balance: balanced hakupuita have height proportional to logarithm of the number of elements, yielding average-case times of O(log n) for these operations; unbalanced trees can degrade to O(n) in the worst case.

Common varieties include binääriset hakupuut (binary search trees), self-balancing trees such as AVL-puut (AVL trees) and punamusta-puut (red-black trees), and multiway trees like B-puut (B-trees). These structures differ in how they maintain balance and how many keys each node can hold, trading off complexity, memory usage, and access patterns.

Applications of hakupuita include implementing dictionaries and associative arrays in programming languages, database indexing, and certain filesystem indices. They are foundational for efficient key-based retrieval in both in-memory and on-disk data structures.