假设我有一个 balancer 的BST（二叉搜索树） . 每个树节点都包含一个特殊字段 count ，它对节点本身的所有后代进行计数 . 他们称这个数据结构为 order statistics binary tree .
此数据结构支持O（logN）的两个操作：
-
rank(x)- 小于x的元素数量 -
findByRank(k)- 找到rank==k的节点
现在我想添加一个新的操作 median() 来查找中位数 . 如果树是 balancer 的，我可以假设此操作是O（1）吗？
3 回答
如果树完整（即所有级别完全填满），是的，你可以 .
除非树完整，否则中值可能是叶节点 . 因此，一般情况下，成本将为O（logN） . 我猜有一个带有请求属性的数据结构和一个O（1）findMedian操作（也许跳过列表指向中间节点的指针;我不确定findByRank和排名操作）但是 balancer 的BST不是一个他们
在 balancer 订单统计树中，找到中位数是O（log N） . 如果在O（1）时间内找到中位数很重要，可以通过保持指向中位数的指针来扩充数据结构 . 当然，问题是您需要在每次插入或删除操作期间更新此指针 . 更新指针将花费O（log N）时间，但由于这些操作已经花费O（log N）时间，更新中值指针的额外工作不会改变它们的大O成本 .
实际上，只有与插入/删除次数相比进行大量“查找中值”操作才有意义 .
如果需要，可以使用(doubly) threaded binary tree降低在插入/删除到O（1）期间更新中值指针的成本，但插入/删除仍然是O（log N） .