What are binary search trees, and why use a balanced tree?
Short answer: In a binary search tree (BST), every node's left subtree has smaller keys and its right subtree larger keys, so search, insert and delete follow one path from the root: O(height). If keys arrive in sorted order, a plain BST degenerates into a linked list (height n, O(n) operations). Self-balancing trees (red-black, AVL) restructure with rotations to keep the height O(log n) in the worst case, and they keep keys in order (unlike hash tables), supporting in-order traversal and range queries.
#include <stdio.h>
#include <stddef.h>
struct tnode { int key; struct tnode *left, *right; };
struct tnode *bst_insert(struct tnode *root, struct tnode *n) /* n comes from a pool */
{
struct tnode **p = &root;
while (*p) p = (n->key < (*p)->key) ? &(*p)->left : &(*p)->right; /* iterative: no recursion */
n->left = n->right = NULL;
*p = n;
return root;
}
struct tnode *bst_find(struct tnode *r, int key)
{
while (r && r->key != key) r = (key < r->key) ? r->left : r->right;
return r;
}
static void inorder(const struct tnode *r) { if (!r) return; inorder(r->left); printf("%d ", r->key); inorder(r->right); }
int main(void)
{
static struct tnode pool[6];
int keys[] = { 50, 30, 70, 20, 40, 60 };
struct tnode *root = NULL;
for (int i = 0; i < 6; i++) { pool[i].key = keys[i]; root = bst_insert(root, &pool[i]); }
inorder(root); printf("| found 40: %s\n", bst_find(root, 40) ? "yes" : "no"); /* 20 30 40 50 60 70 | yes */
return 0;
}
Where balanced trees appear in systems software
- Linux: red-black trees (
rbtree) for the CFS/EEVDF run queue, hrtimers, virtual memory areas (now a maple tree), epoll; Zephyr's scalable scheduler queue. - Interval trees for overlapping ranges (memory regions, IOMMU mappings).
- B-trees and B+ trees for filesystems and databases on flash (high fan-out, fewer reads).
Traversals: in-order (sorted output), pre-order (copy/serialise a tree), post-order (free a tree), level-order (BFS with a queue). For embedded code, avoid deep recursion on unbalanced trees; use iterative traversals with an explicit stack.