Jac*_*ale 6 algorithm data-structures
"算法设计手册"一书中的消息3-7说:
假设您可以访问平衡字典数据结构,该结构支持O(log n)时间内的每个操作搜索,插入,删除,最小,最大,后继和前任.解释如何修改插入和删除操作,使它们仍然采用O(log n),但现在最小和最大需要O(1)时间.(提示:考虑使用抽象字典操作,而不是使用指针等等.)
没有提示,我认为这个问题相当容易.
这是我的解决方案:
对于树,我只保持指针min总是指向最小值,另一个指针max总是指向最大值.
插入x时,我只需将min.key与x.key进行比较if min.key > x.key, then min = x;,如果需要,也可以将此值设为max.
删除x时, if min==x, then min = successor(x); if max==x, then max = predecessor(x);
但暗示说我不能捣乱指针之类的东西.我的解决方案是否与指针混淆？
如果我们不能使用加分,我怎样才能得到O(1)的最小值和最大值？
谢谢