Binary Search Trees

A binary search tree is a binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger. It matters because that rule gives a structure that answers ordered questions, such as the next key or every key in a range, while still changing cheaply, which neither a hash table nor a sorted array does. The topic starts with the ordering rule and the single descent it allows, then follows a search and an insert step by step. It turns next to the validity check that compares only children and misses a key out of place deeper down, and to how the order keys arrive in decides the tree's height. It then deletes a node with two children using its successor, implements the tree in three languages alongside Java's balanced TreeMap, compares the tree with its two rivals, and ends with an exercise on exam scores.