{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "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": 1,
        "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) \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"
                },
                "use_cases": [
                    "Frequent lookups with occasional inserts\/deletes",
                    "Database indexing",
                    "In-memory search structures"
                ],
                "notes": "Strictly balanced (height difference \u22641); 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 \u22642 rotations",
                    "delete": "O(log n) with \u22643 rotations"
                },
                "use_cases": [
                    "General-purpose balanced tree",
                    "Java TreeMap\/TreeSet",
                    "C++ std::map\/set",
                    "Linux kernel"
                ],
                "notes": "Less strict balancing than AVL \u2192 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 \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)"
                },
                "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\u2098 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 \u2192 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 \u00d7 k) \u2014 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\u2098 n)",
                "O(log\u2098 n)",
                "O(log\u2098 n)",
                "O(log\u2098 n)",
                "O(k + log\u2098 n)"
            ],
            "trie": [
                "O(k)",
                "O(k)",
                "O(k)",
                "O(1) if stored",
                "O(p + k)"
            ]
        }
    }
}