Root
The only node without a parent; it is the structure’s entry point.
Algorithms · Data structures
Binary search trees and rotations
A binary search tree keeps keys in an order that guides every decision: smaller to the left, larger to the right. Its efficiency depends on the tree’s shape, not only on its number of nodes.
The property that enables search
Left subtreesmaller keys
vcurrent node
Right subtreelarger keys
For every node v: chiavi(sinistra(v)) < v < chiavi(destra(v))
The condition must hold for entire subtrees, not only for the two immediate children. For clarity, the lab rejects duplicates; a real implementation must choose and document a consistent policy.
Key consequence: an in-order traversal of a BST produces every key in increasing order.
Anatomy and vocabulary
Leaf
A node with no children. A node may also have exactly one child.
Depth
Number of edges from the root to a node. The root has depth 0.
Height
Number of levels on the longest path. Here an empty tree has height 0 and a leaf height 1.
Lab: modify the tree
Nodes are selectable. Rotations act on the selected node; search, insertion and deletion show the comparison path.
- Nodes
- 0
- Height
- 0
- Comparisons
- 0
- Shape
- —
In-order
Pre-order
Post-order
selected
visited path
promoted or changed node
Search, insertion and deletion
Search
Compare the key with the node: stop if equal, go left if smaller, right if larger.
Insertion
Follow the same path as search and attach a new leaf at the first empty pointer.
Deletion
Remove a leaf; replace a one-child node with its child; for two children, use the in-order successor.
The subtle case is deleting a node with two children. The successor is the minimum of the right subtree: it has no left child, so removing it reduces to a simpler case.
Rotations: change shape without changing order
A rotation is a local Θ(1) update. It preserves every ordering relation, so the in-order traversal remains unchanged.
Left rotation around x
x y
/ \ / \
A y → x C
/ \ / \
B C A B
Requires a right child y. y is promoted; subtree B moves from the left of y to the right of x.
Right rotation around y
y x
/ \ / \
x C → A y
/ \ / \
A B B C
This is the inverse operation. It requires a left child x and moves B from the right of x to the left of y.
A rotation does not decide where balancing is needed. AVL and red-black trees add invariants and rules that determine when and which rotations to perform.
Complexity depends on height
| Operation | Cost | Balanced tree | Worst case |
|---|---|---|---|
| Search | Θ(h) | Θ(log n) | Θ(n) |
| Insertion | Θ(h) | Θ(log n) | Θ(n) |
| Deletion | Θ(h) | Θ(log n) | Θ(n) |
| Minimum / maximum | Θ(h) | Θ(log n) | Θ(n) |
| One rotation | Θ(1) | Θ(1) | Θ(1) |
| Full traversal | Θ(n) | Θ(n) | Θ(n) |
Balanced
h = Θ(log n)Each comparison removes roughly half the candidates.
Degenerate
h = Θ(n)Already sorted insertions may create a linked list disguised as a tree.
Three depth-first traversals
In-order · LNR
Left, node, right. In a BST this yields sorted keys.
Pre-order · NLR
Node, left, right. Useful for serializing or reconstructing shape.
Post-order · LRN
Left, right, node. Useful when children must be processed before their parent.
Common mistakes
- Checking only left child < parent < right child: the constraint applies to all descendants.
- Forgetting to update the parent or root during rotation, losing an entire subtree.
- Swapping keys during rotation: keys stay put; only links change.
- Claiming every BST operation is Θ(log n): that only holds when height is logarithmic.
- Failing to define a duplicate-key policy, making the ordering invariant ambiguous.