AVL樹：如何做索引訪問？

我在AVL Tree Wikipedia page注意到以下注釋：AVL樹：如何做索引訪問？

「如果每個節點還記錄其子樹（包括本身和它的後代）的大小，則該節點可以通過指數爲O檢索（log n）的時間作爲好。」

我有谷歌，發現少數地方提accessing by index，但似乎無法找到一個算法會寫的說明。

非常感謝

[更新]謝謝大家。如果發現@templatetypedef與@一個答案結合user448810 links以特別幫助。特別是這個snipit：

「這兩個函數的關鍵是，一個節點的索引是它左邊的孩子的大小，只要我們通過它的左邊孩子下降一棵樹，我們只需要索引但是當我們必須通過右邊的孩子向下移動樹時，我們必須調整大小以包含我們排除的樹的一半。「

因爲我的實現是不可變的，我並不需要做任何額外的工作重新平衡時，每個節點計算它的建築規模（相同鏈接的方案IMPL）

我最終實現結束了：

class Node<K,V> implements AVLTree<K,V> { ... 
    public V index(int i) { 
     if (left.size() == i) return value; 
     if (i < left.size()) return left.index(i); 
     return right.index(i - left.size() - 1); 
    } 
} 

class Empty<K,V> implements AVLTree<K,V> { ... 
    public V index(int i) { throw new IndexOutOfBoundsException();} 
}

這與其他實現方式略有不同，讓我知道，如果你認爲我有一個錯誤！

來源

2012-06-08 Daniel Worthington-Bodart

這種結構背後的總體思想是利用現有的BST，並通過存儲在左子樹的節點的數目增加每個節點。一旦你做到了這一點，你可以看一下第n個節點的樹通過以下遞歸算法：

要查找的第n個元素的BST其根節點在其左子樹k個元素：
- 若k = n時，返回根節點（因爲這是樹中的第零節點）
- 如果n ≤ K，遞歸地查找該第n個元素的左子樹。
- 否則，查找第（n - K - 1）個元件在右子樹。

這需要時間O（h）中，其中h是樹的高度。在AVL樹中，這個O（log n）。在CLRS，這種結構被探索應用於紅/黑樹，他們稱這種樹爲「訂單統計樹」。

在樹輪旋轉過程中，您必須添加一些額外的邏輯來調整左子樹中緩存的元素數量，但這並不是特別困難。

希望這會有所幫助！

來源

2012-06-08 21:04:35 templatetypedef

儘管我同意這是做事的正確方式，但它似乎並不像維基頁面所涵蓋的那樣相同（它存儲了整個子樹的大小，而不是左子樹）。他們正在做的事情（顯然）需要一點點笨拙，通過減去右子樹的大小或查看左子樹來獲得左子樹的大小以找到它的大小。 –

@ JerryCoffin-我已經勾畫出的方法與此方法相關。如果每個子樹存儲它的總大小，我可以通過查看左邊孩子的總大小來查找左邊子樹的大小（如果有的話）。這兩種方法基本上是同構的。 – templatetypedef

然而，我想再看看他們的系統有一個優勢：它支持從任何一端進行索引，因此從集合的末尾對N進行索引就像從一開始就一樣簡單。 –

AVL樹：如何做索引訪問？

回答

相關問題