1. Search Trees

• They are used to search/insert/delete efficiently when given ordered maps
  • Ordered maps
    • Keys are in total order
    • Items are stored in order by their keys
    • It allows us to support nearest neighbor queries
• Search tables based on array can be compared
  • Search - O(log(n))
  • Insert/Delete - O(n). n/2 times of shifting items in the worst case
  • Effective only for ordered maps of small size or the ones where searches are the most common ops

2. Types

Binary Search Trees

BST

Definition

• key(u) < key(v) < key(w) (< → ≤ if duplicates are allowed) u : a node in the left subtrees of v / w : a node in the right subtrees of v

Performance

• Space used - O(n)

• h - O(n) in the worst case, O(log(n)) in the best case)

• Search - O(h)

• Delete - O(h)

• Insert - O(h)

AVL Tress

AVL Trees

Definition

• A BST such that for every internal node v of T, the heights of v's children can differ by at most 1

Performance

• Space used - O(n)

• h - O(log(n))

• Trinode Restructuring (single/double rotation) - O(log(n))

• Rebalancing - O(log(n))

• Search - O(log(n))

• Insert - O(log(n))

• Trinode Restructuring

• Delete - O(log(n))

• Trinode Restructuring
• Rebalancing

(2,4) Trees

(2,4) Trees