圣诞树(ChristMas Tree),简称 CMT,又因为 Q=cmΔt,故我们也可以称它为 Q 比 Δ 树。
圣诞树寓意着庆祝希望和团结,那么它在算法竞赛中是怎样的一棵树呢?
它其实是 BST 的改造,来解决平衡树能解决的问题。比如 P3369 这道难题,我们先维护一棵平平无奇的 BST,但是如果这棵树慢慢地长得不平衡怎么办?我们需要让这棵树变得更平衡。具体地,如果这棵树我深度大于了 n,我们可以对它进行暴力重构,然后中序遍历这棵树,于是我们将获得一个单调有序的序列,这时我们将中间数作为根,然后往下连边即可。这样可以让这棵树的深度变成 log 级别的,那么这样我们发现,查询修改的最劣复杂度是 O(nn) 的,暴力重构的复杂度同样也是 O(nn) 的。