api: YAML JSON TOON Database
version: 1.0.0
format: toon
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[2]: "You need a tree for ordered data, indexing or prefix search.",You are comparing balanced search trees.
  caveats[2]: 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[4]: complexity-analysis,graph-algorithms,spatial-data-structures,file-systems
  entry_count: 8
  fields[6]{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}"
  category: Data Structures
  category_slug: data-structures
  tags: "trees,bst,avl,red-black,b-tree,trie,data-structures,algorithms"
  view_count: 49
  created_at: 1777673262
  updated_at: 1777673262
data:
  tree_types[8]:
    - 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[3]: 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[3]: 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[3]: 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[3]: 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[4]: 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[3]: 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[2]: "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[4]: 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[3]: 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[5]: Search,Insert,Delete,Min/Max,Range Query
    avl[5]: O(log n),O(log n),O(log n),O(log n),O(k + log n)
    "red-black"[5]: O(log n),O(log n),O(log n),O(log n),O(k + log n)
    "b-tree"[5]: O(logₘ n),O(logₘ n),O(logₘ n),O(logₘ n),O(k + logₘ n)
    trie[5]: O(k),O(k),O(k),O(1) if stored,O(p + k)