tag

#balanced-tree

5 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Scapegoat Tree Search

Scapegoat Tree Search Scapegoat tree search uses the ordinary binary search tree search rule. The tree keeps logarithmic height by rebuilding unbalanced subtrees after updates, rather than storing balance information in each node. The search procedure does not rebuild anything. It benefits from the height guarantee maintained by insertions and deletions. Problem Given a scapegoat tree with root root and target key x , find a node such that $$...
algorithms searching scapegoat-tree balanced-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

AVL Tree Search

AVL Tree Search AVL tree search follows the same decision process as binary search tree search, but operates on a tree that maintains strict height balance. For every node, the height difference between left and right subtrees is at most one. This invariant ensures that the tree height remains logarithmic in the number of nodes. Problem Given an AVL tree with root root and a target key x , find...
algorithms searching avl-tree balanced-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Weight Balanced Tree Search

Weight Balanced Tree Search Weight balanced tree search uses the ordinary binary search tree search rule, but the tree shape is maintained by subtree size constraints. Each node stores or can derive the size of its subtree. Insertions and deletions use these sizes to detect imbalance and restore balance with rotations. Search itself only follows key comparisons. Problem Given a weight balanced tree with root root and a target key...
algorithms searching weight-balanced-tree balanced-tree
Wiki › Algorithms › 02. Data Structures › 2. Advanced Data Structures and Operations ›

2.1 Balanced Search Trees

2.1 Balanced search trees, 65 index slug name 1 balanced-search-tree Balanced Search Tree 2 avl-tree AVL Tree 3 avl-insert AVL Insert 4 avl-delete AVL Delete 5 avl-rotation AVL Rotation 6 avl-balance-factor Balance Factor 7 red-black-tree Red Black Tree 8 red-black-insert Red Black Insert 9 red-black-delete Red Black Delete 10 red-black-properties Red Black Properties 11 aa-tree AA Tree 12 aa-tree-skew AA Tree Skew 13 aa-tree-split AA Tree Split 14 treap Treap...
algorithms data-structures trees balanced-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Red Black Tree Search

Red Black Tree Search Red Black tree search uses the same traversal rule as a binary search tree, while relying on structural constraints enforced by node colors to keep the tree approximately balanced. Each node is marked red or black, and the tree satisfies invariants that bound its height. This ensures predictable logarithmic search time without strict balancing. Problem Given a red black tree with root root and a target...
algorithms searching red-black-tree balanced-tree