小编Dan*_*art的帖子

我在AVL Tree Wikipedia页面上注意到以下评论:

"如果每个节点另外记录其子树的大小(包括它自己及其后代),那么也可以通过索引在O(log n)时间内检索节点."

我用google搜索并找到了一些提到索引访问的地方,但似乎无法找到人们会编写的算法的解释.

非常感谢

[更新]谢谢大家.如果发现@templatetypedef与@ user448810之一的链接结合起来特别有帮助.特别是这个剪辑:

"这两个函数的关键是节点的索引是它的左子节点的大小.只要我们通过它的左子节点下降树,我们只需要取节点的索引.但是当我们必须移动时通过正确的孩子在树下,我们必须调整大小,以包括我们排除的树的一半."

因为我的实现是不可变的,所以在重新平衡时我不需要做任何额外的工作,因为每个节点计算它的构造大小(与方案impl链接相同)

我最后的实施结果是:

class Node<K,V> implements AVLTree<K,V> { ...
    public V index(int i) {
        if (left.size() == i) return value;
        if (i < left.size()) return left.index(i);
        return right.index(i - left.size() - 1);
    }
}

class Empty<K,V> implements AVLTree<K,V> { ...
    public V index(int i) { throw new IndexOutOfBoundsException();}
}

这与其他实现略有不同,如果您认为我有错误,请告诉我!

我有 2 个表都具有唯一约束，1 个连接这 2 个表的视图和一个INSTEAD OF INSERT允许INSERT或UPDATE在视图上的触发器。

一切正常INSERT，UPDATE但如果我这样做，INSERT .. ON CONFLICT(tableAColumn,tableBColumn) DO UPDATE我会收到错误消息：

[42P10] ERROR: there is no unique or exclusion constraint matching the ON CONFLICT specification

如果视图可以自动更新，那么我想我可以只使用 aWITH CHECK OPTION但是我如何使用INSTEAD OF INSERT触发器来做到这一点？

或者另一种方式来询问如何使视图具有与构建它的表相同的约束？