【CF 675D Tree Construction】BST

  • 时间:
  • 浏览:2
  • 来源:uu快3官方网址_uu快3是真实吗_下载网址

  对于v大于全局最大值的边界情况汇报,succ及其右子树为空。

分析发现,实在可逆:

  且由“直接性”,succ的左孩子必为空。

数据范围:n [2, 10^5]

2. prev的右孩子为空 => 由顺序性,succ必为prev的祖先 => prev层次更深。

  对于v小于全局最小值的边界情况汇报,prev及其左子树为空。

到此,可不还能不能 着手设计算法了。首先用set维护平衡二叉树,每次插入节点v前,调用set的lower_bound(或upper_bound,元素互异故二者无差别) 得到“大于v的第有有另另一个元素”,即插入v后v的直接后继,记录为迭代器succ。然后 得到succ的直接前驱的迭代器prev = succ - 1。

=> 由顺序性,succ必为prev的右子树中的节点,故prev的右子树必非空

  且由“直接性”,prev的右孩子必为空。

题目链接:http://codeforces.com/problemset/problem/675/D

=> 由顺序性,prev必为succ的左子树中的节点,故succ的左子树必非空

对于有有另另一个新的待插入的节点v,这些人 在当前BST的中序遍历序列 s 中进行二分查找,得到应插入的位置的后继元素的位置succ(“大于v的第有有另另一个元素,即upper_bound”),然后 得到prev=succ-1。为了保证BST的顺序性,v必然要插在prev和succ之间。

实在这这些情况汇报是对立的,然后 一次判断就可选择属于哪种。

题意:给有有另另一个由n个互异整数组成的序列a[],模拟BST的插入过程,依次输出每插入有有另另一个元素a[i]后a[i]的父节点。

1. succ层次更深

可不还能不能 利用STL中的set容器,但对于题目所要找的“父节点”,set暂且提供接口。这时就要考察BST的这些性质推导出解法。

回顾二叉树的中序遍历,对节点prev的直接后继succ的定位操作分这些情况汇报。注意等价BST的“上下可变,左右不乱”的性质,不论否有进行了等价变换,中序遍历序列中任意有有另另一个互为直接前驱和直接后继的元素,其层次关系必然为如下这些之一:

这些人 回到对这这些情况汇报的描述上:然后所做的推导否有可逆呢?可能可逆,这么这些人 可不还能不能 通过判断succ或prev的左右孩子否有为空就可不还能不能 得知是哪种情况汇报。

思路:直接模拟一般的BST而不维护平衡性搞笑的话,有可能会跳出极度不平衡甚至退化的情况汇报,错综复杂度会从O(nlogn)上升到O(n^2)。然后 要用平衡二叉树。

p.s: CF题解的代码好优美,学习了。

2. prev层次更深

1. succ的左孩子为空 => 由顺序性,prev必为succ的祖先 => succ层次更深。

对于左右孩子情况汇报的记录,我这么想到方法,CF题解给出的是维护有有另另一个map<int, int>left, right,left记录节点对<v, lc>,right记录节点对<v, rc>。每次插入前通过判断left[succ]和right[prev]否有为空来判断父节点是谁,以及v作为左孩子还是右孩子插入,更新map。

从树的社会形态上看,可不还能不能 插在标有“必为空”的位置,它恰好介于prev和succ之间,顺序性必然得到保证。具体地,即“succ和prev中更深的那个”,1、2这些情况汇报分别对应succ和prev。要怎样选择是哪种情况汇报呢?