Algorithms, Part I快速查找与快速合并的提高算法之——带权算法

爱被打了一巴掌 2022-03-10 08:19 434阅读 0赞

这个算法就是判断每个树的深度，将小树（即树的深度小的树）的根节点赋给大树（即树的深度大的树）的根节点。  
这样实现快速合并十分的高效又可以避免树过于瘦高而引起的时间复杂度大的问题。  
在权全算法中，一棵树最大的深度不超过4。

这个算法有个标准，就是小树的深度要小于大树的深度  
1 首先我们要判断两个量的根节点是否相同，因为如果相同就代表两个量在一棵树里。  
2如果根节点不同，我们就要判断树的根节点的id\[\]为多少，并且进行比较，  
如：  
p的根节点是id\[4\]=4;  
q的根节点是id\[8\]=8；  
4<8;  
所以要把p这颗树赋给q这棵树上  
这样就是要合并了  
我们需要另外一个数组来实现计算树的大小  
if sz\[i\]<sz\[j\]；  
\{  
id\[i\]=j;  
sz\[j\]+=sz\[i\]  
\}  
else  
\{  
id\[j\]=i;  
sz\[i\]+=sz\[j\];  
\}  
2如果现在是一颗相当瘦高的树，我们要把它展平，展平的方法非常简单  
直接把q的根根节点，即最上头那个赋值给q的上面第一个点  
（1）要通过回溯的方法，找到这颗树的根节点  
while(i!=id\[i\])  
\{  
id\[i\]=id\[id\[i\]\];  
i=id\[i\];  
\}  
return i;//返回的是根节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDI2Nzky_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDI2Nzky_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDI2Nzky_size_16_color_FFFFFF_t_70]: /images/20220310/d5c37dcbb9dc446a9fb6a41f69e17831.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDI2Nzky_size_16_color_FFFFFF_t_70 1]: /images/20220310/0d0d1ae2992c4fa9abe8207b45c78e0e.png