DSA
self-balancing BST (AVL / red-black)
rotations keep O(log n) worst case
Source board
This definition comes from the board below. Open it to see the term in context.
TreesDSAMore terms from this board
- B-treehigh-fan-out balanced tree for disk (DDIA)
- 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
- 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)