rank和select操作

Question

bobo老师，rank和select操作直接用中序遍历，然后找出对应索引或者索引的元素不就行了吗。为什么用size这个变量？

Answer 1

liuyubobobo 2018-08-20 10:15:31

如果使用先中序遍历的方式，rank和select的操作就变成了O(n)级别的操作。但是添加上了对size的维护以后，rank和select操作是O(logn)级别的操作：）

思考一下看看？

提示：如果有size这个变量，比如要找第16个元素，我们从根节点出发，就可以直接知道，或者这个根节点就是第16个元素；或者我们可以直接去左子树找，而完全不管右子树；或者我们可以直接去右子树找；而完全不管左子树：）

强烈建议自己动手实现以下试试看：）

加油！

• 提问者 Super波神 #1

  非常感谢！