Binary Search Tree (BST) Data Structure

• BST stands for Binary Search Tree.
• A binary search tree is a node-based binary tree data structure which has the following properties:
  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

BST Properties

• For any node in a BST:
  • All keys in its left subtree are less than the node's key.
  • All keys in its right subtree are greater than the node's key.
• There are no duplicate keys (this constraint can be modified).
• BSTs facilitate efficient searching, insertion, and deletion of nodes.

BST Operations

• Search: Find a node with a specific key.
• Insertion: Add a new node with a given key.
• Deletion: Remove a node with a specific key while maintaining the BST properties.
• Minimum: Find the node with the smallest key in the tree.
• Maximum: Find the node with the largest key in the tree.
• Successor: Find the node with the next larger key in the tree (inorder successor).
• Predecessor: Find the node with the next smaller key in the tree (inorder predecessor).

Search Operation

• Start at the root node.
• Compare the search key with the node's key.
• If the search key is equal to the node's key, the node is found.
• If the search key is less than the node's key, proceed recursively to the left subtree.
• If the search key is greater than the node's key, proceed recursively to the right subtree.
• If the node is NULL, the key is not in the tree.

Insertion Operation

• Start at the root node.
• Compare the new key with the node's key.
• If the new key is less than the node's key, proceed recursively to the left subtree.
• If the new key is greater than the node's key, proceed recursively to the right subtree.
• If the node is NULL, insert the new node at that position.
• Ensure that the BST properties are maintained after insertion.

Deletion Operation

• Search for the node to be deleted.
• Three cases:
  • Node has no children (leaf node): Simply remove the node.
  • Node has one child: Replace the node with its child.
  • Node has two children: Find the inorder successor (or predecessor), copy its value to the node, and delete the inorder successor (or predecessor).
• Ensure that the BST properties are maintained after deletion.

Minimum and Maximum Operations

• Minimum: Start at the root and keep going left until you reach a node with no left child. This node contains the minimum key.
• Maximum: Start at the root and keep going right until you reach a node with no right child. This node contains the maximum key.

Successor and Predecessor Operations

• Successor: The inorder successor of a node is the node with the smallest key greater than the node's key.
  • If the node has a right subtree, the successor is the minimum node in the right subtree.
  • If the node has no right subtree, go up to the nearest ancestor whose left subtree contains the node.
• Predecessor: The inorder predecessor of a node is the node with the largest key less than the node's key.
  • If the node has a left subtree, the predecessor is the maximum node in the left subtree.
  • If the node has no left subtree, go up to the nearest ancestor whose right subtree contains the node.

BST Applications

• Implementing ordered sets and maps.
• Used in compilers for symbol table management.
• Used in database indexing.
• Can be used for sorting (Tree Sort).
• Used in various search algorithms.

BST Advantages

• Efficient searching, insertion, and deletion (on average).
• Maintains sorted order of keys.
• Dynamic data structure (size can change during runtime).

BST Disadvantages

• The shape of the BST depends on the order of insertion.
• In the worst case (e.g., inserting keys in sorted order), the BST degenerates into a linked list, resulting in O(n) time complexity for search, insertion, and deletion.
• Not self-balancing, which can lead to performance issues.

Self-Balancing BSTs

• To avoid the worst-case scenario of a skewed tree, self-balancing BSTs are used.
• Examples: AVL trees, Red-Black trees, B-trees.
• Self-balancing BSTs automatically adjust their structure to maintain a balanced height, ensuring O(log n) time complexity for search, insertion, and deletion.

Time Complexity

• Average case:
  • Search: O(log n)
  • Insertion: O(log n)
  • Deletion: O(log n)
  • Minimum: O(log n)
  • Maximum: O(log n)
  • Successor: O(log n)
  • Predecessor: O(log n)
• Worst case (skewed tree):
  • Search: O(n)
  • Insertion: O(n)
  • Deletion: O(n)
  • Minimum: O(n)
  • Maximum: O(n)
  • Successor: O(n)
  • Predecessor: O(n)
• Space Complexity: O(n)

Example

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

• In the example tree:
  • The root is 8.
  • The minimum value is 1.
  • The maximum value is 14.
  • The successor of 6 is 7.
  • The predecessor of 6 is 4.