1.7. Binary Search Trees

In a binary search tree, we will argue that all of these operations are actually logarithmic, provided we maintain the binary search tree with a good structure. We will also look at an operation called find, which searches for a value and this will also be logarithmic. So, we will simultaneously be able to optimize all these 7 operations in a binary search tree.

A binary search tree (BST) is a data structure that organizes values in a way that allows for efficient searching, insertion, and deletion operations, all of which can be performed in logarithmic time under optimal conditions. The operation called 'find' allows us to search for a specific value quickly within the tree. A 'good structure' means that the tree is balanced, preventing it from becoming skewed like a linked list, which maintains efficiency.

Imagine a library where books are sorted by their titles alphabetically; if you want to find a particular book, you can quickly narrow down your search to the relevant section by skipping over many irrelevant books. A balanced binary search tree allows us to do something similar with numbers or other values.

A binary tree is just a tree with a root in which every node has either 1, 2, or 3 children. Every node we are going to assume will have a link to its parent, left child, and right child.

In a binary tree, each node can have at most two children, referred to as the left child and the right child. The tree starts with a single root node. Each node also has a connection back to its parent, allowing traversal in both directions. This structure enables the binary search tree to efficiently organize data.

Think of a family tree where each individual connects to their parents and children; similarly, a binary search tree connects each node to its parents and children, allowing us to trace back or move down in the hierarchy.

In a binary search tree, for each node with a value v, all the nodes below v, smaller than v are in the left subtree and all the values bigger than v are in the right subtree.

The property of a BST ensures that all values in the left subtree of any node are less than the node's value, while all values in the right subtree are greater. This property is maintained throughout the tree, allowing efficient searching and sorting of values.

Imagine sorting your toolbox, where tools that are smaller than a wrench go in one compartment to the left, and those larger than the wrench go to the right. This arrangement allows you to find any tool quickly based on size, similar to how values are organized in a binary search tree.

The first thing that we can do with a binary search tree is to list out its values in sorted order, which is called an in-order traversal. In-order traversal is a recursive traversal where we first walk through the left subtree, then the current node, and then the right subtree.

In-order traversal involves visiting all the nodes of a binary search tree in a specific order: descend to the leftmost node, visit the node, and then move to the right subtree. This method guarantees that the values will be retrieved in ascending order, essential for many algorithms using BSTs.

Think about how a librarian organizes books on a shelf; they would start from the leftmost book, read it, and then proceed to the right, ensuring that readers find them in alphabetical order. Similarly, in-order traversal returns the values in a sorted sequence.

Searching for a value in a binary search tree is very much like binary search. If the tree is empty, we say that it is not there; if the current node has the value, we have found it and return true. If not found, we check whether the value is smaller or larger to decide whether to search in the left or right subtree.

When searching for a value in a BST, we start at the root and decide which direction to proceed based on comparisons. If the sought value is smaller, we move left; if larger, we move right. If we reach a leaf node without finding the value, we conclude it is not present in the tree.

It's like playing a game of 20 Questions; you ask yes or no questions to narrow down the possibilities. Each guess helps you eliminate half of the remaining options, just as searching in a binary search tree progressively narrows down the search space to find a specific value.

--