Binary search tree

A binary search tree (BST) is a binary tree containing keys on the internal nodes and nothing on external nodes. For each internal node, the keys in the left subtree are less than its key and the keys in the right are greater than. An in-order traversal of the tree gives the keys in increasing order.

To find a key in a BST, start at the root. If the key is equal to the root key, the item is found, if it is less than recursively search the left subtree, if it is greater than recursively search the right subtree. If an external node is reached the key is not found.

Insertion

Search the tree for the new key, then replace the external node with a new node containing the new key and give it two empty children.

Deletion

Search for the key to remove. If it has no internal children just replace it with an empty node. If it has one internal child, replace it with that child. If the node has two internal children, find the next node using an in-order traversal, then replace the removed node with it.

Performance

Space $O(n)$, height is best case $O(\log n)$ worst case $O(n)$, and search, insertion and deletion are $O(h)$ where $h$ is the height.

AVL trees

AVL trees are balanced binary trees. They are balanced regardless of insertion order. It achieves this using the height balance property, which states the difference in height between internal nodes and their internal children is at most 1. The height of an AVL tree storing $n$ keys is $O(\log n)$.

Rotations

Inserting into an AVL tree works the same as a binary tree, but if the insertion makes the tree unbalanced it needs to be rotated to balance it again. Rotations allow re-balancing the tree without violating the BST property.

Performance

AVL trees take $O(n)$ space and searching, insertion and removal take $O(\log n)$ time. A single restructuring takes $O(1)$ time with a linked-structure binary tree.