api: "YAML JSON TOON Database"
version: "1.0.0"
format: "json"
dataset:
  id: 25
  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: 0
  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)"