April 2021
A binary search tree (BST) is an implementation of a dynamic set (set with changing elements). Each node x in the tree satisfies the following property: each node in the left subtree of x has a key value less than or equal to that of x; each node in the right subtree of x has a key value greater than or equal to that of x.
All binary search tree operations take O(h) time to run in the worst case, where h is the height of the tree.
To search for a particular node p in a BST, start by checking whether the current node x (initialized to the root node) matches p. If not, check whether p.key < x.key. If this is true, recursively search the left child of x. Otherwise, recursively search the right child x.
To find the minimum node, starting at the root node, repeatedly traverse down the left subtree until a leaf is encountered. This leaf is the minimum node. To find the maximum, repeatedly traverse down the right subtree.
To find the successor (next larger node) of a node x, start be checking whether x has a right subtree. If so, then the successor is just the minimum node in the right subtree of x. Otherwise, the successor is the lowest ancestor of x whose left child is also an ancestor of x. The proceedure for finding the predecessor is symmetrical.
To insert a node z into a BST, starting at the root node, traverse down the tree in the following manner: go down the left subtree of x if z.key < x.key, otherwise go down the right subtree. Repeat until a leaf node is encountered, and set z as the appropriate children of this leaf node.
To delete a node z from a BST is slightly more intricate. The computation is organized into three cases. If z has no left child, then replace z with its right child (which may or may not be a node). Else if z has only one (left) child, then replace z with its left child. If none of these are true, then find the predecessor of z and call it y.