> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/14.-disjoint-sets/14.4-weighted-quick-union-wqu.md).

# 14.4 Weighted Quick Union (WQU)

Improving on Quick Union relies on a key insight: whenever we call `find`, we have to climb to the root of a tree. Thus, the shorter the tree the faster it takes!

**New rule:** whenever we call `connect`, we always link the root of the smaller tree to the larger tree.

Following this rule will give your trees a maximum height of $$log N$$, where N is the number of elements in our Disjoint Sets. How does this affect the runtime of `connect` and `isConnected`?

{% embed url="<https://www.youtube.com/watch?v=xc9s9wdaSdU>" %}
Professor Hug's explanation on Weighted Quick Union
{% endembed %}

Let's illustrate the benefit of this with an example. Consider connecting the two sets T1 and T2 below:

![](https://joshhug.gitbooks.io/hug61b/content/chap9/9.4.1.png)

We have two options for connecting them:

&#x20;The first option we link T1 to T2. In the second, we link T2 to T1.

<figure><img src="https://joshhug.gitbooks.io/hug61b/content/chap9/9.4.2.png" alt=""><figcaption></figcaption></figure>

The **second option is preferable** as it only has a height of 2, rather than 3. By our new rule, we would choose the second option as well because T2 is smaller than T1 (size of 3 compared to 6).

We determine smaller / larger by the number of items in a tree. Thus, when connecting two trees we need to know their size (or weight). We can store this information in the root of the tree by replacing the `-1`'s with `-(size of tree)`.&#x20;

**Maximum height: Log N**

Following the above rule ensures that the *maximum* height of any tree is Θ(log N). N is the number of elements in our Disjoint Sets. **By extension, the runtimes of `connect` and `isConnected` are bounded by O(log N).**&#x20;

Why $$logN$$? The video above presents a more visual explanation. Here's an optional mathematical explanation why the maximum height is $$log\_{2}N$$. Imagine any element $$x$$ in tree $$T1$$. The depth of $$x$$ increases by 1 only when $$T1$$ is placed below another tree $$T2$$. When that happens, the size of the resulting tree will be at least double the size of $$T1$$ because $$size(T2)\geq size(T1)$$. The tree with $$x$$ can double at most $$log\_{2}N$$ times until we've reached a total of N items ($$2^{log\_{2}N} = N$$). So we can double up to $$log\_{2}N$$​​ times and each time, our tree adds a level → maximum $$log\_{2}N$$ levels.&#x20;

You may be wondering why we don't link trees based off of height instead of weight. It turns out this is more complicated to implement and gives us the same Θ(log N) height limit.

### Summary <a href="#summary-and-code" id="summary-and-code"></a>

| Implementation       | Constructor | `connect` | `isConnected` |
| -------------------- | ----------- | --------- | ------------- |
| QuickUnion           | Θ(N)        | O(N)      | O(N)          |
| QuickFind            | Θ(N)        | Θ(N)      | Θ(1)          |
| QuickUnion           | Θ(N)        | O(N)      | O(N)          |
| Weighted Quick Union | Θ(N)        | O(log N)  | O(log N)      |

N = number of elements in our DisjointSets data structure


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook/14.-disjoint-sets/14.4-weighted-quick-union-wqu.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.