增強間隔樹

Question

我試圖通過使用按區間的「低」值排序的平衡二叉搜索樹來實現augmented interval tree。

在普通的舊搜索樹中，當試圖插入已存在於樹中的密鑰時，通常忽略重複（無插入）。

但是，當存儲間隔時，我可能有（1,2）和（1,3），它們具有相同的「低」值但不同。

如何處理擴增間隔樹中重複的「低」值？我的意思是，我應該允許插入多個相同的「低」值嗎？按什麼順序？以及如果有重複密鑰，如何在樹中搜索？

Answer 1

鏈接的文章建議使用每個區間的高值作爲次要排序。然後你有間隔的總訂單，你可以正常搜索。相交查詢不需要具有相同低值的間隔中的特定順序;一旦你編寫代碼，這將變得很明顯。