Binary Search Trees, Deletion and AVL Balancing

A binary search tree or BST, is a binary tree that organizes keys according to an ordering rule. For each node with key k, every key in its left subtree is smaller than k and every key in its right subtree is larger than k. If duplicates are permitted, the implementation must adopt a consistent policy, such as storing a count in the node or always directing an equal key to one chosen side.

The invariant applies to entire subtrees, not only to immediate children. A left child smaller than its parent does not make a valid BST if a deeper node in the left subtree exceeds the parent. This global range property enables search to discard one whole subtree after each comparison.

Searching and Extremes

Search begins at the root. If the target equals the current key, it succeeds. If the target is smaller, it continues in the left subtree; if larger, in the right subtree. Each step follows one edge, so the running time is O(h), where h is tree height. Space is O(1) for an iterative search and O(h) for a recursive search.

The minimum key is found by following left children until no left child exists. The maximum follows right children. These operations also take O(h). Inorder traversal visits left subtree, node and right subtree and therefore produces keys in sorted order.

A balanced BST with n nodes has height O(log n), making search efficient. An ordinary BST does not guarantee balance. Inserting already sorted keys can create a chain of height n - 1, reducing search to O(n). The height, rather than the name of the structure, determines performance.

Insertion

Insertion follows the same comparisons as an unsuccessful search. Starting at the root, move left or right according to the new key until reaching a missing child position, then attach the new leaf there. The search-tree invariant holds because every comparison has narrowed the permitted key range for that position.

Insertion costs O(h). A recursive version returns the root of the possibly changed subtree, which makes insertion into an empty position and later balanced-tree rotations convenient. An iterative version tracks the prospective parent and then connects the node.

Duplicate handling belongs to the public contract. Rejecting duplicates models a set. Storing a multiplicity supports a multiset without creating chains of equal nodes. Directing equals consistently to one side also works, but searches, deletion and validation must use the same non-strict inequalities.

Successors and Predecessors

The inorder successor of a key is the next greater key. If a node has a right subtree, its successor is the minimum node in that right subtree. If no right subtree exists and parent links are available, move upward until leaving a left-child relationship; that ancestor is the successor. The predecessor is symmetric: use the maximum of the left subtree or move upward until leaving a right-child relationship.

These operations support ordered iteration, range queries and deletion. They illustrate that the BST stores a total order through local tree structure.

BST Deletion

Deletion first searches for the target and then handles its number of children.

Leaf

A leaf has no child subtree to preserve. Disconnect it from its parent. If it is the root and the only node, the root becomes null.

One Child

A node with one child is replaced in its parent by that child. Every key in the child subtree already lies in the correct range, so bypassing the removed node preserves order. If the removed node is the root, its child becomes the new root.

Two Children

Both subtrees must remain. One common method chooses the inorder successor, which is the minimum node of the right subtree. Copy or transplant the successor’s key and value into the target position, then delete the successor from its original location. The successor has no left child, so the second deletion is a leaf or one-child case. The inorder predecessor, the maximum of the left subtree, works symmetrically.

With key-value entries, all associated payload needed to preserve the mapping must move together. In implementations where node identity matters, transplanting nodes may be preferable to copying only the key. Parent references, subtree sizes and other metadata must also be updated.

Deletion is O(h): one search path plus a path to a successor or predecessor. Careful tests include deleting the root in all three cases, deleting a missing key and deleting until the tree becomes empty.

Validating the Search-Tree Invariant

Checking only each node against its children is insufficient. A correct validator carries an allowed range downward. A left recursive call receives an upper bound of the parent key and a right call receives a lower bound. Every visited key must lie within its permitted bounds under the duplicate policy.

Another approach performs inorder traversal and verifies that the resulting sequence is strictly increasing or nondecreasing when duplicates are represented as nodes. Range validation usually detects the exact location and violated bound more directly.

AVL Trees

An AVL tree is a self-balancing binary search tree. For every node, the heights of the left and right subtrees differ by at most one. Under the convention

balanceFactor = height(left) - height(right)

the permitted balance factors are -1, 0 and 1. A positive factor means left-heavy and a negative factor means right-heavy. Some implementations reverse the subtraction; their rotation conditions must reverse signs consistently.

The AVL constraint limits height to O(log n), so search, insertion and deletion are O(log n) in the worst case. It does not require equal subtree sizes or a perfect shape. It bounds height difference locally at every node.

Nodes commonly store height metadata. With an empty subtree assigned height -1, a leaf has height zero; with an empty height of zero, a leaf has height one. Either convention works. After a structural change, a node’s height becomes one plus the maximum child height.

Rotations

A rotation is a local restructuring that reduces height imbalance while preserving inorder key order. It changes parent-child relationships among a few nodes and reconnects an intermediate subtree in the only position allowed by its key range.

Right Rotation and the LL Case

Suppose node z is too left-heavy and the new key lies in the left subtree of z’s left child y. This is an LL imbalance. A right rotation moves y above z. The former right subtree of y becomes the left subtree of z. Keys remain ordered because those intermediate keys are greater than y and smaller than z.

Inserting 30, 20, 10 creates this case. Rotating right at 30 makes 20 the subtree root, with 10 left and 30 right.

Left Rotation and the RR Case

When z is too right-heavy and growth occurred in the right subtree of its right child, an RR imbalance exists. A left rotation moves that right child above z and its former left subtree becomes z’s right subtree. Inserting 10, 20, 30 produces a subtree rooted at 20 after rotation.

Double Rotations

An LR case is left-heavy at z, but growth occurred in the right subtree of the left child. First rotate the left child left, converting the shape into LL, then rotate z right. An RL case is symmetric: rotate the right child right and then rotate z left.

After a rotation, heights must be recomputed from lower nodes upward. The node moved downward is updated before the node moved upward. The rotated subtree root must also be reattached to its former parent or returned to the recursive caller; otherwise, a correct local rotation can become disconnected from the overall tree.

AVL Insertion

AVL insertion first performs ordinary BST insertion. As recursion returns or an ancestor path is retraced, update each height and calculate its balance factor. The first unbalanced ancestor is repaired according to the direction of the inserted key or the child’s balance factor.

For insertion, one appropriate single or double rotation at the lowest unbalanced ancestor restores the height of that subtree sufficiently that higher ancestors remain balanced. The complete operation follows a logarithmic path and performs constant rotation work, giving O(log n) time.

AVL Deletion

AVL deletion begins with ordinary BST deletion, but removing a node may shorten a subtree. Heights are updated while returning toward the root. Any ancestor whose factor leaves the allowed range is rebalanced.

Deletion cases are classified using child balance factors rather than the deleted key, which may no longer reveal the direction of height loss. If a node is left-heavy, a nonnegative left-child factor calls for a right rotation; a negative left-child factor calls for LR. Right-heavy cases are symmetric.

Unlike insertion, deletion may require repairs at several ancestors. A rotation can reduce the repaired subtree’s height, causing the next ancestor to become unbalanced. The algorithm must therefore continue all the way toward the root. It remains O(log n) because AVL height is logarithmic and each visited ancestor requires constant work.

Ordered-Tree Operations and Tradeoffs

A BST can answer floor, ceiling, predecessor, successor and range queries efficiently. A range traversal prunes a left subtree when the node key is already below the lower bound and prunes a right subtree when it exceeds the upper bound. Its cost is O(h + k) for k reported entries in a balanced tree.

AVL trees provide strict lookup guarantees but perform rotations and height maintenance during updates. Other balanced trees use different constraints. A hash table may offer expected constant-time exact lookup but does not naturally provide sorted traversal or range queries. The correct structure depends on whether the application needs order, worst-case bounds, update frequency and memory characteristics.

A robust AVL checker verifies three facts at every node: all keys obey inherited BST bounds, stored height equals the value derived from child heights and the balance factor lies between -1 and 1. This independent validation catches errors that ordinary successful searches may leave hidden.