Tree Data Structures

Complete reference of tree data structures: binary trees, BST, AVL, Red-Black, B-trees, B+ trees, segment trees, and trie.

Data Structures
13 entries
2 sections
CC0 — public domain

The data

Tree types

Name	Type	Properties	Use cases	Notes
Binary Tree	Base Structure	Nodes Each node has at most 2 children (left, right) Height O(n) worst case (skewed), O(log n) balanced Search O(n) worst case Insert O(1) if position known	Expression trees Huffman coding Binary heap base	Simplest tree form; all other binary trees are specialized variants
Binary Search Tree (BST)	Search Structure	Ordering Left subtree < node < right subtree Search O(h) average O(log n), worst O(n) if unbalanced Insert O(h) Delete O(h)	Search Sorting (in-order traversal) Symbol tables	Degenerates to linked list if insert order sorted; balancing needed for guaranteed O(log n)
AVL Tree	Self-Balancing BST	Balance factor Height(left) - Height(right) ∈ {-1, 0, 1} Rotations Single (LL, RR) and double (LR, RL) Search O(log n) Insert O(log n) with rebalancing Delete O(log n) with rebalancing	Frequent lookups with occasional inserts/deletes Database indexing In-memory search structures	Strictly balanced (height difference ≤1); fewer rotations than Red-Black; slightly slower inserts but faster lookups
Red-Black Tree	Self-Balancing BST	Color Each node red or black Rules Root black Red node's children black Every path to leaf has same black-height Search O(log n) Insert O(log n) with ≤2 rotations Delete O(log n) with ≤3 rotations	General-purpose balanced tree Java TreeMap/TreeSet C++ std::map/set Linux kernel	Less strict balancing than AVL → fewer rotations on insert/delete; better for write-heavy workloads
B-Tree	Balanced Multi-Way Tree	Order M (max children per node); each node has ⌈M/2⌉ to M children Nodes Internal nodes store keys + pointers; leaves store actual data Height O(logₘ n) — very shallow due to high fan-out Disk io Minimized (nodes match disk block size)	Databases (indexes) Filesystems (NTFS, ext4, HFS+) Large datasets on disk	Designed for block-oriented storage; reduces disk seeks; M typically 50-200 depending on block size
B+ Tree	B-Tree Variant	Data location All data in leaves; internal nodes only keys + pointers Linked leaves Leaves connected via linked list (range queries efficient) Search O(logₘ n) Range query O(log n + k) where k = results count	Database indexes (MySQL InnoDB, PostgreSQL, Oracle) Filesystem directories	Better for range queries and full scans than B-tree; internal nodes more compact → more keys in memory
Trie (Prefix Tree)	String Search Tree	Structure Characters as edges; paths form words/keys Search O(k) where k = key length (independent of n) Space O(n × k) — can be high due to many nodes Prefix search O(k + p) where p = number of matches	Autocomplete Spell check IP routing tables (longest prefix match) Dictionary implementations	Compressed variants: Radix tree (compact edges), Ternary Search Tree (space-efficient)
Segment Tree	Range Query Tree	Purpose Query associative operations over intervals (sum, min, max) Build O(n) Query O(log n) Update O(log n)	Range sum/min/max queries Range updates with lazy propagation Computational geometry	Lazy propagation allows range updates in O(log n); Fenwick tree (BIT) is simpler but less flexible

Complexity summary

Operation: Search
Insert
Delete
Min/Max
Range Query
Avl: O(log n)
O(log n)
O(log n)
O(log n)
O(k + log n)
Red black: O(log n)
O(log n)
O(log n)
O(log n)
O(k + log n)
B tree: O(logₘ n)
O(logₘ n)
O(logₘ n)
O(logₘ n)
O(k + logₘ n)
Trie: O(k)
O(k)
O(k)
O(1) if stored
O(p + k)

Fetch the same bytes

The static files are identical to what the API returns, but with no rate limit and no server round trip. Use the API when you want a query and a content type; use the files when you want to cache one document.

curl "https://yjtoon.com/api/dataset/tree-data-structures?format=toon"

const res = await fetch(
  "https://yjtoon.com/static-data/dataset/tree-data-structures.toon"
);
const toon = await res.text();

Rate limit: 120 requests per minute per IP, no key and no signup. API reference →

Tree Data Structures

The data

Tree types

Complexity summary

Fetch the same bytes

Topics