Data Structures · topic
Binary search tree search, insertion and deletion in all three cases, inorder successor and predecessor, height bounds, BST from a preorder, insertion orders, valid search paths, and AVL trees (beyond the named syllabus): balance factor, the four rotations, insertion traces and the minimum nodes for a height.
A binary search tree (BST) is a binary tree that keeps its keys in order, so that searching can discard one whole subtree at every step. It supports the dynamic-set operations search, minimum, maximum, successor, predecessor, insert and delete, each in time proportional to the height of the tree.
Search, insertion and deletion in a binary search tree take time proportional to the tree's height h. Inserting keys in sorted order builds a path of height n - 1, so an unbalanced BST can degrade to Θ(n) per operation.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
