api: YAML JSON TOON Database
version: 1.0.0
format: yaml
dataset:
  id: 502
  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."
  category: Data Structures
  category_slug: data-structures
  tags: trees,bst,avl,red-black,b-tree,trie,data-structures,algorithms
  view_count: 2
  created_at: 1781275786
  updated_at: 1781275786
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)