Please enable JavaScript.

Coggle requires JavaScript to display documents.

MM11 - Coggle Diagram

- - - - Described by explicit listing or property-based rules.
      - Contrast with lists: unordered vs. ordered, uniqueness vs. duplicates.
      - Unordered collection of distinct elements.
    - - Membership check
        Union
        Intersection
    - - Bit Vectors
        
        Each element in U maps to a bit
        
        Fast operations
        
        High memory
      - Lists
        
        Enforce uniqueness and handle order
        
        Sorted for efficiency
    - - Allows dupes
  - - - Dynamic data structure
        
        Search
        
        Insert
        
        Delete
      - Balances efficiency between operations
    - - Arrays
        
        Unsorted
        
        Fast inserts, slow searches
        
        Sorted
        
        Slow inserts, binary search
      - Hashing
        
        Fast for average case operations
      - Balanced Search Trees
        
        O(log n) time
        
        AVL trees
  - - - Union
      - Find
- - - - search
        insert
        delete
    - - Maps keys to hash table
        
        h(K) = K mod m
  - - - Keys stored in linked lists
      - Load Factor (α = n/m)
        
        Success: S ≈ 1 + a/2
        
        Unsuccessful: U ≈ a
      - Efficiency
        
        O(1), a ≈ 1
    - - Keys stored in table
      - Linear Probing
        
        Check next cell on collision
        
        Causes clustering
        
        Degrades performance
      - Double hashing
        
        Secondary hash function
        
        No clustering
      - Rehashing
        
        Resize table when a increases
  - - - Hashing
        
        O(1) best case
        O(n) worst case
      - Trees
        
        O(log n) constant
    - - Hashing doesn't preserve key order
      - Trees preserve key order