api: YAML JSON TOON Database version: 1.0.0 format: yaml dataset: id: 2506 slug: tree-data-structures title: Tree Data Structures description: "Complete reference of tree data structures: binary trees, BST, AVL, Red-Black, B-trees, B+ trees, segment trees, and trie." summary: "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_when: - You need a tree for ordered data, indexing or prefix search. - You are comparing balanced search trees. caveats: - 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. related: - complexity-analysis - graph-algorithms - spatial-data-structures - file-systems entry_count: 8 fields: - section: tree_types field: name type: string example: Binary Tree - section: tree_types field: type type: string example: Base Structure - section: tree_types field: properties type: object example: "{nodes,height,search,insert}" - section: tree_types field: use_cases type: array example: "[3 items]" - section: tree_types field: notes type: string example: Simplest tree form; all other binary trees are … - section: complexity_summary field: "*" type: object example: "{operation,avl,red-black,b-tree}" category: Data Structures category_slug: data-structures tags: trees,bst,avl,red-black,b-tree,trie,data-structures,algorithms view_count: 48 created_at: 1777673262 updated_at: 1777673262 data: tree_types: - name: Binary Tree type: Base Structure properties: 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 use_cases: - Expression trees - Huffman coding - Binary heap base notes: Simplest tree form; all other binary trees are specialized variants - name: Binary Search Tree (BST) type: Search Structure properties: ordering: Left subtree < node < right subtree search: O(h) average O(log n), worst O(n) if unbalanced insert: O(h) delete: O(h) use_cases: - Search - Sorting (in-order traversal) - Symbol tables notes: Degenerates to linked list if insert order sorted; balancing needed for guaranteed O(log n) - name: AVL Tree type: Self-Balancing BST properties: 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 use_cases: - Frequent lookups with occasional inserts/deletes - Database indexing - In-memory search structures notes: Strictly balanced (height difference ≤1); fewer rotations than Red-Black; slightly slower inserts but faster lookups - name: Red-Black Tree type: Self-Balancing BST properties: 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 use_cases: - General-purpose balanced tree - Java TreeMap/TreeSet - "C++ std::map/set" - Linux kernel notes: Less strict balancing than AVL → fewer rotations on insert/delete; better for write-heavy workloads - name: B-Tree type: Balanced Multi-Way Tree properties: 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) use_cases: - Databases (indexes) - Filesystems (NTFS, ext4, HFS+) - Large datasets on disk notes: Designed for block-oriented storage; reduces disk seeks; M typically 50-200 depending on block size - name: B+ Tree type: B-Tree Variant properties: 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 use_cases: - Database indexes (MySQL InnoDB, PostgreSQL, Oracle) - Filesystem directories notes: Better for range queries and full scans than B-tree; internal nodes more compact → more keys in memory - name: Trie (Prefix Tree) type: String Search Tree properties: 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 use_cases: - Autocomplete - Spell check - IP routing tables (longest prefix match) - Dictionary implementations notes: "Compressed variants: Radix tree (compact edges), Ternary Search Tree (space-efficient)" - name: Segment Tree type: Range Query Tree properties: purpose: Query associative operations over intervals (sum, min, max) build: O(n) query: O(log n) update: O(log n) use_cases: - Range sum/min/max queries - Range updates with lazy propagation - Computational geometry notes: 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)