Binary Search Trees

3.1 Definition of Binary Search Tree (BST)

Binary Search Tree (BST) is a binary tree that has the following properties:

• For any node, its left subtree contains only nodes with keys less than the node's key.
• For any node, its right subtree contains only nodes with keys greater than the node's key.
• Both subtrees of each node are also binary search trees.

Example BST:

BST stands for Binary Search Tree. It's basically a way of organizing data in a "tree" structure that allows for super fast searching. The tree structure is essentially a sneaky/smart way of sorting elements.

In-order Traversal

The task of traversal is to form a list of nodes (or data from nodes, which is terminology and can matter in practice) in a certain way. In-order (symmetric) traversal means that the root of the tree is placed between the results of the corresponding traversals of the left and right subtrees.

Together with the binary search tree property (which is about inequalities, see theory), this tells us that in-order traversal of a binary search tree gives us a sorted list of nodes — awesome! Here's how the traversal of the previously defined tree looks:

3.2 Working Principles and Properties of BST

Working Principles:

• Data Organization: BST organizes data to allow efficient searching, insertion, and deletion of elements.
• Recursive Structure: Each node in a BST follows the same rules as the root, making the structure recursive.
• Balance: To ensure optimal performance, a BST should be balanced, meaning the heights of the left and right subtrees should be about the same.

Properties of BST:

• Orderliness: At any given moment, you can traverse the tree in "in-order" (left subtree → current node → right subtree) to get all elements in sorted order.
• Operation Time:
  • On average, search, insert, and delete operations take O(log n), where n is the number of nodes.
  • In the worst-case scenario (if the tree is unbalanced), operation times can reach O(n).
• Unique Keys: All keys in a BST must be unique to maintain order.

3.3 Basic Operations

1. Insertion:

How It Works:

• Start at the root node.
• Compare the new node's key with the current node's key.
• If the new key is smaller, go to the left subtree; if larger, go to the right.
• Repeat the process until finding a suitable spot for the new node (either the left or right child is absent).

Algorithm:

1. If the tree is empty, the new node becomes the root node.
2. Otherwise, recursively find the right spot and add the new node.

2. Deletion:

How It Works:

• Find the node to delete.
• Consider three cases:
• The node is a leaf (has no children): simply remove the node.
• The node has one child: replace the node with its child.
• The node has two children: find the smallest node in the right subtree (or the largest in the left), copy its value to the node being deleted, and recursively delete the smallest node in the right subtree.

Algorithm:

1. Find the node with the given key.
2. Depending on the case, perform the corresponding deletion and node rearrangement.

3. Search:

How It Works:

• Start at the root node.
• Compare the searched node's key with the current node's key.
• If the key matches, return the node.
• If the key is smaller, go to the left subtree; if larger, go to the right.
• Repeat the process until finding the node with the searched key or reaching the end of the tree (in which case the node is not found).

Algorithm:

1. If the tree is empty or the node's key matches the searched one, return the node.
2. If the searched node's key is smaller, recursively search in the left subtree.
3. If the searched node's key is larger, recursively search in the right subtree.

3.4 Example Problems Solved with BST

1. Finding an Element in a Dynamic Set

Maintain a set of numbers where you can add new elements, delete existing ones, and quickly check if a given number is in the set.

Solution with BST:

• Insert new elements into the tree.
• Delete existing elements.
• Search for elements in the tree.

Example Use:

Maintain a list of registered users in a system where users can be added and removed, and the system needs to quickly check if a user is registered.

2. Finding the Minimum and Maximum Element

Quickly find the minimum and maximum values in a data set.

Solution with BST:

• The minimum element is located in the leftmost node of the tree.
• The maximum element is located in the rightmost node of the tree.

Example Use:

Maintain a system that tracks stock prices where it is necessary to quickly find the minimum and maximum price at any given time.

3. Expression Balance Check

Given a mathematical expression, check its balance with regards to opening and closing brackets.

Solution with BST:

Use BST to store intermediate states of bracket balance checking.

Example Use:

Parsing and compiling code where it is necessary to check the correct placement of brackets in expressions.

4. Building a Dictionary

Create a data structure for storing a dictionary where words can be added, deleted, and quickly found.

Solution with BST:

• Words are added to the tree in alphabetical order.
• Search for words is done by keys.

Example Use:

Text autocorrect system where it is necessary to quickly find and correct words.