Please enable JavaScript.

Coggle requires JavaScript to display documents.

ICS 46 Final Topics (Trees (BST (AVL (Rotations (Used to Balance), "…

- - - - "Balanced BST"
      - Every node's left and right children
        have heights within 1 of each other
      - Rotations
        
        Used to Balance
    - - Worst: Sorted Array
      - Make Balanced: recursively take median
    - - Height
        
        Max: # nodes
        
        Min: Log (Nodes)
        
        Number of "layers"
        
        1 node = 0
        
        0 nodes = -1
      - Nodes
        
        Size
  - - - Find if in node
      - If not, which between which two
      - Go down that list
      - If end reached is false
  - - - A
        
        N
        
        T
        
        E
        
        A
        
        T
        
        1 more item...
        
        S
        
        I
        
        M
        
        A
        
        1 more item...
    - - Go down tree
      - If values same, keep going
      - If value not possible return false
      - If all satisfied, return if node specifies in tree
  - - - Print Level by level, left to right
    - - Left, right, root last
    - - Print left to right
- - - - Swap with smaller/larger child (depending on condition)
    - - Swap if parent is larger/smaller (depend on condition)
- - - - 1
        
        Constant
      - N
        
        Linear
      - log N
        
        Logrithmic
      - N logN
        
        Slightly more than linear
      - N^2
        
        Quadratic
- - - - Best: O(N)
      - Worst Case: O(N^2)
      - Average Case: O(N^2)
      - Process
        
        Compare two values
        
        Swap if one on right is smaller
        
        Keep going until left is smaller
        
        Repeat for each element
      - Comparisons: O(N^2)
      - Swaps: O(N^2)
    - - Best Case: O(N^2)
      - Worst Case: O(N^2)
      - Average Case: O(N^2)
      - Process
        
        Search Array for lowest
        
        Add swap next "unsorted" with lowest
        
        Repeat
      - Comparisons: O(N^2)
      - Swaps: O(N)
  - - - Worst Case: O(N^2)
      - Best Case: O(N log N)
      - Average Case: O(N log N)
      - Process
        
        Get a pivot
        
        Go from left to find larger
        
        Go from right to find smaller
        
        Swap low and high
        
        Repeat until left and right are same spot
        
        Switch Pivot with final location
        
        Select new pivot
        
        Repeat until sorted
      - Space Complexity: O(logN) if recursive
      - Comparisons: O(N^2) worst, O(N logN) avg
      - Swaps: O(N^2) worst, O(N logN) avg
    - - Worst Case: O(N logN)
      - Best Case: O(N logN)
      - Process
        
        Split in left and right array
        
        Keep splitting until down to 2 values
        
        Merge the Arrays
        
        a. Put the smaller value into first
        
        b. Find next smaller and put in
        
        c. Repeat until both arrays are empty
      - Space complexity: O(N)
      - Average Case: O(N logN)
      - Swaps: O(N logN)
      - Comparisons: O(N logN)
    - - Average Case: O(N log N)
      - Best Case: O(N log N)
      - Worst Case: O(N logN)
      - Process
        
        Heapify the array
        
        Take top out of stack
        
        Put to end and rebalance stack
        
        Repeat until all sorted
      - Comparisons: O(N logN)
      - Swaps: O(N logN)
  - - - No Extra space needed
    - - Same Relative Positions
  - - - Space Complex: O(N)
      - Worst Case: O(N log10 N)
      - No Comparisons
    - - Place items into sorted buckets
      - Sort items within each bucket
    - - N = number to be sorted
      - M = Buckets
- - - - Priority Queue
        
        Order defined by different function
      - First in first out
      - enqueue to add
      - dequeue to take out
    - - First in Last out
      - Push to add
      - Pop to take out
      - Has a defined order
    - - Links two values to each other
      - Python dictionary
    - - No defined order
      - All elements unique
- - - - Array
      - Put item into array index of compressed hash value
      - If Index already taken, find next open
      - Searching
        
        Go to index
        
        Check for value
        
        Go until no empty index
      - Deleting
        
        Search
        
        Delete
        
        Mark array index as "deleted" so search does not see as empty
    - - Deleting
        
        Delete from Linked List
        
        Search
      - Searching
        
        Go down Linked List
        
        Go to bucket
      - Put item in to bucket in LN at end
      - Bucket has linked lists
      - Each Hash value has bucket
  - - - O(1)
      - Make different for everything
      - C++ <Hash>
    - - O(N)
      - do not separate properly
      - Make Everything 0
    - - Make Hash value down to bucket size
- - - - Make empty Maps for answer and Info
      - Create a priority queue with priority given to lowest distance
      - PQ not empty
        
        a. Dequeue
        
        b. Put into answer
        
        c. Get distance to "min_node" and add distance to distance of each edge to "new_node"
        
        d. If sum is less than current distance to "new_node", replace distance with new distance
      - Repeat 3 until PQ is empty
  - - - N-1 edges
      - Minimum Spanning tree
        
        Total of edges is lowest
        
        Algorithm
        
        Add all edges to priority queue
        
        Remove the top and put two nodes in same equivalence class
        
        Dequeue another edge
        
        4a. If the edges are not in same equivalence class, add edge to tree
        
        Repeat step 3 and 4 until empty
        
        4b. If in same class, do nothing
      - Tree that links all nodes of graph
    - - Edges go both ways A<-> B
    - - Edge a-> b ==> Edge b-> a (can be different values)
    - - Edge a-> b == Edge b-> a
    - - Portion of graph that does not contain all nodes
    - - Nodes + all edges going into and out of nodes
    - - A-> B + B -> C ==> A-> C
    - - Each node not connected to many nodes
    - - A-> B for all nodes A and B in graph
    - - Each Node connected to almost all other nodes