帶有隱式鍵的Treap

Question

有一個名爲treap的數據結構：這是一個隨機二叉搜索樹，它也是隨機生成的所謂「優先級」上的堆。

這種結構存在變化，其中鍵是隱式的，它們不存儲在樹中，但我們將樹中節點的有序索引視爲此節點的鍵。我們需要在每個節點中存儲子樹的大小而不是密鑰。這種技術使我們能夠像某種數組一樣思考treap，它支持O（log N）時間內的大量操作：插入，刪除，子數組反轉，間隔變化等等。

我對這個結構有所瞭解，但沒有那麼多。我試圖谷歌它，但我發現只有很多關於treap本身的文章，但沒有關於這個「隱式treap」/「索引列表」。我甚至不知道它的名字，因爲我的母語不是英語，我聽過的講座使用了結構的本地術語，而不是英語的原始術語。這個本地術語可以直接用英語翻譯爲「隱式密鑰上的樹」或「隱式密鑰上的笛卡爾樹」。

任何人都可以在關於這個結構的文章中指出我的意思，或告訴我它的原名嗎？謝謝。

P.S.對不起，如果我的英語不夠理解。

UPD：關於我正在尋找的結構的一些額外解釋。

考慮一個通常的隨機選擇優先級和密鑰，它們是存儲在樹中的實際用戶數據。然後讓我們想象一下，在每個節點中都存儲有其他用戶信息，而鍵只不過是搜索鍵。下一步是計算並維護每個節點中的子樹大小：我們必須在每個合併/拆分/添加/刪除後更新此參數，但它允許我們在O（log N）中查找樹的第K個元素，時間。

當我們在每個節點中都有子樹大小時，我們可以丟棄密鑰並設想treap代表一個用戶數據在inorder遍歷中的數組。每個元素的數組索引可以通過子樹大小輕鬆計算。現在我們可以在數組中間添加/移除一個元素，或者分割這個數組 - 全部在O（log N）時間。

我們也可以進行「多重」操作 - 例如，爲我們的「數組」中的所有元素添加一個常數值。爲了實現這個，我們必須使這個操作延遲，在每個節點中添加一個參數，該參數表示一個延遲常量，該參數必須「稍後」添加到此節點的子陣列的所有元素中，並將變化「向上」推送爲必要。向子陣列添加常量或繪製（標記）子陣列可以以這種方式進行延遲，如顛倒子陣列（這裏位於「子陣列中的節點中的延遲信息必須顛倒」）等等。

UPD2：這是code snippet - 我找到的少量信息。不要注意西裏爾字母:)單詞「снеявнымключом」的意思是直接翻譯「隱含密鑰」。

Answer 1

您可以在Kaplan和Verbin的論文中找到這種數據結構，其中包括通過反轉排序簽名排列（第7頁，第3.1節）：http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf。

Answer 2

在treaps中的關鍵思想（沒有雙關意圖！）是使用密鑰，這是隨機的。如果你把鑰匙取下來，我看不出你有什麼樣的方法：所以也許我誤解了你的問題。或者您可能指的是trevert的替代方案，隨機二分搜索樹。兩種數據結構都使用相同的思想，通過確保您的樹看起來像平均樹（而不是病態），您可以獲得平均情況下的複雜性。

隨着treaps，你使用隨機優先級和平衡來做到這一點。

對於隨機二叉樹，隨機性僅在構造過程中被包含：也就是說，當您在樹T中插入節點時，其概率爲1 /（size（T）+ 1）爲根，其中大小（T）是T的節點數量;當然如果節點沒有插入到根目錄下，你將繼續遞歸直到它被添加。 （請參閱我的C.馬丁內斯關於這些樹的詳細研究的文章。）

此數據結構的行爲完全像treap，但使用不需要密鑰的不同機制。

如果這不是你正在尋找的東西，也許你可以分享一些額外的信息：你的講師是否提到過任何可能在這個結構上工作過的人，你在哪裏講這個講師以及他/你的國籍。它可能看起來不像，但知道你的母語可能是一個重要的線索，因爲你通常可以將算法/數據結構固定到源自它的特定國家。

Answer 3

我不認爲這個數據結構有一個名稱，因爲它只是兩個正交概念的組合。你可以像這樣使用隱式鍵來處理任何自平衡樹數據結構。

您可能想看看替罪羊樹，因爲它們已經使用子樹大小進行重新平衡，並且不需要任何每個節點的開銷。

Answer 4

也許您在尋找一種Rope（字符串的複雜形式），以適應您對延遲操作的需求。有趣的是，關於繩索right here right now有一個懸而未決的問題。