使用什麼數據結構來進行O（log n）鍵和值查找？

Question

有一個排序字典（散列表，地圖或任何鍵/值結構），你可以很容易地進行二進制搜索尋找一個項目。如果我們假設密鑰是唯一的，但值可能會重複，那麼可以使用什麼數據結構對密鑰進行O（log n）檢索，還可以使用O（log n）查詢來查找給定數據中的計數values=something？

Answer 1

兩個二叉搜索樹，一個用於鍵，第二個用於值，具有相互指針，將提供所需的功能。指針可以是從鍵到值的多對一，也可以是從值到鍵的一對多。