Can be a single tree for the matrix where keys are tuples of two integers. Or one tree per row, where keys are single integers, column index.
Unlike CSR, inserting elements is Log(n). RAM overhead is larger than CSR but still reasonable, much smaller than hash maps or red-black trees would be. Similar to CSR, reading rows is mostly sequential RAM reads i.e. pretty fast.
I used these trees in the code that builds large sparse matrices from something else. The domain was CAM/CAE, it was finite elements. As a nice side effect, with one tree per row I was able to parallelize the construction of that matrix, as different CPU cores can update different rows of the matrix in parallel.
No, this is not the mathematical definition. An n-by-n matrix is usually considered sparse if the number of nonzero elements is O(n). Which means that the ratio of nonzero elements goes to zero as the matrix grows.
[1] https://arrow.apache.org/docs/cpp/api/tensor.html?highlight=...
[2] https://github.com/apache/arrow/blob/master/python/pyarrow/t...
If you know how it's supposed to work in theory but struggle to bang it out, you could do eg leetcode.
It's a generalized CSR/CSC (to ndim > 2) format that uses a tree data structure where each path from root to leaf encodes a nonzero element.
