使用二叉搜索樹實現稀疏矩陣

Question

我必須實現一個稀疏矩陣（主要爲零的矩陣，所以你只記錄不同於0的值），但我必須使用二叉搜索樹來實現它。

編輯：

所以現在我想通過使用行/列作爲一個關鍵的實現它，但我該怎麼作爲樹的根使用？

/EDIT

我希望當我研究了二叉搜索樹我能明白這一點的實現將如何是有益的，或者至少是可能的，但我爲我的生活不能弄清楚。

我曾試圖谷歌無濟於事，我自己無法想象如何甚至嘗試這樣做。

我還沒決定使用哪種語言，所以我不需要代碼示例，我的問題就是邏輯。我需要看看這將如何工作。

P.S.我不知道要使用什麼標籤，如果有人可以編輯一些標籤，這將非常感激。

Answer 1

要使用二叉樹，您需要爲矩陣中的每個（可能）條目指定一個不同的鍵。所以如果你想在矩陣[100，100]中查找（2，4），那麼鍵可以是類似「002004」的東西。用這個鍵你可以在樹中插入一個值。

對於每個維度，密鑰會更長，因此您還可以考慮使用散列函數來散列單元格的座標，並在樹中爲此散列密鑰提供條目列表。那麼樹只是右列表的一個索引。在列表中，您需要執行順序搜索。或者，如果您訂購清單，則可以通過使用二分查找來改進。