前言
关于我想去学环状树却学了左偏树这件事
正文
前置芝士
性质
根据算法名称就可以知道,这是一个森林中所包含的所有树都向左偏的森林(也是因为他向左偏,并且可以进行合并,所以他也是可并堆)。
算法函数
建树: 很简单,并查集实现(就不放代码了)。
合并: 也就是把两棵树合并先放代码:
按照代码从上往下说,首先来看这句:
什么意思呢,很简单我们可以把它和 r[x]=merge(r[x],y);
结合食用,也就是说再找右子树时,如果到了叶子节点或 y 变为 0 了,就把以 y 为根的树变为右子树或返回右子树当前节点的值(因为 y 等于零的情况肯定是前几次循环,x 与 y 交换了值)。
其他就不用说了,都是维护左偏树。
删除: 删除分两种,一种是把根节点删除(也就是删除堆中的最大或最小元素),第二种是删除任意元素。
先上代码:
其实这两种差不了多少,都是先把左右子树合并,再和自己父节点所在的子树合并(可以想一想,很简单)。
嗯对就没了,一共就这两种操作,上一下例题 p3377 的代码 (无注释):
例题
和板子题一模一样。
需要删去任意节点,另外注意判断。
每次合并要除以 2,以及要寻找堆顶。
finally
没了。
0 条评论