压缩路径过程#xff1a;如开始让L节点找根节点A#xff0c;那么…知识汇总

Find操作优化

find操作主要是通过S[]数组一路向北来找给定节点的根节点从给定节点到找到根节点所经过的节点路径称为查找路径。

压缩路径就是让查找路径变短。

压缩路径过程如开始让L节点找根节点A那么会根据Find操作一路向北依次找到E、B、A即LEBA为查找路径压缩路径就是先找到根节点A再将查找路径上的所有节点都挂到根节点下即找到了根节点是A查找路径上的节点为LEB都挂到根节点下即index(A)0index(L)11index(E)4,index(B)1让S[11]index(A)0,S[4]index(A)0,S[1]index(A)0(开始B的S值就是0不用改)则此时L再想找根节点直接查找1次就直达根节点A了

代码实现

根据给定节点x数组下标先while循环通过S[]0找到根节点root再while循环对找根节点过程中的节点的S值root数组下标即挂到根节点下边即给定节点-根节点的路径已经变成了1即压缩了路径等下一次再找给定节点的根节点时就还可使用已经压缩好的路径查找提高了效率时间复杂度能大概提高到O(1)(咋还找这是用了缓存吗给定节点的路径压缩完路径后能一直保持不变

Find操作-----》压缩路径使得构造树的高度不超过O(α(n))

近似于O(1)union操作------》小树合并大树使得构造树的高度不超过O(log2n)O(α(n))

优化汇总

union操作优化前find操作查找根节点最坏情况为树为单支h较高情况最坏时间复杂度为O(n)即要从底部查到第一个节点在进行n个独立元素的union操作时需要unin的次数为n-1次(如2个元素union则需要1次union操作)且要先find再union而find的时间复杂度是O(n)则union操作时间复杂度为O(n²)即n*O(n)

union操作优化后(小树合并大树)union操作优化小树合并大树后会让树的高度不超过log2n则find操作的时间复杂度不超过O(log2n)在进行n个独立元素的union操作时需要n-1次union且进行union操作时先find再union,而find的时间复杂度是O(log2n)则union操作时间复杂度为O(nlog2n)

Find操作优化后(压缩路径)find操作压缩路径后会让树的高度不超过O(α(n))则find操作的时间复杂度是O(α(n))在进行n个独立元素的union操作时需要n-1次union且进行union操作时先find再union,而find的时间复杂度是O(α(n))则union操作时间复杂度为O(α(n))[即(n-1)*O(α(n))O(nα(n))]