Binary Search Trees (BST)

Overview

• Binary Tree: General structure discussed in previous lesson.
• Binary Search Tree (BST): Special binary tree for efficient data organization.
• Purpose: Quick search and quick updates (insert/remove).

Problem Statement

• Need a data structure for a modifiable collection of any data type with:
  • Quick search for records.
  • Ability to modify the collection (insert/remove).

Data Structures for Collection

Arrays

• Operations:
  • Search: O(n) - Worst case requires scanning entire array.
  • Insertion: O(1) - Constant time if space is available.
  • Removal: O(n) - Requires shifting elements.
• If the array is filled, we create a larger array (size doubles) and copy elements: O(n).
• Dynamic Array: Insertion O(1) if space is available, O(n) if not.

Linked Lists

• Operations:
  • Search: O(n) - Worst case requires traversing all nodes.
  • Insertion: O(1) - At head, O(n) at tail.
  • Removal: O(n) - Must traverse to find the node.

Efficiency Concerns

• O(n) for search is inefficient, particularly with large datasets (e.g., populations over 100 million).
• Binary Search (on sorted arrays): O(log n) - Much faster than O(n).
  • Insertion/Removal still O(n) due to shifting elements to maintain order after insertion.

Binary Search Trees (BST)

• Definition: A binary tree where:
  • For each node, all values in the left subtree are lesser or equal.
  • All values in the right subtree are greater.
• Balanced Tree: Ensures O(log n) operations.
  • Unbalanced tree can result in O(n) operations (similar to linked list).

Properties of BST

• Search:

  • Start at the root, compare, and move left or right based on value.
  • Reduces search space similar to binary search in arrays.
  • Average case: O(log n).

• Insertion:

  • Determine position like search.
  • Insert as left or right child without shifting elements: O(log n).

• Deletion:

  • Find the node first (O(log n)), adjust links for removal (O(log n)).

Balancing the BST

• Importance: To maintain O(log n) for operations.
• Methods to restore balance will be covered in later lessons.

Conclusion

• Next lesson: Detailed implementation of binary search trees.