笛卡尔树的笛卡尔树的实现
发布网友
发布时间：2022-05-02 06:41
共1个回答
热心网友
时间：2022-06-29 05:11
①排序之后直接构造笛卡尔树的方法：
首先将节点序列按照key从小到大排序，然后按照顺序插入节点，注意到排序之后，插入的节点的key值一定是树中最大的，所以只需查找最右端的路径，找到一个节点A[i]的value大于待插入节点的value,同时A[i]->right的value小于待插入节点的value。找到之后，只需将A[i]的right指向待插入的节点，A[i]的right原来指向的节点赋值给待插入节点的left指针。注意到查找最右路径的方向，如果从下到上查找，复杂度比较容易分析O(N)（因为查找过的节点必然会旋转到某个节点的左子节点，因此每个查找过的节点只会被查找一次），如果从上倒下，比较复杂（和最右端的最终的路径长度有关吧），会超过N，甚至更高，可能为O(N^2)。
②利用排序加左旋的方法：
就是一样先排序，然后使用treap插入节点，可以发现，所有的旋转都为左旋。这种方法也TLE了，这种方法有一个很重要的意义，就是分析了上个方法中从上到下扫描的复杂度。因为这两种方法的效率是等价的，都TLE。 我们将要将A的元素依次插入笛卡尔树C。每次插入都可能使树的形态发生变化。为了在O(N)的时间内完成整个插入过程，考虑C的右链，即根结点、根结点的右儿子、根结点的右儿子的右儿子……组成的链。注意这些元素的下标和值都是递增的。下标最大，即将要插入的元素A[i]一定是新树右链的最后一个元素。原来的右链中，值比A[i]大的元素在新树中不再属于右链，这些元素组成的链成为A[i]的左子树的右链；原来右链中的其它元素加上A[i]组成了新的右链。初看起来，寻找分界点的最佳方法是O(logN)时间的二分查找；但是对于整个过程来说，O(NlogN)的时间复杂度不是最优的。关键在于一旦一个元素比A[i]大，它就从右链中被永久地移除了。如果按照从后到前的顺序判断一个元素是否大于A[i]，则每次插入的时间复杂度为O(k+1)，k为本次插入中移除的右链元素个数。因为每个元素最多进出右链各一次，所以整个过程的时间复杂度为O(N)。
用一个栈结构维护右链元素的下标，上述过程可以很容易地实现。（见下面代码部分）
