DSA
B-tree
high-fan-out balanced tree for disk (DDIA)
Source board
This definition comes from the board below. Open it to see the term in context.
TreesDSAMore terms from this board
- balancedh ≈ log n
- binary tree≤2 children
- BSTleft < node < right (in-order = sorted)
- complete treefilled level-by-level (→ array storage)
- heapcomplete tree, parent≤children (min) or ≥ (max)
- height hlongest root-to-leaf path
- rotationlocal re-link to rebalance
- self-balancing BST (AVL / red-black)rotations keep O(log n) worst case
- sift up/downrestore heap property
- traversalvisit all nodes (in/pre/post-order = DFS; level-order = BFS)
- treehierarchical nodes, one root, no cycles
- triecharacter-keyed prefix tree (O(len) lookup)