balanced tree
A balanced tree is a search tree that actively keeps itself short, so it never degenerates into a long vine. The motivation is the weakness of a plain binary search tree: feed it sorted data and it collapses to O(n). A balanced tree adds a rule that caps the height at about log n, which locks in O(log n) for search, insertion, and deletion no matter what order the keys arrive in.
Two famous designs show the idea. An AVL tree keeps the left and right heights of every node within one of each other — strict, so it stays very short and searches are fast. A red-black tree colors nodes red or black and enforces looser rules that still bound the height to about 2·log n — a bit taller, but cheaper to maintain, which is why it backs the ordered maps and sets in many standard libraries. Both store extra bookkeeping (a height or a color) in every node.
When an insert or delete pushes the tree out of balance, it is repaired with rotations: small, local rearrangements that pivot a node with its child to redistribute the subtrees and reduce the height, without breaking the left-smaller / right-larger ordering. A rotation touches only a handful of pointers, so it runs in O(1), and you only ever need O(log n) of them along the path back to the root — which is how the whole structure stays cheap to keep balanced.
// x y
// / \ / \
// y C --> A x
// / \ / \
// A B B C
Node* rotateRight(Node* x) {
Node* y = x->left;
x->left = y->right;
y->right = x;
return y; // y is the new subtree root
}A single right rotation — an O(1) local repair that keeps a search tree balanced.
AVL trees stay shorter (faster lookups); red-black trees rebalance with fewer rotations (faster updates) — both guarantee O(log n).