Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algorithms (Searching (Union Find (Implementations (Quick-union (lazy…

- - - - find
        
        query are two objects in the same set?
      - union
        
        union the two sets when the two objects are in different sets
    - - Quick-find
        
        Find - objects p and q are connected if they have the same id
        Union - change ids of all objects in p's set to that of q's set
        
        problems:
        
        too many values need to change id, which can be slow
        
        lost info of previous set ids
        
        eager approach
      - Quick-union
        
        lazy approach
        
        store parent of object i in id[i] instead of id
        
        Find - objects p and q have the same root?
        Union - set the id of q's root to that of p's root
        
        problems:
        
        trees can get too tall
        
        need to do find to do union
      - Improvements
        
        Weighting
        
        keep track of size of each component/depth of tree paths
        
        balance by avoid creating tall trees (link small trees to tall ones)
        
        Path Compression
        
        after finding root for a node, set id of each examined node in the path to the root, to flatten the tree
        
        solution: make every other node in the path point to its grandparent, just one line: id[i] = id[id[i]]
        
        M union and find ops on N objects takes O(N + M lg* N) time (almost linear in practice)