合併演算法用於將兩個有序列表合併成一個列表。此演算法在不同情況下使用。如果我們想要執行歸併排序，那麼我們需要將排序後的列表合併成更大的列表。方法很簡單。我們取兩個列表，將有兩個指標。第一個指向第一個列表的元素，第二個指向第二個列表的元素。根據它們的值，從這兩個列表中的一箇中取出較小的元素，然後增加相應列表的指標。此操作將... 閱讀更多

當我們嘗試實現抽象資料型別字典時，節點與值相關聯。字典基本上是一組鍵，這些鍵必須是從全序中提取的元素。可能還有其他資訊與每個鍵相關聯，但這不會導致任何概念上的理解。如果字典使用樹實現，則每個節點將儲存唯一的鍵。這裡對於樹中的每個節點 u，每個鍵 u.l 都嚴格小於 u.k。並且 u.r 中的每個鍵都嚴格大於 u.k。樹根據此不變式組織... 閱讀更多

在本節中，我們將瞭解什麼是 Robin-Hood 雜湊方案。這種雜湊是開放定址技術之一。它試圖透過使用更公平的衝突解決策略來平衡元素的搜尋時間。當我們嘗試插入時，如果我們想在位置 xi 插入元素 x，並且已經有元素 y 放在 yj = xi，則兩個元素中較年輕的必須移動。因此，如果 i ≤ j，則我們將嘗試在位置 xi+1、xi+2 等插入 x。否則，我們將 x 儲存在... 閱讀更多

在本節中，我們將瞭解什麼是 LCFS 雜湊。這是開放定址策略之一，它改變了衝突解決策略。如果我們檢查開放地址方案中雜湊的演算法，我們可以發現如果兩個元素髮生衝突，則優先順序更高的元素將被插入表中，後續元素必須繼續移動。因此，我們可以說開放定址方案中的雜湊是 FCFS 標準。使用 LCFS（後進先出）方案。任務的執行方式完全相反。當我們插入一個元素時，它將被放置在位置... 閱讀更多

在本節中，我們將瞭解什麼是非對稱雜湊技術。在這種技術中，雜湊表被分成 d 個塊。每個拆分長度為 n/d。探測值 xi，0 ≤ i ≤ d，是從 $$\lbrace\frac{i*n}{d}, ..., \frac{(i+1)*n}{d-1}\rbrace$$ 中均勻抽取的。與多選雜湊一樣，要插入 x，演算法檢查列表 A[x0]、A[x1]、...、A[xd – 1] 的長度。然後將 x 附加到這些列表中最短的列表中。如果出現平局，則將其插入到索引最小的列表中。根據 Vocking，預期長度為... 閱讀更多

這裡我們將瞭解什麼是平衡二叉搜尋樹。二叉搜尋樹 (BST) 是二叉樹，其左子節點具有較小的元素，右子節點具有較大的元素。搜尋 BST 中元素的平均時間複雜度為 O(log n)。它取決於二叉搜尋樹的高度。為了維護二叉搜尋樹的屬性，有時樹會變得傾斜。因此，傾斜的樹將如下所示：這實際上是一棵樹，但它看起來像一個連結串列。對於這種樹，搜尋時間將... 閱讀更多

在本節中，我們將瞭解與開放定址雜湊相關的 Brent 方法。此方法是一種啟發式方法。它試圖最小化雜湊表中成功搜尋的平均時間。此方法最初應用於雙重雜湊技術，但它可以用於任何開放定址技術，如線性探測和二次探測。儲存在開放定址雜湊表中的元素 x 的年齡是使 x 放在 A[xi] 的最小值 iBrent 方法試圖最小化所有元素的總年齡。如果我們插入一個元素 x，... 閱讀更多

在本節中，我們將瞭解開放定址方案中的雙重雜湊技術。有一個普通的雜湊函式 h´(x) : U → {0, 1, . . ., m – 1}。在開放定址方案中，實際的雜湊函式 h(x) 在空間未滿時採用普通的雜湊函式 h’(x)，然後執行另一個雜湊函式以獲得一些空間進行插入。$$h_{1}(x)=x\:mod\:m$$$$h_{2}(x)=x\:mod\:m^{\prime}$$$$h(x, i)=(h^{1}(x)+ih^{2})\:mod\:m$$i 的值為 0、1、...、m – 1。因此，我們從 i = 0 開始，並增加它，直到我們獲得一個空閒空間。因此，最初當 i = ... 閱讀更多

在本節中，我們將瞭解開放定址方案中的二次探測技術。有一個普通的雜湊函式 h’(x) : U → {0, 1, . . ., m – 1}。在開放定址方案中，實際的雜湊函式 h(x) 採用普通的雜湊函式 h’(x) 並附加一些其他部分以構成一個二次方程。h´ = (𝑥) = 𝑥 𝑚𝑜𝑑 𝑚ℎ(𝑥, 𝑖) = (ℎ´(𝑥) + 𝑖2)𝑚𝑜𝑑 𝑚我們也可以使用一些常數放置其他二次方程i 的值為 0、1、...、m – 1。因此，我們從 i ... 閱讀更多

在本節中，我們將瞭解開放定址方案中的線性探測技術。有一個普通的雜湊函式 h´(x) : U → {0, 1, . . ., m – 1}。在開放定址方案中，實際的雜湊函式 h(x) 採用普通的雜湊函式 h’(x) 並附加一些其他部分以構成一個線性方程。h´(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚ℎ(𝑥, 𝑖) = (ℎ´(𝑥) + 𝑖)𝑚𝑜𝑑 𝑚i 的值為 | = 0、1、...、m – 1。因此，我們從 i = 0 開始，並增加它，直到我們獲得一個空閒空間。因此，最初... 閱讀更多