sift up/down

Source board

This definition comes from the board below. Open it to see the term in context.

TreesDSA

More 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
• self-balancing BST (AVL / red-black)rotations keep O(log n) worst case
• traversalvisit all nodes (in/pre/post-order = DFS; level-order = BFS)
• treehierarchical nodes, one root, no cycles
• triecharacter-keyed prefix tree (O(len) lookup)