关于二叉索引树 (indexed binary search tree) 的元素查找问题？

Question

这是书上对一棵二叉索引树进行一次查找的结果, 要查找的索引是 2, 对应的元素是 18

书上只是给出了一个例子, 并没有详细说明算法, 也没有给出对应的代码

现在, 对于这个算法, 我有一个猜想 : 假设要查找的元素索引是 i, 如果索引比根元素的索引要大, 那么向左走; 否则, 向右走. 遇到下一个节点时, 对元素对应的索引值和要查找的索引值进行比较. 如果目前所在元素的索引值和要查找的索引值不相等, 那么 i -= (目前元素的索引值 + 1). 重复上述步骤直到找到为止

根据这个猜想, 我自己画了一棵二叉搜索树

这棵二叉搜索树每个节点的左侧是这个节点具有的左子节点的个数, 也就是书上对于二叉索引树的定义, 这个定义从二叉搜索树衍生

如果要在这颗树上查找索引为 3 的节点, 那么对应的元素应该是 23; 如果要在这棵树上查找索引为 4 的节点, 那么对应的元素应该是 34

我在网上查找过一些关于二叉索引树的资料, 网上都是关于二进制的资料比较多, 但是书中并没有提到任何关于二进制的内容. 除了上面这个, 我想问下网上所说的二进制相关的二叉索引树和书中提到的二叉索引树是否是同一个数据结构

Answer 1

树状数组，也叫二叉索引树（Binary Indexed Tree，简称 BIT）。其内部实现是数组，而不是树。

https://subetter.com/algorith...