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

JSON9,979 B
YAML6,625 B · −34%
TOON5,893 B · −41%

Tree data structures with type, properties, uses and notes: binary trees, binary search trees, AVL and red-black trees, B-trees and B+ trees, tries and segment trees, plus a complexity comparison of balanced trees.

Use it when

You need a tree for ordered data, indexing or prefix search.
You are comparing balanced search trees.

Watch out for

An unbalanced binary search tree can degrade to O(n); use a self-balancing variant when input order is not controlled.
B-trees are favored on disk because they minimize reads, not because of lower asymptotic cost.

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)

Fields

The shape of this dataset, read from the data itself: every column, its type and a real value. Agents can use this to plan a query without fetching the whole document.

Section	Field	Type	Example
tree_types	`name`	string	Binary Tree
tree_types	`type`	string	Base Structure
tree_types	`properties`	object	{nodes,height,search,insert}
tree_types	`use_cases`	array	[3 items]
tree_types	`notes`	string	Simplest tree form; all other binary trees are …
complexity_summary	`*`	object	{operation,avl,red-black,b-tree}

Fetch the same bytes

The static files contain the same reference rows as the API, with no API rate limit. Live metadata, such as view counts, may differ. Use the API for content negotiation; use the static files for a cacheable snapshot.

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 →