O（1）時間內平衡二進制搜索時間的最小/最大元素

我知道我們可以在O（logn）時間的二叉搜索樹中找到最小/最大值。但在C++中的地圖給了我們恆定時間的最小/最大值。我們可以在地圖上使用map::begin和最大值使用map::rbegin找到最小元素。這兩項操作都需要一定的時間。任何人都可以提出一個方法，使找到最小/最大O（1）？O（1）時間內平衡二進制搜索時間的最小/最大元素

來源

2016-06-11 Shivam Mitra

存儲兩個指針以及根。 – molbdnilo

std :: map通常是用搜索樹實現的，所以你的意思是通過hashmap實現的std :: unordered_map。由於hashmap不關心訂單，我們無法在O（1）中找到最小值。當你想在O（1）中獲得最小/最大值而不刪除它時，我會建議你使用最小堆或最大堆 – Exagon

@Exagon：我的意思是ordered_map。你可以看看map :: rbegin和map :: begin。 –

C++映射不是由BST實現的。它由紅黑樹實施。如果要通過O（1）在BST中查找最小/最大值，則可以將這兩個指針存儲在樹中最左邊的節點和最右邊的節點上。否則，您可以使用minheap或maxheap找出O（1）中的最小/最大值。

來源

2016-06-11 20:49:51

是的，我們可以做到這一點。但刪除最小/最大節點會更改指針。這仍然需要O（logn）來找到新的最小值/最大值。 –

不，它可以在O（1）中再次完成。即使您在刪除期間刪除最小節點（假設），您也可以將最小指針更新爲最小節點的後繼節點。所以，在任何時候你都可以在O（1）中得到你的最小值，最大值。你可以說你正在增加你在刪除中的複雜性。但那仍然是O（logn）。 –

紅黑樹也是一個二進制搜索樹，只是說 – Exagon

O（1）時間內平衡二進制搜索時間的最小/最大元素

回答

相關問題