Binary Search (2)

BST Property

Left subtree keys ≤ node key ≤ right subtree keys

BST Node Types

Internal nodes: store keys or key-value pairs; External nodes (leaves): are empty/don't store items

BST Element Requirements

Must have a total order relationship; Must be comparable

Ideal vs Worst Tree Structures

Ideal: Balanced tree with height O(log n); Worst: Linear/degenerate tree with height O(n) (resembles linked list)

BST Time Complexity

Balanced BST: O(log n); Unbalanced BST: O(n)

Binary Search Array Time Complexity

O(log n) in all cases

Space Complexity

O(n) for both BST and arrays

Binary Search Array Requirements

The array must be sorted

BST Remove Operation

No kids: Just cut (remove the node); One kid: Promote (replace with the child); Two kids: Inorder swap (replace with inorder successor)

BST Insert Operation

Search for the position; Reach a leaf node; Plant the new node

BST Search Operation

Compare key with current node; Go left if smaller, right if larger; Repeat until found or reach null

Binary Search in Arrays

Compare target with middle element; Go to left half if smaller, right half if larger; Repeat until found or search space is empty

Key Comparison in BST

Keys less than or equal: left subtree; Keys greater than or equal: right subtree

Degenerate BST

Resembles a linked list with height O(n), making search operations inefficient compared to a balanced tree's O(log n)

BST vs Array Binary Search

Array binary search: Always O(log n); BST search: O(log n) for balanced, O(n) for unbalanced

Total Order Relationship

For any two elements, you must be able to determine their relative order (≤, =, or ≥). All elements must be comparable with each other

External vs Internal Nodes

External nodes represent the endpoints of the tree structure where new nodes can be inserted. They don't store data but mark potential insertion points

Inorder Successor/Predecessor

Replace the node with either its inorder successor (smallest node in right subtree) or inorder predecessor (largest node in left subtree)

BST Height Impact

Height directly impacts time complexity: Height O(log n): Operations are O(log n); Height O(n): Operations degrade to O(n)

Array vs BST Trade-offs

Arrays: Guaranteed O(log n) search but O(n) insertion/deletion; BSTs: O(log n) for all operations when balanced, but can degrade to O(n) if unbalanced