api: "YAML JSON TOON Database"
version: 1.0.0
format: toon
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: 3
  created_at: 1781275786
  updated_at: 1781275786
data:
  tree_types
    [8]{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) \u2208 {-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 \u22642 rotations","delete":"O(log n) with \u22643 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 \u2308M\/2\u2309 to M children","nodes":"Internal nodes store keys + pointers; leaves store actual data","height":"O(log\u2098 n) \u2014 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\u2098 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 \u00d7 k) \u2014 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:
      [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)"