与其他数据结构相比,二进制索引树几乎没有理论要研究。唯一简短讲授的地方是topcoder教程。尽管本教程的所有解释均已完成,但我无法理解,这种树背后的直觉是什么?以及如何证明其正确性?
我认为证明很难解释。因此,在使用BIT时,您会采用哪种方法?
我发现@templatetypedef给出的答案非常清楚地说明了二进制索引树的直觉和证明:答案…。
直观地,您可以将二进制索引树视为二进制树的压缩表示形式,它本身就是对标准数组表示形式的优化。这个答案有一个可能的推论。
例如,假设您要存储总共7个不同元素的累积频率。您可以首先写出将要分配数字的七个存储桶:
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
1 2 3 4 5 6 7
现在,让我们假设累积频率如下所示:
[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
1 2 3 4 5 6 7
使用此版本的阵列,您可以通过增加在该点存储的数字的值来增加任何元素的累积频率,然后增加之后所有事物的频率。例如,要将3的累积频率增加7,我们可以在位置3或之后的数组中的每个元素上加上7,如下所示:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
这样做的问题是,这需要O(n)时间来完成,如果n大,这将非常慢。
我们可以考虑改进此操作的一种方法是更改存储在存储桶中的内容。您可以考虑只存储当前频率相对于先前存储桶增加的数量,而不是存储直到给定点的累积频率。例如,在本例中,我们将上述存储桶重写如下:
Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
现在,我们可以在时间段O(1)中增加一个桶中的频率,只需在该桶中添加适当的数量即可。但是,执行查找的总成本现在变为O(n),因为我们必须通过对所有较小存储桶中的值求和来重新计算存储桶中的总数。
我们需要从这里获得的二进制索引树的第一个主要见解如下:不是连续重新计算特定元素之前的数组元素之和,如果我们要预先计算所有特定元素之前的所有元素的总和,该怎么办?点顺序?如果我们能够做到这一点,那么我们可以通过将这些预先计算的总和正确组合起来得出一个点的累计总和。
一种实现方法是将表示形式从存储桶数组更改为节点的二叉树。每个节点都将用一个值表示,该值代表该给定节点左侧所有节点的累计和。例如,假设我们从这些节点构造以下二进制树:
4
/ \
2 6
/ \ / \
1 3 5 7
现在,我们可以通过存储包括该节点及其左子树在内的所有值的累积和来扩充每个节点。例如,给定我们的值,我们将存储以下内容:
Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
After:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[ +5] [+15] [+52] [ +0]
有了这种树形结构,很容易确定一个点的累积总和。想法如下:我们维护一个计数器,最初为0,然后进行常规的二进制搜索,直到找到有问题的节点。在执行此操作时,我们还将执行以下操作:在每次向右移动时,我们还将当前值添加到计数器中。
例如,假设我们要查找3的总和。为此,我们执行以下操作:
您可以想象也可以反向运行此过程:从给定节点开始,将计数器初始化为该节点的值,然后沿树走到根。每当您向上跟随一个正确的子链接时,请在您到达的节点上添加值。例如,要找到3的频率,我们可以执行以下操作:
要增加节点的频率(以及隐式地增加其后所有节点的频率),我们需要更新树中包含该节点在其左子树中的节点集。为此,我们执行以下操作:增加该节点的频率,然后开始向上走到树的根。每当您点击将您带入左边的链接时,都可以通过添加当前值来增加遇到的节点的频率。
例如,要将节点1的频率增加5,我们将执行以下操作:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[ +5] [+15] [+52] [ +0]
从节点1开始,将其频率增加5以得到
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[+10] [+15] [+52] [ +0]
现在,转到其父级:
4
[+32]
/ \
> 2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
我们沿着左子链接向上移动,因此我们也增加了该节点的频率:
4
[+32]
/ \
> 2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
我们现在转到其父项:
> 4
[+32]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
那是一个左子链接,所以我们也增加这个节点:
4
[+37]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
现在我们完成了!
最后一步是将其从树转换为二进制索引树,在这里我们可以使用二进制数做一些有趣的事情。让我们用二进制重写此树中的每个存储区索引:
100
[+37]
/ \
010 110
[+11] [+80]
/ \ / \
001 011 101 111
[+10] [+15] [+52] [ +0]
在这里,我们可以做一个非常非常酷的观察。取这些二进制数中的任何一个,找到该数字中设置的最后一个1,然后将该位及其后的所有位都删除。现在,您剩下以下内容:
(empty)
[+37]
/ \
0 1
[+11] [+80]
/ \ / \
00 01 10 11
[+10] [+15] [+52] [ +0]
这是一个非常非常酷的观察结果:如果将0表示“左”,将1表示“右”,则每个数字上的其余位将准确说明如何从根开始,然后向下移动到该数字。例如,节点5具有二进制模式101。最后1是最后一位,因此我们将其丢弃以得到10。实际上,如果您从根开始,请向右(1),然后向左(0),然后结束在节点5上!
之所以如此重要,是因为我们的查找和更新操作取决于从节点备份到根节点的访问路径,以及我们是否遵循左或右子链接。例如,在查找过程中,我们只关心我们遵循的左侧链接。在更新期间,我们只关心我们遵循的正确链接。该二进制索引树仅通过使用索引中的位就可以高效地完成所有这些工作。
关键技巧是此完美的二叉树的以下属性:
给定节点n,通过取n的二进制表示并删除最后一个1,可以得到访问路径上备份到根的第二个节点。
例如,看一下节点7的访问路径,即111。我们访问根的访问路径上涉及向上跟随右指针的节点是
所有这些都是正确的链接。如果我们采用节点3的访问路径(即011),然后看一下正确的节点,则得到
这意味着我们可以非常非常有效地计算到一个节点的累积总和,如下所示:
同样,让我们考虑如何执行更新步骤。为此,我们希望遵循访问路径回到根,更新所有我们沿左链接向上的节点。我们可以通过本质上执行上述算法来做到这一点,但是将所有1都切换为0,将0切换为1。
二进制索引树的最后一步是要注意,由于这种按位欺骗,我们甚至不需要再显式地存储树。我们可以将所有节点存储在长度为n的数组中,然后使用按位旋转技术隐式地导航树。实际上,这正是按位索引的树所做的工作-
将节点存储在数组中,然后使用这些按位技巧来有效地模拟在此树中的向上行走。
希望这可以帮助!
从二叉查找树中删除节点时,您可以将节点替换为左侧的最大子节点或右侧的最小子节点。 我很难理解以下实现执行删除操作的方式。 上面的代码包括以下步骤: < li >查找替换节点。 < li >让替换节点引用已删除节点的左右子节点。 < li >让已删除节点的左右子节点将替换节点作为父节点。 < li >让替换节点引用已删除节点的父节点作为自己的父节点。 < li >清理。 我有困难的部分特别是递归。据
我试着删除二叉查找树的节点,当我打印出来的时候,我得到的结果实际上不是这个删除,实际上可以删除二叉树本身的任何键。 我是二进制搜索树的新手。有人能帮我写代码吗?我们将感谢您的帮助。 谢谢 完整代码
我正在尝试为二叉搜索树类编写一种方法来修改平衡的普通树,这使得树仅在一侧具有节点。 从元素在不平衡树中出现的顺序来看,依序遍历(左、中、右)之间似乎存在某种关系。
假设BST定义如下: 节点的左子树只包含键小于节点键的节点。节点的右子树只包含键大于节点键的节点。左子树和右子树也必须是二叉搜索树。 示例1:
问题内容: 我正在编写一个使用二进制搜索树存储数据的程序。在以前的程序中(无关),我能够使用Java SE6随附的实现来实现链表。二进制搜索树是否有类似的东西,还是我需要“从头开始”? 问题答案: 您可以使用。被实现为一棵红黑树,这是一个自平衡二进制搜索树。
二进制搜索树(BST)是一个树,其中所有节点都遵循下面提到的属性 - 节点的左子树具有小于或等于其父节点密钥的密钥。 节点的右子树的密钥大于其父节点的密钥。 因此,BST将其所有子树划分为两个部分; 左子树和右子树可以定义为 - left_subtree (keys) ≤ node (key) ≤ right_subtree (keys) 表示 Representation BST是节点
给定二叉查找树(BST)和整数val的根。 在BST中找到该节点的值等于val的节点,并返回以该节点为根的子树。如果这样的节点不存在,则返回null。 为什么'ans=root'不起作用??
我正在尝试实现一个二叉查找树,但是“搜索”函数对于除了根之外的每个条目都返回了错误的值。 该函数应返回其值与键参数匹配的节点的地址,如果节点不存在,则返回 NULL。 当我运行代码时,我得到以下内容: 我知道每个节点的“左”和“右”指针链接正确,因为“delAll”函数成功删除了所有节点。 将“cout”语句添加到“search”函数表明该函数似乎返回了正确的地址。为什么从主主调用时会打印错误的地