qiu*_*bit 3 algorithm tree data-structures
我们给出了一个树,n节点以指向其根节点的指针的形式存在,其中每个节点包含指向其父节点,左子节点和右子节点的指针,以及一个整数键.对于每个节点,v我想添加额外的字段v.bigger,该字段应包含密钥大于的节点数v.key,这些节点位于以子树为根的子树中v.将这样的字段添加到树的所有节点O(n log n)总共需要时间.
我正在寻找任何可以解决这个问题的提示.我尝试了几种启发式方法 - 例如,当考虑以自下而上的方式对固定节点执行此问题时v,v.left并且v.right可以提供v某种类型的设置(平衡BST？)与操作bigger(x),对于给定的x返回更多的元素比x在logarihmic时间设定.问题是,我们需要合并这些集合O(log n),所以这似乎是一个禁忌,因为我不知道任何有序的集合,如支持快速合并的数据结构.
我还考虑过自上而下的方法 - 一个节点为某个节点v添加一个u.bigger节点,u当且仅当它u位于到根节点的简单路径上时u<v.所以v可以u以某种方式更新所有这些,但我无法想出任何合理的方式来做到这一点......
那么,思考这个问题的正确方法是什么？
在给定树中执行深度优先搜索(从根节点开始).
当第一次访问任何节点(来自父节点)时,将其密钥添加到某个订单统计数据结构(OSDS).同时查询OSDS以获得大于当前密钥的密钥数量,并v.bigger使用此查询的否定结果进行初始化.
当最后一次访问任何节点(来自右子)时,查询OSDS以获取大于当前键的键数并将结果添加到v.bigger.
您可以将此算法应用于任何有根树(不一定是二叉树).并且它不一定需要父指针(您可以使用DFS堆栈).
对于OSDS,您可以使用增强的BST或Fenwick树.在Fenwick树的情况下,您需要预处理给定的树,以便压缩键的值:只需将所有键复制到数组,对其进行排序,删除重复项,然后通过此数组中的索引替换键.