有關數據結構的小問題

Question

我試圖用Kruskal算法搜索節點的父節點。我的程序運行良好，但我想我已經聽說過一種方法，通過在搜索父節點並將其連接到父節點時重構樹來提高算法的速度。我非常肯定，我聽說過這個地方，也許是在講座中。任何人都能刷新我的記憶？

此外，給定數量的數組時，當從數組的某個部分搜索最小值和最大值時，樹的名稱可以通過使數組計算最小值/最大值O（log N）中每個數組的最小值/最大值的二叉樹？

Answer 1

關於你的第二個問題：我想你說的是heap。一個堆可以檢索O（1）中的最大值或，並在O（log n）中刪除它。

但是，有一些複雜的數據結構，它們是爲了處理完整的列表（即它們不是爲最小/最大訪問而設計的）。這些也支持同時訪問最大數量和。一些著名的例子：

• Red-Black-Tree
• B-Tree（攤銷O（log n）的）
• Splay-Tree（攤銷O（log n）的）

關於你的第一個問題：Kruskals algorithm用於計算一個minimum spanning tree。但是既然你提到了「父節點」，我認爲你所考慮的結構已經是一棵樹了。但是如果結構已經是樹，Kruskals算法只返回樹本身。你可以澄清你的意思是「父節點」

Answer 2

對於第一個問題，您正在尋找Disjoint-set data structure。

對於第二個問題，我假定您詢問範圍最小/最大查詢。數據結構是Cartesian Tree。