sparse-matrix - 使用二叉搜索树实现稀疏矩阵

Question

我必须实现一个稀疏矩阵（一个以零为主的矩阵，所以你只记录不同于 0 的值），但我必须使用二叉搜索树来实现它。

编辑：

所以现在我正在考虑通过使用行/列作为键来实现它，但是我用什么作为那棵树的根呢？

/编辑

我希望一旦我研究了二叉搜索树，我就会明白这种实现会有什么好处，或者至少是可能的，但我这辈子都想不通。

我试过谷歌无济于事，我自己也无法想象如何尝试这样做。

我还没有决定用什么语言来实现它，所以我不需要代码示例，我的问题是逻辑。我需要看看这甚至会如何工作。

PS我不知道要使用什么标签，如果有人可以编辑一些，将不胜感激。

Answer 1

要使用二叉树，您需要有一个对矩阵中的每个（可能）条目都不同的键。因此，如果您想在矩阵 [100, 100] 中查找 (2, 4)，则键可能类似于“002004”。使用此键，您可以将值插入树中。

对于每个维度，键会更长，因此您还可以考虑使用散列函数来散列单元格的坐标，并且在树中，您有此散列键的条目列表。然后，树只是右列表的索引。然后，您需要在列表中执行顺序搜索。或者，如果您订购列表，您可以通过使用二进制搜索来改进。