We found Quick-find is too slow for huge problems. So, how are we going to do better? Our first attempt is an alternative called, Quick-union.
Quick-union is also called lazy approach to algorithm design where we try to avoid doing work until we have to. It uses the same data structure or array ID with size N but now it has a different interpretation. We are going to think of that array as representing a set of trees that's called a forest as depicted in Figure 2. So, each entry in the array is going to contain a reference to its parent in the tree. For example, 3's parent is four, 4's parent is nine. So 3's entry is four and 4's entry is nine in the array. Now each entry in the array has associated with it a root. That's the root of its tree.
In general, the data structure are:
- Integer array id of size N
- Interpretation: id[i] is parent of i
- Root of i is id[id[id[...id[i]...]]]
Find operation: check if p and q have the same root. For example, find(3,5)
Union operation: to merge components containing p and q, set the id of p's root to the id of q's root. For example, union(3, 5)
Quick-union: Java implementation
Quick-union efficiency (it is also too slow)
Cost model: Number of array accesses (for read and write)
- Trees can get very tall
- Find too expensive (could be N array accesses)
References & Resources
- Dependency injection
- Directives and Pipes
- Data binding
- HTTP Get vs. Post
- Node.js is everywhere
- MongoDB root user
- Prefer Async Script Loading
- Components, Bootstrap and DOM
- What is HEAD in git?
- Show the changes in Git.
- What is AngularJS 2?
- Confidence Interval for a Population Mean
- Accuracy vs. Precision
- Sampling Distribution
- Working with the Normal Distribution
- Standardized score - Z score
- Evaluating the Normal Distribution
- What is Nodejs? Advantages and disadvantage?
- How do I debug Nodejs applications?
- Sync directory search using fs.readdirSync