使用符號表實現二元搜索樹索引

Question

我正在閱讀有關作者Robert Sedwick在C++算法中使用符號表實現的索引實現。

下面是從書中

我們可以適應二叉搜索樹建立索引的正是 相同的方式，我們的排序和堆提供間接片段。 像往常一樣，通過關鍵成員 函數安排從項目中提取密鑰。而且，我們可以使用並行數組作爲鏈接，就像我們爲鏈接列表所做的那樣。我們使用三個數組，每個數組用於 項目，左側​​鏈接和右側鏈接。鏈接是數組索引 （整數），並將我們替換鏈接引用如

X = X->升

在我們與數組引用如

爲X = L的所有代碼

[X] 。

這種方法避免了動態內存分配的每個 節點的項目的成本佔據了陣列，而不考慮搜索功能， 我們預先分配每個項目兩個整數來抱樹鏈接， 認識到我們需要所有 項目都在搜索結構中時，至少需要這麼多的空間。鏈接的空間不是 總是在使用中，但它在那裏供搜索例程使用，不需要任何時間開銷用於分配。這種 方法的另一個重要特徵是它允許額外的數組（額外的信息與每個節點相關聯的 ）被添加，而根本不改變樹操縱碼 。當搜索例程返回一個項目的索引時， 通過使用該索引訪問適當的數組，可以立即訪問與該項目相關聯的所有信息 。

實施BSTS在搜索的 項大型陣列，以幫助的這種方式有時是有用的，因爲它避免了 複製物品的額外費用進入ADT的內部表示，和分配的 開銷和建設的新。如果空間有限且符號表增長並且顯着縮小，特別是如果預先很難估計符號表的最大尺寸時，則使用陣列 不適用。如果沒有準確的大小 預測是可能的，未使用的鏈接可能會浪費項目 陣列中的空間。

我上面的文字問題是

1. 什麼是筆者的「因爲我們沒有爲鏈表，我們可以使用並行陣列來鏈接」是什麼意思？這個說法是什麼意思，什麼是平行陣列。

2. 作者所指的鏈接是數組索引，我們用x = l [x]替換鏈接引用，例如x = x-> l。

3. 作者所說的「這種方法的另一個重要特點是，它允許額外的數組（額外的信息與每個節點相關聯）被添加，而根本不需要改變樹操作代碼。」 ？

Answer 1

您似乎編輯了文本以取出有用的參考。無論是或者你有一個早期的文本版本。

我的第三版指出，索引構建在第9.6節中涵蓋，它涵蓋了過程，並行數組在第3章中進行了解釋。並行數組僅僅存儲有效負載（鍵和可能的數據保存在樹中）以及三個或更多個獨立陣列中的左/右指針，使用索引將它們連接在一起（x = left[x]）。在這種情況下，您可能會得到如下結果：

int leftptr[100]; 
int rightptr[100]; 
char *payload[100]; 

等等。在該例中，節點＃74將其數據存儲在payload[74]中，並且左側和右側「指針」（實際上是索引）分別存儲在left[74]和right[74]中。

這是相對於具有結構的單個陣列與該結構保持有效載荷和指針一起（x = x->left;）：

struct sNode { 
    struct sNode *left, right; 
    char payload[]; 
}; 

因此，對於特定的問題：

1. 平行陣列只是將樹結構信息從有效負載信息中分離出來，並使用索引將這些數組中的信息捆綁在一起。

2. 由於您正在使用數組作爲鏈接（並且這些數組現在保存數組索引而不是指針），因此不再使用x = x->left移動到左側子級。而是使用x = left[x]。

3. 樹操作只對鏈接感興趣。通過使鏈路與有效負載分離（以及其他可能有用的信息），用於操縱樹結構的代碼可以更簡單。

Answer 2

如果您還沒有準備好，你應該翻轉回在書中，他說，該技術以前用於（它可能解釋有）上鍊表部分。

並行數組意味着我們沒有一個結構來保存節點信息。我們有數組。我們有數組。

int data[SIZE]; 
int left[SIZE]; 
int right[SIZE]; 

這些平行的陣列，因爲我們將使用相同的索引來訪問數據和鏈接。節點在我們的代碼中由索引表示，而不是指針。因此，對於節點4中，數據是在

data[4]; 

左鏈接是在

left[4]; 

在節點增加更多的信息可以通過創建具有相同的尺寸的另一個陣列來完成。

int extra[SIZE]; 

節點4的額外數據將在從STL

extra[4];