Binary Search Trees

Binary Search Trees are discussed in COMP-SCI-300.

For sake of review, a binary search tree (BST) is a binary tree in which each node has a key value and satisfies the following properties:

1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtrees are also binary search trees.

Rotations

Left Rotation

Original Tree:

%% Left Rotation: BEFORE
flowchart TB
X((x)) --> A((A))
X --> Y((y))
Y --> B((B))
Y --> C((C))

After Left Rotation:

%% Left Rotation: AFTER
flowchart TB
    Y((y)) --> X((x))
    X --> A((A))
    X --> B((B))
    Y --> C((C))

Right Rotation

Original Tree

%% Right Rotation: BEFORE
flowchart TB
    X((x)) --> Y((y))
    Y --> A((A))
    Y --> B((B))
    X --> C((C))

After Right Rotation:

%% Right Rotation: AFTER
flowchart TB
    Y((y)) --> A((A))
    Y --> X((x))
    X --> B((B))
    X --> C((C))

Time Complexity

A rotation changes a constant number of references: $O(1)$ once the parent and child are known. Locating those nodes separately may cost $O(h)$ for tree height $h$.

Connections

• Topic index

Obvious technical and formatting errors repaired.